knights_tour.py

class KnightsTour():
    '''Knights Tour using Warnsdorf's rule as heuristics'''

    def __init__(self, N, start_point=(0,0)):
        self.N             = N
        self.initial_state = (start_point, )
        # all relative moves expressed as displacement in 2D
        self._actions      = [(1,2), (1,-2), (2,1), (2,-1),\
                              (-1,2), (-1,-2), (-2,1), (-2,-1)]

    def actions(self, s):
        '''Possible actions from a state.'''
        # generate every possible state and filter unvalid ones
        return [a for a in self._actions if self._is_valid(self.result(s, a))]

    def result(self, s, a):
        '''Result of applying an action to a state.'''
        last_x, last_y = s[-1]; 
        delta_x, delta_y = a

        b = list(s)     # make mutable to add next move
        b.append((last_x+delta_x, last_y+delta_y))
        return tuple(b) # immutable to search


    def _is_valid(self, state):
        last_s = state[-1]
        if last_s in state[:-1]:
            return False

        for (sx, sy) in state:
            if ( not (0 <= sx < self.N) or  not (0 <= sy < self.N) ):
                return False

        return True

    def heuristic(self, state):
        # how many actions can be performed in given state
        return len(self.actions(state))

    def go_on_a_ride(self):
        s = self.initial_state
        for i in range(self.N**2-1):
            # get all state and their respective heuristics
            d = {i: self.heuristic(self.result(s, i)) for i in self.actions(s)}
            a = min(d, key=d.get) # get the action that leads to a state 
                                  # that has least possible actions
            s = self.result(s, a)
            if not s:
                print "Sorry no Knights tour starting from", self.start_point
                return
        self.print_board(s)

    def print_board(self, s):
        board = s
        N     = self.N
        for i in range(N):
            for j in range(N):
                if (i,j) in board:
                    print "%3s" % s.index((i,j)),
                else:
                    print '.',
            print ''

## Define the size of board NxN and the start point
problem = KnightsTour(N=8, start_point=(0,0))
problem.go_on_a_ride()