The Knight’s tour is a puzzle in a N * N chessboard where Knight makes sequence of moves and must visit every square exactly once.
This problem can be solved with backtracking.
We begin the solution by placing knight at (0, 0).
At every position, we try the possible moves to find a valid one. If we find a valid move, we move the knight to that position. If we don’t find such valid move, we backtrack and try to re-position the previous move.
If we have completed all the squares of the board, we have a solution. If we have tried all possible moves and could not cover all the squares, we have failed to find a solution.