N-queens

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
• http://www.nist.gov/dads/HTML/nqueens.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 x₁ ... x_n and y₁ ... y_n in the range 1 .. n such that :

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

• x_A ≠ x_B ( No two queens on same column )
• y_A ≠ y_B ( No two queens on same row )

 

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

• (x_A + y_A) ≠ (x_B + y_B) (No two queens on \ diagonal)
• (x_A - y_A) ≠ (x_B - y_B) (No two queens on / diagonal)