The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Backtracking

Problem :-
Solve the Knight's tour problem i.e find a Knight's tour on a 8 x 8 chessboard.
A Knight's tour is a sequence of moves of Knight on a chessboard such that the knight visits every square exactly once.

Solution :-
A Knight is placed on the first cell of an empty chessboard and can move according to the chess rules.
At any point on the chessboard, the knight have a maximum of 8 possible options to make a move.
1 ) Suppose, the knight is currently in cell ( x , y ) and it chooses one of the possible moves to a cell ( if the cell is not visited previously and the move is indeed a valid one ). Then, we move the knight to that cell and check recursively whether we can find a solution from that cell. If the solution exists, then that cell is marked as visited and then again knight chooses one of the possible moves and follows same steps.
2 ) If the solution doesn't exits, then the knight backtracks to the previous cell ( x , y ) and tries out other possible alternatives.
When all the cells are visited, we have found a sequence of knight moves which visits every cell on the chessboard exactly once. See the implementation below.