James Gray
3/13/2006 10:13:00 PM
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