This repository animate the solution of the 8 queens puzzle (and the general case of N queens puzzle) using a backtracking algorithm.
The 8 queens puzzle is concerned with placing 8 queens in an chess board such that no queen threatens any other queen. Please read more on the eight queens puzzle here. In this repo we present a solution to the general N queens puzzle in chess board.
Backtracking is a general problem solving technique that builds a solution incrementally and abandons "backtracks" a candidate move if it will lead to invalid solution. Please read more on backtracking here. In the case of the eight aueens puzzle, assume we placed queens in the first rows. The algorithm places a queen in the row as long as it does not threaten a previously placed queen in any of the previous rows. If that is not possible, the algorithm removes the queen in the row and try to find a new position for it. If it succeeds, it proceeds forward. Otherwise, it goes backward again to the row and so on.
In the animation, the forward move is hightlighted in yellow, the backward move is highlighted in red, and a solid red line is drawn to connect the two queens that threaten each other. Watch the animation: