Eight queens

The eight queens applet that solves the task using simple recursion. Turn delay on to see the process of solution.
The Eight queens puzzle is a well known puzzle where the player must place eight queens on a standard chessboard so that none of the queens have the ability to take any other queen, by its' standard moves (up and down, side to side, and diagonally).

There are in total 92 solutions to this problem, not many in comparison to 16,777,216 possible combinations. Hence, it cannot be solved by enumerating queen positions with brute force.

The task can be easily solved using a recursive search, like the applet at the right of the page. Queens are placed from left to right, one per column. Two queens cannot share the column as they would be able to take each other. Every new queen is placed on its column at random, but so that it does not break existing partial solution. If it is not possible to place a queen in any of the eight possible rows, moves are taken back in reverse order than they were made, removing the previously placed queens till it is possible to go some alternative way.

The applet actually places every new queen at the top of the next column, not at random. It starts from the top row and moves down till either the partial solution is valid or the bottom row has already been reached; this doesn't affect the algorithm's correctness very much.

While this solution works, mathematicians have proposed many even more efficient methods[1].

Variations on the problem use different chess pieces and boards of variable size (the n-queens problem). When the size of the board edge is two or three, no solution exist.

Acknowledgements

  • Java applet by Eli Bildirici with minor post modifications, GPL.

References

  1. 1 Wikipedia article on Eight queens task