From: James Edward Gray II <james@...>
Date: 2006-03-14T07:13:22+09:00
Subject: Re: [QUIZ] Constraint Processing (#70)

Here is my own solution to this week's Ruby Quiz.  I built a simple  
constraint library and used it to solve a sudoku puzzle.  First the  
library (constraint.rb):

#!/usr/local/bin/ruby -w

class Problem
   def initialize
     @vars    = Hash.new { |vars, name| vars[name] = Array.new }
     @rules   = Hash.new { |rules, var| rules[var] = Array.new }

     yield self if block_given?
   end

   def var( name, *choices )
     if choices.empty?
       values = @vars[name]
       values.size == 1 ? values.first : values
     else
       @vars[name].push(*choices)
     end
   end

   def rule( name, &test )
     @rules[name] << test
   end

   def solve
     loop do
       changed = false
       @vars.each do |name, choices|
         next if choices.size < 2

         failures = choices.select do |choice|
           @rules[name].any? { |rule| !rule[choice] }
         end
         unless failures.empty?
           @vars[name] -= failures
           changed = true
         end
       end

       break unless changed
     end

     self
   end
end

def problem( &init )
   Problem.new(&init).solve
end

__END__

And here is my sudoku solver (sudoku.rb), using that library:

#!/usr/local/bin/ruby -w

require "constraint"

# sudoku conveniences
indices = (0..8).to_a
boxes   = Hash.new
[(0..2), (3..5), (6..8)].each do |across|
   [(0..2), (3..5), (6..8)].each do |down|
     squares = across.map { |x| down.map { |y| "#{x}#{y}" } }.flatten
     squares.each { |square| boxes[square] = squares - [square] }
   end
end

solution = problem do |prob|
   # read puzzle, setting problem variables from data
   (ARGV.empty? ? DATA : ARGF).each_with_index do |line, y|
     line.split.each_with_index do |square, x|
       prob.var("#{x}#{y}", *(square =~ /\d/ ? [square.to_i] : (1..9)))
     end
   end

   # apply the rules of the game
   indices.each do |x|
     indices.each do |y|
       col = (indices - [y]).map { |c| "#{x}#{c}" }  # other cells in  
column
       row = (indices - [x]).map { |r| "#{r}#{y}" }  # other cells in  
row
       box = boxes["#{x}#{y}"]                       # other cells in  
box
       [col, row, box].each do |set|  # set rules requiring a cell to  
be unique
         prob.rule("#{x}#{y}") { |n| !set.map { |s| prob.var 
(s) }.include?(n) }
       end
     end
   end
end

# pretty print the results
puts "+#{'-------+' * 3}"
indices.each do |y|
   print "| "
   indices.each do |x|
     print "#{solution.var("#{x}#{y}").inspect} "
     print "| " if [2, 5].include? x
   end
   puts "|"
   puts "+#{'-------+' * 3}" if [2, 5, 8].include? y
end

__END__
7 _ 1 _ _ _ 3 _ 5
_ 8 _ 1 _ 5 _ 6 _
2 _ _ _ _ _ _ _ 9
_ _ 6 5 _ 1 2 _ _
_ 3 _ _ _ _ _ 1 _
_ _ 8 3 _ 4 9 _ _
9 _ _ _ _ _ _ _ 8
_ 2 _ 6 _ 9 _ 4 _
6 _ 5 _ _ _ 7 _ 1

Running that on the included puzzle produces the following output:

+-------+-------+-------+
| 7 6 1 | 9 4 2 | 3 8 5 |
| 3 8 9 | 1 7 5 | 4 6 2 |
| 2 5 4 | 8 6 3 | 1 7 9 |
+-------+-------+-------+
| 4 9 6 | 5 8 1 | 2 3 7 |
| 5 3 2 | 7 9 6 | 8 1 4 |
| 1 7 8 | 3 2 4 | 9 5 6 |
+-------+-------+-------+
| 9 1 3 | 4 5 7 | 6 2 8 |
| 8 2 7 | 6 1 9 | 5 4 3 |
| 6 4 5 | 2 3 8 | 7 9 1 |
+-------+-------+-------+

Thanks for the quiz, Jav.  I learned a lot!

James Edward Gray II