4.3.2 Examples of Nondeterministic Programs

Section 4.3.3 describes the implementation of the amb evaluator.

First, however, we give some examples of how it can be used. The advantage of

nondeterministic programming is that we can suppress the details of how search

is carried out, thereby expressing our programs at a higher level of

abstraction.

Subheading: Logic Puzzles

4.3.3 节描述了 amb 求值器的实现。在此之前，我们先给出若干关于它如何使用的示例。非确定性程序设计的优势在于，我们可以屏蔽搜索如何进行的细节，从而在更高的抽象层次上表达程序。

小节标题：逻辑谜题

The following puzzle (taken from Dinesman 1968) is typical of a large class of

simple logic puzzles:

下面这道谜题（取自 Dinesman 1968）是一大类简单逻辑谜题的典型代表：

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an

apartment house that contains only five floors. Baker does not live on the top

floor. Cooper does not live on the bottom floor. Fletcher does not live on

either the top or the bottom floor. Miller lives on a higher floor than does

Cooper. Smith does not live on a floor adjacent to Fletcher’s. Fletcher does

not live on a floor adjacent to Cooper’s. Where does everyone live?

Baker、Cooper、Fletcher、Miller 和 Smith 住在一栋只有五层楼的公寓楼里，每人住在不同楼层。Baker 不住顶层。Cooper 不住底层。Fletcher 既不住顶层也不住底层。Miller 住的楼层比 Cooper 高。Smith 不住与 Fletcher 相邻的楼层。Fletcher 不住与 Cooper 相邻的楼层。每人各住哪一层？

We can determine who lives on each floor in a straightforward way by

enumerating all the possibilities and imposing the given

restrictions:

我们可以通过枚举所有可能性并施加给定约束的方式，直接确定每人所住的楼层：

Evaluating the expression (multiple-dwelling) produces the result

对表达式 (multiple-dwelling) 求值，得到如下结果

Although this simple procedure works, it is very slow. Exercise 4.39 and

Exercise 4.40 discuss some possible improvements.

尽管这个简单的过程能够正确工作，但它非常缓慢。练习 4.39 和练习 4.40 讨论了若干可能的改进方案。