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.
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
+-------------------------------+ | x | | | | | | | | +-------------------------------+ | | | | | | | x | | +-------------------------------+ | | | | | x | | | | +-------------------------------+ | | | | | | | | x | +-------------------------------+ | | x | | | | | | | +-------------------------------+ | | | | x | | | | | +-------------------------------+ | | | | | | x | | | +-------------------------------+ | | | x | | | | | | +-------------------------------+
No attempt to break the involved symmetries is made here.