Study the code for the nondeterministic interpreter discussed in class.
Add a (reset) primitive function to the interpreter's initial environment that aborts any computation in progress and also abandons any nondeterministic choices that are pending. (Hint: this is a one-liner.) For example:
==> (choose 1 2 3) 1 ==> (choose 'apple 'banana) apple ==> (try-again) banana ==> (try-again) 2 ==> (try-again) 3 ==> (try-again) "no more choices" ==> (choose 1 2 3) 1 ==> (choose 'apple 'banana) apple ==> (try-again) banana ==> (100 + (3 * (reset))) ok ==> (try-again) "no more choices" ==>
Implement require as a primitive function in the interpreter's initial environment. This way, we won't have to define it every time we need to use it in a nondeterministic program.
If we omit the requirement that Smith and Fletcher do not live on adjacent floors in the multiple-dwellings puzzle, how many solutions are there? Include your answer in a comment at the top of your interpreter file.
Write a nondeterministic Scheme program (using define-choose.ss) called liars.ss to solve the following logic puzzle. Try to write the program so that it runs as efficiently as possible.
Five schoolgirls sat for an examination. Their parents--so they
thought--showed an undue degree of interest in the result. They therefore
agreed that, in writing home about the examination, each girl should make
one true statement and one untrue one. The following are the relevant
passages from their letters:
Betty: "Kitty was second in the examination. I was only third."
Ethel: "You'll be glad to hear that I was on top. Joan was second."
Joan: "I was third, and poor old Ethel was bottom."
Kitty: "I came out second. Mary was only fourth."
Mary: "I was fourth. Top place was taken by Betty."
What in fact was the order in which the five girls were placed?
Write a nondeterministic Scheme program (using define-choose.ss) called yachts.ss to solve the following logic puzzle. Try to write the program so that it runs as efficiently as possible.
Mary Ann Moore's father has a yacht and so has each of his four friends: Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr. Parker. Each of the five also has one daughter and each has named his yacht after a daughter of one of the others. Sir Barnacle's yacht is the Gabrielle, Mr. Moore owns the Lorna; Mr. Hall the Rosalind. The Melissa, owned by Colonel Downing, is named after Sir Barnacle's daughter. Gabrielle's father owns the yacht that is named after Dr. Parker's daughter. Who is Lorna's father?
How many solutions are there if we do not know that Mary Ann's last name is Moore? Include your answer in a comment at the top of yachts.ss.
Implement a nondeterministic Scheme program (using define-choose.ss) to solve Sudoku puzzles.
Files to submit:
You don't need to submit the environment or parser code. If you have questions about anything, just ask!