# N-queens

## Problem

The eight queens puzzle is 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. – Wikipedia

Replace “8” with “n” to get the n-queens puzzle.

## Code

``` 1 require 'rubygems'
2 require 'gecoder'
3
4 # Solves the n-queens problem: http://en.wikipedia.org/wiki/Nqueens . No attempt
5 # to break the involved symmetries is made.
6 class NQueens
7   include Gecode::Mixin
8
9   def initialize(n)
10     @size = n
11
12     # The row number that the queen in the i:th column has. By using this as
13     # our variables we already make sure that no two queens are in the same
14     # column.
15     queen_rows_is_an int_var_array(n, 0...n)
16
17     # Set up the constraints
18     # Queens must not be in the same diagonal (negative slope).
19     queen_rows.must_be.distinct(:offsets => (0...n).to_a)
20     # Queens must not be in the same diagonal (positive slope).
21     queen_rows.must_be.distinct(:offsets => (0...n).to_a.reverse)
22     # Queens must not be in the same row.
23     queen_rows.must_be.distinct
24
25     # Branching, we use first-fail heuristic.
26     branch_on queen_rows, :variable => :smallest_size, :value => :min
27   end
28
29   # Displays the assignment as a chessboard with queens denoted by 'x'.
30   def to_s
31     rows = queen_rows.values
32
33     separator = '+' << '-' * (3 * @size + (@size - 1)) << "+\n"
34     res = (0...@size).inject(separator) do |s, i|
35       (0...@size).inject(s + '|') do |s, j|
36         s << " #{rows[j] == i ? 'x' : ' '} |"
37       end << "\n" << separator
38     end
39   end
40 end
41
42 # Print the first solution. Note that there are 92 solutions, but only 12
43 # are rotationally distinct. For any serious use one should place additional
44 # constraints to eliminate those symmetries.
45 puts NQueens.new((ARGV || 8).to_i).solve!.to_s
```

### Output

```+-------------------------------+
| x |   |   |   |   |   |   |   |
+-------------------------------+
|   |   |   |   |   |   | x |   |
+-------------------------------+
|   |   |   |   | x |   |   |   |
+-------------------------------+
|   |   |   |   |   |   |   | x |
+-------------------------------+
|   | x |   |   |   |   |   |   |
+-------------------------------+
|   |   |   | x |   |   |   |   |
+-------------------------------+
|   |   |   |   |   | x |   |   |
+-------------------------------+
|   |   | x |   |   |   |   |   |
+-------------------------------+
```

No attempt to break the involved symmetries is made here.