# \[Quiz 70 Solution\] -- Using Amb

**URL:** <https://www.ruby-forum.com/t/quiz-70-solution-using-amb/80219>\
**Category:** Ruby\
**Created:** [March 13, 2006, 8:47am UTC](https://www.ruby-forum.com/t/quiz-70-solution-using-amb/80219 "2006-03-13T08:47:23Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![jimweirich](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/ce73a5/32.png) [@jimweirich](https://www.ruby-forum.com/u/jimweirich)\
**Post date:** [March 13, 2006, 8:47am UTC](https://www.ruby-forum.com/t/quiz-70-solution-using-amb/80219/1 "2006-03-13T08:47:23Z")

</div>

The Amb library is part of the continuations talk that Chad and I gave  
at last years Ruby conference. Amb is a library that allows you to  
choose from a number of possibilities, e.g.:

```
A = Amb.new
x = A.choose(1,2,3,4)
# at this point, x may be 1, 2, 3, or possibly 4

```

And then assert things that must be true about the choice:

```
A.assert (x % 2)
# at this point, x can only be 2 or 4.

```

If the assertion is not true, Amb will rewind the program back to the  
point of choosing, and make a different choice.

Here is the solution to part one of the quiz using the Amb library:

–BEGIN-----------------------------------------------------------  
require ‘amb’

A = Amb.new

begin  
a = A.choose(_(0…4))  
b = A.choose(_(0…4))  
c = A.choose(\*(0…4))

A.assert a \< b  
A.assert a + b == c

puts “a=#{a}, b=#{b}, c=#{c}”

A.failure

rescue Amb::ExhaustedError  
puts “No More Solutions”  
end  
–END-------------------------------------------------------------

Here’s the output of the solution:

$ ruby quiz70.rb  
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  
No More Solutions

The magic square solution is a bit more involved for two reasons. (1) I  
created a magic square object that allowed me to express the constraints  
easily, and the class turned out to be a bit wordy. (2) In order to  
reduced the number of states searched for a solution, it is necessary to  
assert constraints about the magic square as early as possible. For  
example, we assert that a new number is unique as soon as we add it to  
the square, rather than building the entire square and asserted that all  
members are unique. This greatly reduced the number of possibilities  
that needed to be tested and allowed the program to finish quite  
quickly.

Here is the magic square solution:

–BEGIN------------------------------------------------------  
#!/usr/bin/env ruby

# Ruby Q. # 70 – Constraint Solving

# Copyright 2006 by Jim W.

# 

# Again, using Amb to solve the magic square constraint problem. The

# key to getting this to run half-way efficiently is to do the

# assertions as soon as possible, before additional choices have been

# made. This minimizes the amount of backtracking needed.

# 

# See the following for details about Amb:

# 

[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node\_chap\_14](http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14)

require ‘amb’

# A Magic Square class, mostly to get convenient column/row/diagonal

# summations and detecting previously used values.

# 

class MagicSquare  
def initialize(side)  
@side = side  
@values = Array.new(side\*\*2) { 0 }  
end

# Access square value

def [](col, row)  
@values[col + @side\*row]  
end

# Set square value

def []=(col, row, value)  
@values[index(col, row)] = value  
end

# Calculate the sum of value along row +row+.

def row\_sum(row)  
(0…SIDE).inject(0) { |sum, col| sum + self[col,row] }  
end

# Calculate the sum of values in column +col+.

def col\_sum(col)  
(0…SIDE).inject(0) { |sum, row| sum + self[col,row] }  
end

# Calculate the sum of values along the major diagonal (i.e. r ==

# c).

def diagonal\_sum  
(0…SIDE).inject(0) { |sum, i| sum + self[i,i] }  
end

# Calculate the sum of values along the other diagnol (i.e. r ==

# SIDE-c-1).

def other\_diagonal\_sum  
(0…SIDE).inject(0) { |sum, i| sum + self[i,SIDE-i-1] }  
end

# Has this value been previously used in the square in any previous

# row, or any previous column of the current row?

def previously\_used?(col, row, value)  
(0…index(col, row)).any? { |i| @values[i] == value }  
end

# Convert to string for display.

def to\_s  
(0…SIDE).collect { |r|  
(0…SIDE).collect { |c| self[c,r] }.join(’ ')  
}.join(“\n”)  
end

private

def index(col, row)  
col + @side\*row  
end  
end

SIDE = 3  
MAX = SIDE\*\*2  
SUM = (MAX\*(MAX+1))/(2\*SIDE)

A = Amb.new  
square = MagicSquare.new(SIDE)

# Build up the square position by position. To minimize backtracking,

# assert everything you know about a position as early as possible.

count = 0

begin  
(0…SIDE).each do |r|  
(0…SIDE).each do |c|  
value = A.choose(\*(1…MAX))  
A.assert ! square.previously\_used?(c, r, value)  
square[c,r] = value  
A.assert( (r \< SIDE-1) || square.col\_sum(c) == SUM)  
end  
A.assert square.row\_sum(r) == SUM  
end  
A.assert square.diagonal\_sum == SUM  
A.assert square.other\_diagonal\_sum == SUM

count += 1  
puts “SOLUTION #{count}:”  
puts square

# Explicitly force a failure and make the program search for another

# solution.

A.failure

rescue Amb::ExhaustedError  
puts “No More Solutions”  
end  
–END--------------------------------------------------------

And the output of the magic squares program:

$ ruby magic\_square.rb  
SOLUTION 1:  
2 7 6  
9 5 1  
4 3 8  
SOLUTION 2:  
2 9 4  
7 5 3  
6 1 8  
SOLUTION 3:  
4 3 8  
9 5 1  
2 7 6  
SOLUTION 4:  
4 9 2  
3 5 7  
8 1 6  
SOLUTION 5:  
6 1 8  
7 5 3  
2 9 4  
SOLUTION 6:  
6 7 2  
1 5 9  
8 3 4  
SOLUTION 7:  
8 1 6  
3 5 7  
4 9 2  
SOLUTION 8:  
8 3 4  
1 5 9  
6 7 2  
No More Solutions

Finally, we get to the Amb library. It is a direct Ruby port of the  
Scheme amb function described in Teach yourself Scheme in fixnum days.  
In brief, Amb saves a continuation whenever a choice has to be made.  
Whenever an Amb assertion fails, the last choice is redone with a  
different result by invoking the latest continuation. If all choices  
are used up, then we go to the previous choice and undo retry it.

If you want a more indepth description of Amb, see  
[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node\_chap\_14](http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14)

Here is the amb.rb library:

–BEGIN (amb.rb) ------------------------------------------------  
class Amb  
class ExhaustedError \< RuntimeError; end

def initialize  
@fail = proc { fail ExhaustedError, “amb tree exhausted” }  
end

def choose(\*choices)  
prev\_fail = @fail  
callcc { |sk|  
choices.each { |choice|  
callcc { |fk|  
@fail = proc {  
@fail = prev\_fail  
fk.call(:fail)  
}  
if choice.respond\_to? :call  
sk.call(choice.call)  
else  
sk.call(choice)  
end  
}  
}  
@fail.call  
}  
end

def failure  
choose  
end

def assert(cond)  
failure unless cond  
end  
end  
–END------------------------------------------------------------

–  
– Jim W.

---

<div class="post-metadata">

**Author:** ![jimweirich](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/ce73a5/32.png) [@jimweirich](https://www.ruby-forum.com/u/jimweirich)\
**Post date:** [March 13, 2006, 9:05am UTC](https://www.ruby-forum.com/t/quiz-70-solution-using-amb/80219/2 "2006-03-13T09:05:48Z")

</div>

Oops, typo!

Jim W. wrote:  
[…]

> And then assert things that must be true about the choice:
> 
> ```
> A.assert (x % 2)
> # at this point, x can only be 2 or 4.
> 
> ```

The assertion should read:

```
A.assert (x % 2) == 0

```

Sorry.

–  
– Jim W.