The -queens problem is the problem of placing queens on an chessboard such that no two queens are attacking each other. The following tool provides a visualization of a “brute-force” algorithm for solving the problem. This algorithm advances across the board column by column. In each column, the queen is moved down until it no longer conflicts with any of the previous queens. Once such a position is found, the queen in the next column is placed. This continues until the last queen is placed, solving the problem. If at any time a queen in a certain column cannot be placed anywhere, we “backtrack” to the previous column and move that queen down to its next valid position. Once we have placed all queens, we can continue this algorithm to find other solutions.
This tool shows the current queen in blue. Queens that conflict with the current queen as it is moved are shown in red. The top row of numbers shows the position (row number) of each queen in the corresponding column. The controls on the side adjust board size and speed of the visualization. There are also buttons for running the visualization, taking a single step, and stopping.
Notes ¶
- For example implementations of this algorithm in C++, refer to this GitHub repo.
- While the algorithm described and visualized above is designed to find all solutions to the -queens problem for any , it is not the most efficient if we only seek to find one solution. In this case, we can turn to a closed-form solution, such as the one described in the paper Explicit solutions to the N-queens problem for all N and implemented here.