Sudoku with Sets

  1 require 'rubygems'
  2 require 'gecoder'
  3 require 'enumerator'
  4 
  5 # Solves the sudoku problem using sets. The model used is a fairly direct 
  6 # translation of the corresponding Gecode example: 
  7 # http://www.gecode.org/gecode-doc-latest/sudoku-set_8cc-source.html .
  8 class SudokuSet
  9   include Gecode::Mixin
 10 
 11   # Takes a 9x9 matrix of values in the initial sudoku, 0 if the square is 
 12   # empty. 
 13   def initialize(predefined_values)
 14     # Verify that the input is of a valid size.
 15     @size = n = predefined_values.row_size
 16     block_size = Math.sqrt(n).round
 17     unless predefined_values.square? and block_size**2 == n
 18       raise ArgumentError, 'Incorrect value matrix size.'
 19     end
 20     sub_count = block_size
 21     
 22     # Create one set per assignable number (i.e. 1..9). Each set contains the 
 23     # position of all squares that the number is located in. The squares are 
 24     # given numbers from 1 to 81. Each set therefore has an empty lower bound 
 25     # (since we have no guarantees where a number will end up) and 1..81 as 
 26     # upper bound (as it may potentially occurr in any square). We know that
 27     # each assignable number must occurr 9 times in a solved sudoku, so we 
 28     # set the cardinality to 9..9 .
 29     sets_is_an set_var_array(n, [], 1..n*n, n..n)
 30     predefined_values.row_size.times do |i|
 31       predefined_values.column_size.times do |j|
 32         unless predefined_values[i,j].zero?
 33           # We add the constraint that the square position must occurr in the 
 34           # set corresponding to the predefined value.
 35           sets[predefined_values[i,j] - 1].must_be.superset_of [i*n + j+1]
 36         end
 37       end
 38     end
 39 
 40     # Build arrays containing the square positions of each row and column.
 41     rows = []
 42     columns = []
 43     n.times do |i|
 44       rows << ((i*n + 1)..(i*n + n))
 45       columns << (0...n).map{ |e| e*n + 1 + i }
 46     end
 47     
 48     # Build arrays containing the square positions of each block.
 49     blocks = []
 50     # The square numbers of the first block.
 51     first_block = (0...block_size).map do |e| 
 52       ((n*e+1)..(n*e+block_size)).to_a 
 53     end.flatten
 54     block_size.times do |i|
 55       block_size.times do |j| 
 56         blocks << first_block.map{ |e| e + (j*n*block_size)+(i*block_size) }
 57       end
 58     end
 59 
 60     # All sets must be pairwise disjoint since two numbers can't be assigned to
 61     # the same square.
 62     n.times do |i|
 63       (i + 1).upto(n - 1) do |j|
 64         sets[i].must_be.disjoint_with sets[j]
 65       end
 66     end
 67 
 68     # The sets must intersect in exactly one element with each row column and
 69     # block. I.e. an assignable number must be assigned exactly once in each
 70     # row, column and block. 
 71     sets.each do |set|
 72       rows.each do |row|
 73         set.intersection(row).size.must == 1
 74       end
 75       columns.each do |column|
 76         set.intersection(column).size.must == 1
 77       end
 78       blocks.each do |block|
 79         set.intersection(block).size.must == 1
 80       end
 81     end
 82 
 83     # Branching.
 84     branch_on sets, :variable => :none, :value => :min
 85   end
 86   
 87   # Outputs the assigned numbers in a grid.
 88   def to_s
 89     squares = []
 90     sets.values.each_with_index do |positions, i|
 91       positions.each{ |square_position| squares[square_position - 1] = i + 1 }
 92     end
 93     squares.enum_slice(@size).map{ |slice| slice.join(' ') }.join("\n")
 94   end
 95 end
 96 
 97 predefined_squares = Matrix[
 98   [0,0,0, 2,0,5, 0,0,0],
 99   [0,9,0, 0,0,0, 7,3,0],
100   [0,0,2, 0,0,9, 0,6,0],
101     
102   [2,0,0, 0,0,0, 4,0,9],
103   [0,0,0, 0,7,0, 0,0,0],
104   [6,0,9, 0,0,0, 0,0,1],
105       
106   [0,8,0, 4,0,0, 1,0,0],
107   [0,6,3, 0,0,0, 0,8,0],
108   [0,0,0, 6,0,8, 0,0,0]]
109 puts SudokuSet.new(predefined_squares).solve!.to_s