The touring knight problem is a maths problem that takes the movement of a knight in chess and attempts to find a path around a two dimensional board such that every single square is visited exactly once.

There are more sofisicated solutions but as you might have imagined, brute forcing is the most naive approach to solving this problem.

By trying every possible combination of legal move from your current position you can follow through every legal path and check whether you've completed the board or not.

It starts with a board.

class Board(object): def __init__(self, height = 8, width = 8, board = None): self._board = [] if board is None: self.height = height self.width = width for y in xrange(self.height): self._board.append([False] * self.width) else: self.height = board.height self.width = board.width for y in xrange(self.height): row = list() for x in xrange(self.width): row.append(board.get(y, x)) self._board.append(row) def set(self, y, x, value): self._board[y][x] = value def get(self, y, x): return self._board[y][x] def __len__(self): return width * height def copy(self): return Board(board = self) def isValidPosition(self, (y, x)): return (width > 0) and (y >= 0 and y < height) and (x >= 0 and x < width) def isValidMove(self, (y, x)): if self.isValidPosition((y, x)): return not bool(self.get(y, x)) return False def __str__(self): s = "" for y in xrange(self.height): s += ("+---" * self.width) + "+\n" row = "|" for x in xrange(width): row += "% 3d|" % (board.get(y, x)) s += row + "\n" s += ("+---" * width) + "+\n" return s

Which combined with the number of squares we've so far visited allows us to determine if we've visited everywhere.

def IsBoardComplete(board, depth): return len(board) == depth

Simples. Now we need a method to determine out possible options from any square.

def PossibleMoves(board, position): # +-+-+-+-+-+ # | |x| |x| | # +-+-+-+-+-+ # |x| | | |x| # +-+-+-+-+-+ # | | |o| | | # +-+-+-+-+-+ # |x| | | |x| # +-+-+-+-+-+ # | |x| |x| | # +-+-+-+-+-+ y, x = position Moves = [] for yoffset in [-1, 1]: for xoffset in [2, -2]: newPosition = y + yoffset, x + xoffset if board.isValidMove(newPosition): Moves.append(newPosition) for yoffset in [-2, 2]: for xoffset in [1, -1]: newPosition = y + yoffset, x + xoffset if board.isValidMove(newPosition): Moves.append(newPosition) return Moves

The main logic of the tour is a recursive function that attempts every path and upon completion appends the path to a list of successful paths. We carry around how many paths we've calculated for fun.

def Tour(board, position, tryCount = 0, found = None, sequence = 1): y, x = position board.set(y, x, sequence) tryCount += 1 if found is None: found = [] if IsBoardComplete(board, sequence): if board in found: return tryCount, found found.append(board.copy()) print "Board complete" print board board.set(y, x, False) # unset last position return tryCount, found Moves = PossibleMoves(board, position) for newPosition in Moves: tries, _ = Tour(board, newPosition, tryCount, found, sequence + 1) tryCount += tries board.set(y, x, False) return tryCount, found

We initialise and kick things off by iterating over every possible starting position to get every possible way to complete our board.

if __name__ == '__main__': width, height = 3, 4 for y in xrange(height): for x in xrange(width): startPosition = (y, x) board = Board(width = width, height = height) print "Starting from position", y, x tries, found = Tour(board, startPosition) if not found: print "There are no solutions for this board when starting from", y, x, "tried", tries, "combinations" else: print "Found", len(found), "complete boards after", tries, "tries when starting from", y, x for board in found: print board sys.exit()

This is something I toyed with on one of my long journeys to London and back that I have to do every week.