[QUIZ] Constraint Processing (#70)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Jay Anderson

For this quiz the goal is to make a constraint processing library for ruby. A
Constraint Satisfaction Problem consists of variables, domains for each
variable, and constraints among the variables. Here's a sample (Solutions DO NOT
need to follow this syntax, this is just an example):

a = IntVar.newa, (0..4).to_a) #Set up the variables and their domains.
b = IntVar.newb, (0..4).to_a)
c = IntVar.newc, (0..4).to_a)
con1 = a < b #Create constraints on the problem.
con2 = a + b == c
prob = Problem.new(con1, con2) #Create a problem with the constraints
solution = prob.solve #Find a solution
p solution

There are many solutions. It could return any (or all) of the following:

{:a => 0, :b => 1, :c => 1}
{:a => 0, :b => 2, :c => 2}
{:a => 0, :b => 3, :c => 3}
{:a => 0, :b => 4, :c => 4}
{:a => 1, :b => 2, :c => 3}
{:a => 1, :b => 3, :c => 4}

Another example would be to solve the magic square:

SIDE = 3
MAX = SIDE**2
SUM = (MAX*(MAX+1))/(2*SIDE)
square = Array.new(SIDE) do |x|
Array.new(SIDE) {|y| IntVar.new("#{x},#{y}", (1..MAX).to_a ) }
end
cons = []
zero = IntVar.newzero, [0])
SIDE.times do |row|
ÊÊÊ sum = zero
ÊÊÊ SIDE.times {|col| sum += square[col][row] }
ÊÊÊ cons << sum == SUM
end
SIDE.times do |col|
ÊÊÊ sum = zero
ÊÊÊ SIDE.times {|row| sum += square[col][row] }
ÊÊÊ cons << sum == SUM
end
#A constraint to ensure no two variables have the same value in a solution.
cons << AllDistinct.new(*square.flatten)
prob = Problem.new(*cons)
solution = prob.solve
p solution

There are many problems that can be solved through constraint programming (even
some past quizzes): gift exchanges, sudoku, magic squares, N queens,
cryptoarithmetics, scheduling problems, etc... So be creative here. Pick a
simple problem to solve with your Constraint Programming Engine.

Good luck!

For more information see:

http://ktiml.mff.cuni.cz/~bartak/constraints/

and:

http://en.wikipedia.org/wiki/Constraint_programming

 

[James Edward Gray II]

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

 

[Dave Burt]

Hi,

Thanks for another quiz. I read it and thought "that looks difficult and
ugly", but I had a little spare time, and, to my own surprise, was able to
solve it rather quickly.

My naive solution just makes big nested loops over the domains of all the
variables, so it's not going to solve a sudoku this century, but you
wouldn't have to change the constraint code to speed it up - the engine can
be fixed keeping the same interface.

The interface is DSP-ish and blocky as seems to be the fashion in Ruby these
days.

Here's N-Queens (n=4 so it works with my naive constraint processor):
http://www.dave.burt.id.au/ruby/constraints/nqueens.rb

And here's the thing itself:
http://www.dave.burt.id.au/ruby/constraints/constraint_processor.rb

Cheers,
Dave

 

[Chris Parker]

Hi

Here is my CSP language. I have actually been doing this for a class,
so I got an extra week to work on it. As test cases, I have been
modeling typical CSP problems so right now, I can do cryptarthemtic,
sudoku, mastermind, map coloring, and the zebra problem.

I use forward checking with the MRV heuristic and the variable with the
most constraints heuristic for tie breaking. I have also been working
on a domain specific language that uses my CSP library. Some of the
test cases use the language and some of them use the library.

The language uses generic variables and requires user defined domain
constricting functions for non-trival constraints.

I would love some feedback on what I have done so far, including the
syntax of the domain language and methods for the library. I plan to
put the library on RubyForge at the end of the class.

Here is the link to the files needed to try it out:
http://reducto.case.edu/projects/team2/attachment/wiki/FileDump/CSP.zip?format=raw

Chris Parker

 

[James Edward Gray II]

I've been having a lot of fun with this quiz. Pit Capitain sent me a
improved version of Amb that is more "Rubyish" and much easier to read
(my original was a direct translation of the scheme version).

Oh sure, you would do that after I summarized the trickier version.

# Make a choice amoung a set of discrete values.
def choose(*choices)
choices.each { |choice|
callcc { |fk|
@back << fk
return choice
}
}
failure
end

I tried to eliminate the outer continuation when I was summarizing,
convinced it wasn't needed. My attempt wasn't successful though. :
( It's good to know I wasn't completely wrong.

James Edward Gray II

 

[James Edward Gray II]

Here is my CSP language. I have actually been doing this for a class,
so I got an extra week to work on it.

This is a great glimpse at a more robust solution. Thanks for
sending it in!

As test cases, I have been
modeling typical CSP problems so right now, I can do cryptarthemtic,
sudoku, mastermind, map coloring, and the zebra problem.

Ooo, I liked the Mastermind example. We need to do that as a Ruby
Quiz at some point...

James Edward Gray II

 

[Jim Weirich]

Oh sure, you would do that after I summarized the trickier version.


I tried to eliminate the outer continuation when I was summarizing,
convinced it wasn't needed. My attempt wasn't successful though. :
( It's good to know I wasn't completely wrong.

Yes, the new version is SO much easier on the eyes. Eliminating the
extra continuation not only makes it easier to read, but a bit faster as
well. The other simplification is that the original version supported
delayed choices, i.e. passing in a lambda as a choice where that lambda
wouldn't get evaluated until the choice was needed. Although a cool
idea, I don't think I ever used it in any of the puzzles. So, it was
extra baggage that wasn't really needed.