Recursive backtracking
Eight queens puzzle
Javascript (animated)
click on a square on the chessboard to place a queen
| Start | ⏮️ | ▶️ | ⏸️ | ⏭️ |
This animation shows how a backtracking algorithm works on the eight queens puzzle. The algorithm only takes a few milliseconds, but is shown here at a slower speed to show how it works. The following code shows how to solve this problem with Javascript.
Procedure: Go through the rows from top to bottom, the columns from left to right, checking to see if it is possible to place a queen; if it is possible, place the queen and go to the next row. If positioning is not possible, go back one row and move that queen further to the right; if repositioning is not possible, go back another row, this can go back to the beginning. The row of the fixed queen is skipped.
Eight queens puzzle at Wikipedia
NOTE: When the animation starts, the algorithm has already run through, every change to the board has been saved and will be played through the animation. Since this is a representation of recursive backtracking, the animation script is not part of the source code.
Javascript source code: