Forum: Ruby [Quiz 70 Solution] -- Using Amb

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Jim W. (Guest)
on 2006-03-13 09:47
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-s...

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-s...

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.
Jim W. (Guest)
on 2006-03-13 10:05
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.
This topic is locked and can not be replied to.