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)