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[0] || 8).to_i).solve!.to_s

Output

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

Notes

No attempt to break the involved symmetries is made here.