# The Knight’s Tour

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):    assert board[x][y] == 0    board[x][y] = num_move                                      possible_moves = getPossibleMoves(x,y)    numOfMoves = []          for move in possible_moves:        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.

Standard

## One thought on “The Knight’s Tour”

1. Jack says:

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