#!/usr/bin/python ## Uncomment the following two lines ## to enable JIT compilation. #import psyco #psyco.full() knightsmoves = [(-1,-2), (-2,-1), (1,-2), (-2,1), (-1,2), (2,-1), (1,2), (2,1)] ## Uncomment one of the following two definitions if you ## Want an alternative order of search. #knightsmoves = [((-1)**y*(1+x), (-1)**z*(2-x)) # for x in [0,1] # for y in [0,1] # for z in [0,1]] #knightsmoves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] def add(pos1,pos2): return (pos1[0] + pos2[0], pos1[1] + pos2[1]) def onboard(pos): return (pos[0] >= 0) and \ (pos[0] < 8) and \ (pos[1] >= 0) and \ (pos[1] < 8) def moves(pos): return [newpos for newpos in [add(pos,move) for move in knightsmoves] if onboard(newpos)] def filmoves(pos,soln): return [newpos for newpos in moves(pos) if not (newpos in soln)] def compval(pos1,pos2,soln): return len(filmoves(pos1,soln)) - len(filmoves(pos2,soln)) def sortedmoves(soln): list = filmoves(soln[0],soln[1:]) list.sort(lambda x,y: compval(x,y,soln)) return list def extend(soln): if len(soln) == 64: if soln[-1] in moves(soln[0]): return soln else: return False else: for newpos in sortedmoves(soln): # We have already checked this #if newpos in soln: # continue #print "(",newpos[0],",",newpos[1],")" sol=extend([newpos]+soln) if not sol: continue else: return sol return False def printsol(soln): line = "-" for i in range(8): for j in range(8): line = line + "-----" print line line = "|" for j in range(8): line = line + " %2i |" % (64-soln.index((i,j))) print line line = "-" for j in range(8): line = line + "-----" print line ## Uncomment these lines if you want an executable #from sys import argv # #if (len(argv) > 2): # printsol(extend([(int(argv[1]), int(argv[2]))])) #else: # print "Usage:",argv[0],"x y\n",