fixed logic bug. now 4 lines.
This essentially proves that badly written python is almost as unitelligible as badly written perl. Interestingly badly written python is easier to debug than badly written perl. But then again perl-golf is played for characters not lines! for example, bzip2 is done in 55 perl characters.
def recurse((position, visited),xdim= int(__import__("sys").argv[1]),ydim=
int(__import__("sys").argv[2])):
map(recurse,sorted([(t,visited+[t]) for t in (lambda t: [ (t[0]+2, t[1]+1), (t[0]+2, t[1]-1), (t[0]-2, t[1]+1), (t[0]-2, t[1]-1), (t[0]-1, t[1]+2), (t[0]-1, t[1]-2),(t[0]+1, t[1]+2),(t[0]+1, t[1]-2)])(position) if 0<=t[0]<xdim and 0<=t[1]<ydim and t not in visited],lambda x,y:cmp(len( [1 for t in [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] if (x[0][0]+t[0],x[0][1]+t[1]) in visited ] ),len( [1 for t in [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] if (y[0][0]+t[0],y[0][1]+t[1]) in visited ] ))))
if len(visited) == xdim*ydim: print "success: %s"%str(visited).strip("[]"),__import__("sys").exit()
for ii,jj in [ (i,j) for i in xrange((int(__import__("sys").argv[1])+1)/2) for j in xrange( (int(__import__("sys").argv[2])+1)/2) ]: recurse(((ii,jj),[(ii,jj)]))