4.3.3 · Examples of nondeterministic programs

A puzzle states choices and constraints; failure resumes the next choice.

Use explicit success and failure continuations to solve the multiple-dwelling puzzle and enumerate finite Pythagorean triples.

Guiding question

How can the program describe valid answers while the continuation protocol owns the order of alternatives and backtracking?

Choose one value while retaining the remaining alternatives in a failure continuation
Reject a partial or complete assignment by invoking the current failure continuation
Express all-different and adjacency constraints independently from enumeration control
Collect every finite solution by resuming after success
Reuse the same choose protocol for a numeric search problem
Keep finite depth-first enumeration distinct from fair infinite search

choose passes the first option to succeed and packages the remaining options as next-failure. Each nested dwelling choice therefore carries a continuation that can resume at exactly the nearest untried alternative. Once five floors are selected, the constraint predicate either reports one solution or invokes that continuation. The solver contains the puzzle facts; choose and collect-solutions contain the search protocol.

The Pythagorean program reuses the same continuations with numeric choices. Ordering constraints remove permutations and the square equality accepts two triples in the finite range 1 through 10. Both examples use depth-first finite lists and record every choice reached within that range.

SICP code2,098 of 1,048,576 UTF-8 bytes

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The dwelling search returns (((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))). The numeric search returns ((3 4 5) (6 8 10)).

Trace focus

Follow one choose call into its next-failure closure, then locate the constraint that rejects the current complete assignment and resumes the nearest alternative. On success, distinguish recording the solution from invoking next-alternative to continue enumeration. Compare the same protocol across symbolic floor assignments and numeric triples.

Try it yourself

Change the program and compare the result.

Add the yacht puzzle or a four-variable sum puzzle using the same choose function. Record how many complete candidates reach the final constraint before and after moving safe constraints earlier.

Show hint

A constraint may invoke the current failure continuation as soon as all values it needs are known. Earlier rejection changes work, not the answer set.

Complete this lesson

0 of 23 lessons complete in this chapter0%