Knight’s Tour Problem | Backtracking

Knight’s tour is a problem in which we are provided with a NxN chessboard and a knight.

According to the problem, we have to make the knight cover all the cells of the board and it can move to a cell only once.

There can be two ways of finishing the knight move — the first in which the knight is one knight’s move away from the cell from where it began, so it can go to the position from where it started and form a loop, this is called closed tour; the second in which the knight finishes anywhere else, this is called open tour.

How to make an recursive intuition for this problem. First Lemme show you the Code for this problem and then I’ll explain you what is happening in the code.

rowDir = [2,1,-1,-2,-2,-1,1,2]
colDir = [1,2,2,1,-1,-2,-2,-1]
def canPlaceKnight(board, row, col, n):
   return row >=0 and col >=0 and row < n and col < n and board[row][col] == 0
def solveKnightMove(board, n, move_no, currRow,currCol):
    if move_no == n*n:
        return True
    for i in range(8):
        nextRow = currRow + rowDir[i]
        nextCol = currCol + colDir[i]
        if canPlaceKnight(board, nextRow, nextCol, n):
            board[nextRow][nextCol] = move_no + 1
            isSuccessfull = solveKnightMove(board, n, move_no+1, nextRow, nextCol)
            if isSuccessfull:
                return True
            board[nextRow][nextCol] = 0
return False
if __name__ == "__main__":
    n = 5
    board = [[0 for i in range(n)] for i in range(n)]
    if solveKnightMove(board, n, 1, 0, 0):
        print(board)
    else:
        print('Not Possible Solution')

The figure in left shows the possible movement coordinates of a knight on chess board. from here I have chosen the row and col list.

My solveKnightMove() function calculates all possible moves (Total 8) using a loop.

The next move co-ordinates are calculated and then is checked using canPlaceKnight() function, which return true if the move is valid. If the move is valid then we fill the board with move and order recursion to calculate the rest solution for us. If the move is invalid i.e canPlaceKnight() function return False, then next among 8 possible coordinates is checked.
If Knight is not able to move at any 8 possible coordinates than our function return False.

This is a solution for 5*5 board.
Here 1, 2, 3, 4 …. signifies the next cell movement.