The N-Queens problem is a classic example for a constraint satisfaction problem: given a chessboard of size NxN, place N queens on the board such that none of them can hit any other in one move.

There are 12 distinct solutions for the 8-queens problem - two solutions are not distinct if you can obtain one from another by rotating or flipping the chessboard. Clearly, there are no solutions for the 2-queens and 3-queens problems.

There’s a nice on-line N-Queens demo at http://kaminari.scitec.kobe-u.ac.jp/PrologCafe/Queens.html, where you can set N and let a Java applet find the solutions for you.

At the time of writing, Google returns about 12,000 hits when searching for ‘n-queens’, and there are dozens – if not more - of methods and algorithms for finding solutions.

Sources:

• http://www.math.utah.edu/~alfeld/queens/queens.html

Heres one neat way to express the N-queen problem. Simple math shows that if two queens can attack each other, one of the following must apply:

• They must be on the same column.
• They must be on the same row.
• The sum of the row and column must be the same for both( \ diagonal).
• The difference of the row and column must be the same for both ( / diagonal).

It can be thought of as a simultaneous equation with 2N unknowns.

Find integers x1 ... xn and y1 ... yn in the range 1 .. n such that :

Given integers A and B in the range 1..n and A ≠ B

• xA ≠ xB ( No two queens on same column )
• yA ≠ yB ( No two queens on same row )

For all combinations of integers A and B in the range 1..n and A ≠ B

• (xA + yA) ≠ (xB + yB) (No two queens on \ diagonal)
• (xA - yA) ≠ (xB - yB) (No two queens on / diagonal)

Log in or register to write something here or to contact authors.