I saw an online game around the knight’s tour problem the other day and it made me think of mathematics of chess puzzles. You know… Domination, independence (eight queens) etc. I thought it would be a good way to go back to writing some Python code after a long break.

The “Knight’s Tour” is a problem in which the objective is to move a knight, starting from any square on a chessboard to every other square landing on each square only once. Euler is said to be the first one to study this problem in 1759 on a 8 x 8 board. A knight’s tour is a Hamiltonian path. A closed tour is a Hamiltonian cycle i.e. the last square visited is also reachable from the first square by a single knight’s move. For all even n >= 6 there exists a closed knight’s tour on an n x n chessboard and an open knight’s tour if n >= 5.

We can create a matrix of size n x n with not visited cells filled with zeroes and every other cell to be filled with the order visited in the tour.

`board = []`

board_size = -1

`def initiateBoard (board_dimensions):`

global board

global board_size

global knights_moves

board_size = board_dimensions

for i in range(0, board_size):

board.append(board_size*[0]) #untouched board

```
```

` `

Given knight’s behavior the possible moves relative to knight’s location are

`knights_moves = ((-2,-1),(1,2),(2,-1),(-2,1),(2,1),(-1,2),(1,-2),(-1,-2))`

But depending on where knight is on the board, not all moves will work so we should check whether a certain point is on the board and not visited.

`def isAvailable(x, y):`

if x < len(board) and y < len(board[0]) and \

x >= 0 and y >= 0 and board[x][y]==0:

return True

else:

return False

Naïve backtracking is a possible solution but for an 8×8 board, there exist 33,439,123,484,294 un-oriented paths so instead I will use Warnsdorff’’s rule to get to the solution a bit quicker. According to this heuristic method, knight always proceeds to the square from which it will have the fewest onward moves.

` `

```
````def`

getPossibleMoves(x, y):

possible_moves = []

for move in knights_moves:

cx,cy = x+move[0], y+move[1]

if isAvailable(cx,cy):

possible_moves.append((move[0],move[1]))

return possible_moves

`def`

getNumMoves(x, y):

return len(getPossibleMoves(x, y))

`def`

getNextMove (numMoves):

smallestIndex = 0

if not numMoves: #Nowhere to go

drawBoard() #Show the results

sys.exit(1)

smallest = numMoves[0]

for i in range(len(numMoves)):

if numMoves[i] < smallest:

smallest = numMoves[i]

smallestIndex = i

return smallestIndex

` `

And finally the recursion to find the complete path

`def`

solve (x,y,num_move):

board[x][y] == 0`assert`

board[x][y] = num_move

possible_moves = getPossibleMoves(x,y)

numOfMoves = []

move `for`

possible_moves:`in`

numOfMoves.append(getNumMoves(x+move[0],y+move[1]))

nextMove = possible_moves[getNextMove(numOfMoves)]

solve(x+nextMove[0],y+nextMove[1],num_move+1)

`def getKnightsPath (board_dimensions):`

initiateBoard (board_dimensions)

solve(0,0,1)

I’m leaving drawBoard() function to your imagination, but here is what I got using matplotlib.path.

For scaling to very large boards a divide-and-conquer solution would be necessary. If I can find some time, I’d also like to share a parallel implementation here.

Nice. I’d have never thought of using path for this purpose. I see what you did there. Clever.