Eight Queens

Eight Queens: this simple game is based on one of the chess rules, demonstrating the behavior of the queen in the board, to win you have to find spots to move the queen 8 times.

The eight queens puzzle is based on the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The color of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard like the board below:

Finding all solutions to the eight queens puzzle is a good example of a simple but nontrivial problem. For this reason, it is often used as an example problem for various programming techniques, including nontraditional approaches such as constraint programming, logic programming or genetic algorithms. Most often, it is used as an example of a problem which can be solved with a recursive algorithm, by phrasing the n queens problem inductively in terms of adding a single queen to any solution to the n−1 queens problem. The induction bottoms out with the solution to the 0 queens problem, which is an empty chessboard.

Related words: Functional programming, Mathematical game, Backtracking.

© 2006 IQLOGY.com

iqlogy@gmail.com