```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).  I've
added comments and a bit of polish to his cleanup, so here's the new and
improved version of Amb along with another puzzle (just for fun).

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

# Copyright 2006 by Jim Weirich (jim / weirichhouse.org).  All rights
reserved.
# Permission is granted for use, modification and distribution as
# long as the above copyright notice is included.

# Amb is an ambiguous choice maker.  You can ask an Amb object to
# select from a discrete list of choices, and then specify a set of
# constraints on those choices.  After the constraints have been
# specified, you are guaranteed that the choices made earlier by amb
# will obey the constraints.
#
# For example, consider the following code:
#
#   amb = Amb.new
#   x = amb.choose(1,2,3,4)
#
# At this point, amb may have chosen any of the four numbers (1
# through 4) to be assigned to x.  But, now we can assert some
# conditions:
#
#   amb.assert (x % 2) == 0
#
# This asserts that x must be even, so we know that the choice made by
# amb will be either 2 or 4.  Next we assert:
#
#   amb.assert x >= 3
#
# This further constrains our choice to 4.
#
#   puts x    # prints '4'
#
# Amb works by saving a contination at each choice point and
# backtracking to previousl choices if the contraints are not
# satisfied.  In actual terms, the choice reconsidered and all the
# code following the choice is re-run after failed assertion.
#
# You can print out all the solutions by printing the solution and
# then explicitly failing to force another choice.  For example:
#
#   amb = Amb.new
#   x = Amb.choose(*(1..10))
#   y = Amb.choose(*(1..10))
#   amb.assert x + y == 15
#
#   puts "x = #{x}, y = #{y}"
#
#   amb.failure
#
# The above code will print all the solutions to the equation x + y ==
# 15 where x and y are integers between 1 and 10.
#
# The Amb class has two convience functions, solve and solve_all for
# encapsulating the use of Amb.
#
# This example finds the first solution to a set of constraints:
#
#   Amb.solve do |amb|
#     x = amb.choose(1,2,3,4)
#     amb.assert (x % 2) == 0
#     puts x
#   end
#
# This example finds all the solutions to a set of constraints:
#
#   Amb.solve_all do |amb|
#     x = amb.choose(1,2,3,4)
#     amb.assert (x % 2) == 0
#     puts x
#   end
#
class Amb
class ExhaustedError < RuntimeError; end

# Initialize the ambiguity chooser.
def initialize
@back = [
lambda { fail ExhaustedError, "amb tree exhausted" }
]
end

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

# Unconditional failure of a constraint, causing the last choice to
# be retried.  This is equivalent to saying
# <code>assert(false)</tt>.
def failure
@back.pop.call
end

# Assert the given condition is true.  If the condition is false,
# cause a failure and retry the last choice.
def assert(cond)
failure unless cond
end

# Report the given failure message.  This is called by solve in the
# event that no solutions are found, and by +solve_all+ when no more
# solutions are to be found.  Report will simply display the message
# to standard output, but you may override this method in a derived
# class if you need different behavior.
def report(failure_message)
puts failure_message
end

# Class convenience method to search for the first solution to the
# constraints.
def Amb.solve(failure_message="No Solution")
amb = self.new
yield(amb)
rescue Amb::ExhaustedError => ex
amb.report(failure_message)
end

# Class convenience method to search for all the solutions to the
# constraints.
def Amb.solve_all(failure_message="No More Solutions")
amb = self.new
yield(amb)
amb.failure
rescue Amb::ExhaustedError => ex
amb.report(failure_message)
end
end
-- END AMB
---------------------------------------------------------------

And a new puzzle to go along with the new version of Amb:

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

# Two thieves have being working together for years. Nobody knows
# their identities, but one is known to be a Liar and the other a
# Knave. The local sheriff gets a tip that the bandits are about to
# commit another crime. When the sheriff arrives at the seen of the
# crime, he finds three men, A, B, and C. C has been stabbed with a
# dagger. He cries out, "A stabbed me" before anybody can say anything
# else; then, he falls down dead from the stabbing.
#
# Not sure which of the three men are the crooks, the sheriff takes
# the two suspects to the jail and interrogates them. He gets the
# following information.
#
# A's statements:
# 1. B is one of the crooks.
# 2. B?s second statement is true.
# 3. C was telling the truth.
#
# B's statements:
# 1. A killed the other guy.
# 2. C was killed by one of the thieves.
# 3. C?s next statement would have been a lie.
#
# C's statement:
# 1. A stabbed me.
#
# The sheriff knows that the murderer is among these three people. Who
# should the sheriff arrest for killing C?
#
# NOTE: Liars always lie, knights always tell the truth and knaves
# strictly alternate between truth and lies.

require 'amb'

# Some helper methods for logic
class Object
def implies(bool)
self ? bool : true
end
def xor(bool)
self ? !bool : bool
end
end

# True if the given list of boolean values alternate between true and
# false.
def alternating(*bools)
expected = bools.first
bools.each do |item|
if item != expected
return false
end
expected = !expected
end
true
end

# A person class to keep track of the information about a single
# person in our puzzle.
class Person
attr_accessor :statements

def initialize(amb, name)
@name = name
@type = amb.choose(:liar, :knave, :knight)
@murderer = amb.choose(true, false)
@thief = amb.choose(true, false)
@statements = []
end

def to_s
"#{name} is a #{type} " +
(thief ? "and a thief." : "but not a thief.") +
(murderer ? "  He is also the murderer." : "")
end
end

# Some lists used to do collective assertions.
people = Array.new(3)
thieves = Array.new(2)

# Find all the solutions.

Amb.solve_all do |amb|
count = 0

# Create the three people in our puzzle.

a = Person.new(amb, "A")
b = Person.new(amb, "B")
c = Person.new(amb, "C")
people = [a, b, c]

# Basic assertions about the thieves.

thieves = people.select { |p| p.thief }
amb.assert thieves.size == 2  # Only two thieves
amb.assert thieves.collect { |p| # One is a knave, the other a liar
p.type.to_s
}.sort == ["knave", "liar"]

# Basic assertions about the murderer.

amb.assert people.select { |p| # There is only one murderer
p.murderer
}.size == 1
murderer = people.find { |p| p.murderer }
amb.assert ! c.murderer       # No suicides

# Create the logic statements of each of the people involved.  Note
# we are just creating them here.  We won't assert the truth of them
# until a bit later.

c1 = a.murderer               # A stabbed me
c2 = case c.type              # (hypothetical next statement)
when :knight
false
when :liar
true
when :knave
!c1
end
c.statements = [c1, c2]

b1 = a.murderer               # A killed the other guy
b2 = murderer.thief           # C was killed by one of the thieves
b3 = ! c2                     # C's next statement would have been
true
b.statements = [b1, b2, b3]

a1 = b.thief                  # B is one of the crooks
a2 = b2                       # B's second statement is true
a3 = c1                       # C was telling the truth.
a.statements = [a1, a2, a3]

# Now we make assertions on the truthfulness of each of persons
# statements based on whether they are a Knight, a Knave or a Liar.

people.each do |p|
amb.assert(
(p.type == :knight).implies(
p.statements.all? { |s| s }
))

amb.assert(
(p.type == :liar).implies(
p.statements.all? { |s| !s }
))

amb.assert(
(p.type == :knave).implies(
alternating(*p.statements)
))
end

# Now we print out the solution.

count += 1
puts "Solution #{count}:"
people.each do |p| puts p end
puts
end
-- END PUZZLE
-------------------------------------------------------------

-- Jim Weirich

--
Posted via http://www.ruby-forum.com/.

```