The N-queens puzzle is the problem of placing N chess queens on an N×N chessboard so that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. Solutions exist only for n = 1 or n ≥ 4.
The puzzle is solved as a CSP problem, using backtracking search. Forward checking is used to limit the size of the search space. The next unassigned variable and ordering of domain values are selected at random.
./nqueens.rb <N>
where N is the number of queens to place on a NxN chessboard
----------------------------------------------------------------------
Solving the 8-queens problem...
----------------------------------------------------------------------
----------------------------------------------------------------------
Solution: {0=>4, 5=>2, 3=>5, 6=>0, 7=>6, 4=>7, 1=>1, 2=>3}
Found a solution in 0.0 seconds
----------------------------------------------------------------------
0 0 0 0 0 0 X 0
0 X 0 0 0 0 0 0
0 0 0 0 0 X 0 0
0 0 X 0 0 0 0 0
X 0 0 0 0 0 0 0
0 0 0 X 0 0 0 0
0 0 0 0 0 0 0 X
0 0 0 0 X 0 0 0