Knight’s Tour Problem | Backtracking

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

Knight Moves Image
Knight Moves Image
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 Falseif __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')
knight moves
knight moves

I’m an undergrad student at IIIT Ranchi, pursuing my B-Tech in computer science and Engineering. I love to learn and share new technologies.