Assignment 9: Fun (and Games) with Prolog!
Due Sunday, April 5 by 11:59pm

Typically puzzles ask the user to satisfy a set of constraints -- and this is precisely what prolog was designed to do. In this assignment you will be using prolog to solve several different types of puzzles. The work involved is primarily in representing the puzzles and their rules. In order to help the graders, please check that you name your prolog rules (predicates) as they're specified in the assignment.

Feel free to use Prolog's built-in predicates in solving these puzzles. In particular, Prolog has a built-in length(L, N) which is true if and only if list L has length N. member( X, L ) is built-in to at least some versions of Prolog. You may use your removeOne from the previous assigment, or use this one:

removeOne(X,[X|R],R).
removeOne(X,[F|R],[F|S]) :- removeOne(X,R,S).

And certainly feel free to define your own helper rules as needed!

Submission    Please submit your problems in separate files named

• logicpuzzle.pl (for problem #1)
• twentyfour.pl (for problem #2)
• riverpuzzle.pl (for problem #3)
• parser.pl (for problem #4 and the first ex. cr.)
• paths.pl (for problem #5)
• puzzle.pl (for the second ex. cr.)

Part 1: Einstein's logic-constraint puzzles

[20 points, individual]

/*
 * algird, bruno, collette, dino, and edwina are each from different
 * one of five colleges: pomona, pitzer, hmc, cmc, and scripps.
 *
 * Each one brings a different snack:  jots, chocolate, donuts, pez, and spam.
 * They are all on the train together in seats 1 through 5.
 *
 * We want to know which student is in each seat, what college does each
 * student attend, what did each student bring for a snack?
 * Determine whether there is a solution, and if so, whether it is unique.
 *
 * 1.  bruno and dino sat in the end seats.
 * 2.  algird sat next to the student from hmc.
 * 3.  collette sat next to (i.e. between) friends with chocolate and donuts.
 * 4.  The hmc student brought spam as a snack and sat in the middle seat.
 * 5.  chocolate was immediately to the left of pez.
 * 6.  bruno, dino, and algird do not go to Scripps.
 * 7.  The pomona student sat between the person with jots and the person with spam.
 * 8.  dino did not sit next to the person with donuts.
 * 9.  The cmc student did not sit next to edwina.
 *
 * Note that negation constraints don't generate values -- they can
 * only check for consistency of already-instantiated values. Thus,
 * they must be tested _after_ variables are instantiated with values.
*/

Be sure to format your output in an easy-to-read manner. In addition, make sure that you leave a comment for the graders so that they know how to generate and print the solution to the puzzle. As an example, consider the solve predicate in the einstein.pl example. It first generates the solution to the Zebra puzzle, and then it prints the five houses in a reasonable fashion:

solve :-
  einstein( [ H1, H2, H3, H4, H5 ] ),
  write( ' first house: '), write(H1), nl,
  write( 'second house: '), write(H2), nl,
  write( ' third house: '), write(H3), nl,
  write( 'fourth house: '), write(H4), nl,
  write( ' fifth house: '), write(H5), nl.

?- solve.

 first house: [norwegian, cat, dunhill, water, yellow]
second house: [dane, horse, marlboro, tea, blue]
 third house: [brit, bird, pallmall, milk, red]
fourth house: [german, zebra, rothmans, coffee, green]
 fifth house: [swede, dog, winfield, beer, white]

Yes

Please submit this part of the assignment in a file called logicpuzzle.pl.

Part 2: The Game of 24!

[25 points, individual]

This problem asks you to use Prolog to provide a solver for a generalized version of the game "Twenty-Four". In the original game, players view a card with four numbers on it and try to make an arithmetic combination of the numbers using the operators +, -, *, / so that the result is 24 (parentheses are allowed but are implicit). Each number must be used exactly once. Each operator can be used any number of times.

In our generalization of the game, the fixed number 24 is replaced with a variable, the set of operators is specified in a list, and the list of numbers can have any length, not just 4. (By definition, no result can be made if the list is empty.)

Define a 4-ary predicate solve such that

     solve(Ops, Values, Result, Tree)
  

 solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree).

 Tree = [*,[+,[-,3,2],5],4] 
 

This means that we have found a solution Tree using operators +, *, and - such that the solution combines the numbers in the list [2, 3, 4, 5] to yield 24.

You may assume that the set of operators will always be a subset of ['+', '*', '-', '/'] and that '/' denotes integer division. In prolog, integer division is performed using // (which is why 1-line comments in prolog are prefaced by % and not //).

Here is an eval predicate (for evaluating trees of opreations) that will be helpful in solving this problem. You may copy this code and use it freely. Note that eval can handle numbers and it can handle trees that are bound to some value (using the nonvar predicate) Thus, the eval predicate can not generate trees. Allowing eval to generate trees can lead to infinite recursion, as it looks in the (unbounded) space of trees for operations possibly leading to R.

    eval(R, R) :- number(R).
    eval(['+', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR + BR.
    eval(['*', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR * BR.
    eval(['-', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR - BR.
    eval(['/', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), BR\==0, R is AR // BR.
 

Here are some other examples of solve in action. Warning: You may especially want to check the second of these. In particular, a common partially working solution to this problem handles the first example below, but not the second example. Note how the list of values is being split into sublists in the second case:

  solve(['+', '*', '-'], [1, 2, 3, 4], 24, Tree),

  Tree = [*,1,[*,2,[*,3,4]]]    % other solutions are certainly possible!




  solve(['+','-','*','/'], [2,8,22,424], 42, Tree).  % only one solution possible!

  Tree = [-,[/,424,8],[/,22,2]]



  solve(['+'], [1, 1, 1, 1], 24, Tree).   % no solution

  No.



  solve(['+'], [24], 24, Tree).    % base case

  Tree = 24
 

Warning!    Be careful for a situation that can lead to infinite recursion: if you split a list into two parts and one of those two parts is the same length as the original list, then a recursive call will not get closer to a base case (and is likely to continue forever!)

Please submit this part of the assignment in a file called twentyfour.pl.

Part 3: Man, Fox, Hare, Lettuce!

[25 points, pair or individual]

In this part of the assignment, you will write a Prolog program to solve the famous Man, Fox, Hare, Lettuce problem described in class. Please submit your solution in a file called riverpuzzle.pl.

You should carefully review the solution to the Towers of Hanoi problem that we developed in class. The big ideas in the two programs are very similar.

Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer at least one correct solution to the puzzle. It need not be the shortest solution, but it must be valid. Moreover, Prolog (in its "infinite" wisdom) may give you the same solution many times. That's just Prolog being Prolog and it's OK!

Here are the details:

• The Prolog rule that "starts things up" should be called solve. This rule should take two arguments, a list representing the initial configuration and a list representing the sequence of moves. solve should then infer whether or not this list of moves is a valid solution for solving the puzzle from the initial configuration.
• A configuration is a list with two elements: A list comprising the state of the left bank of the river and a list comprising the state of the right bank of the river. The initial configuration will be [[man, fox, hare, lettuce], []] indicating that all four parties are on the left bank initially and there is nothing currently on the right bank. The final goal configuration is [[], [man, fox, hare, lettuce]] indicating that everyone has made it safely to the right bank.
• Recall that in this puzzle, a configuration cannot have the fox and the hare on the same side of the river together without the man there to keep the hare safe. Similarly, the hare and the lettuce cannot be left without the man. Therefore, for example, the configuration [[fox, hare], [man, lettuce]] is not a valid configuration in this puzzle whereas [[fox, lettuce], [man, hare]] is valid.
• The list of moves is a list of zero or more atoms with the following names:
  • man_goes_left (the man goes in the canoe by himself from the right bank to the left bank).
  • man_goes_right (the man goes in the canoe by himself from the left bank to the right bank).
  • man_takes_fox_left (the man takes the fox from the right bank to the left bank).
  • man_takes_fox_right (the man takes the fox from the left bank to the right bank).
  • man_takes_hare_left (the man takes the hare from the right bank to the left bank).
  • man_takes_hare_right (the man takes the hare from the left bank to the right bank).
  • man_takes_lettuce_left (the man takes the lettuce from the right bank to the left bank).
  • man_takes_lettuce_right (the man takes the lettuce from the left bank to the right bank).

When your program is done, you will be able to run it like this:

?- solve([[man, fox, hare, lettuce], []], X).

X = [man_takes_hare_right, man_goes_left, man_takes_fox_right, 
     man_takes_hare_left, man_takes_lettuce_right, 
     man_goes_left, man_takes_hare_right]

Yes

• Your program should not produce a solution that revisits the same configuration twice! For example, if the solution begins by taking the man right, and then taking the man left, then the we are now back in the same configuration in which we started. Unfortunately, Prolog may be tempted to do this because it may not be able to distinguish between two configurations that LOOK different but, in fact, are the same in terms of their meaning. For example, the configuration [[man, fox, hare, lettuce], []] is structurally different from [[fox, man, hare, lettuce], []] although we can see that these are really the same. To get around this, we strongly suggest that you enforce that the contents of each configuration be kept "sorted" with respect to the food chain. That is, man comes before fox (although we are, happily, unaware of men eating foxes), fox comes before hare, and hare comes before lettuce. For example, this would allow [[man, fox, hare, lettuce], []] but disallow [[fox, man, hare, lettuce], []]. Similarly, the configuration [[fox, lettuce], [man, hare]] would be valid but the logically identical configuration [[lettuce, fox], [hare, man]] would not. You will need to encode constraints to ensure that a configuration must maintain this food chain ordering in order to be valid.
  
  
• You'll need to use dynamic and assert in much the same way that we did in the Towers of Hanoi problem that we saw in class.
  
  
• If you run your solve search twice, it might succeed the first time and fail the second time! Why? Recall that as we discussed in class, the asserted facts are still present the second time (that is, the configurations are still marked as visited!). The easiest way to get around this (without leaving Prolog) is to retract all of the dynamic assertions:

  
         | ?- retractall(marked(_)).
         yes
       

  Then, you should be able to run it again!.

Submit this problem under assignment #9 as riverpuzzle.pl.

Part 4: Grammars in Prolog

[20 points, pair or individual]

In Assignment 4 you wrote a recursive descent parser in Rex for a grammar for arithmetic expressions involving addition, multiplication, and exponentiation. In this assignment you will write a general "parse engine" in Prolog which will allow you to determine if a given string can be successfully parsed by virtually ANY grammar that you give it! Amazing, but true!

Here, the goal is not to determine a parse tree, but we DO want to know if there EXISTS a parse tree for a given string using the given grammar. For example, IF we had a grammar for the English language, we would be able to ask our parser if a particular sentence was valid in English. The neat thing is that we won't tell Prolog how to parse, we'll just tell it what a grammar is and what string we're interested in and ask: "Hey Prolog, can this string be parsed by the given grammar?"

Take a look at the files g0.pl,g1.pl, g2.pl, g3.pl and g4.pl supplied to you in /cs/cs60/hwfiles/a9. Each of these files specifies a different grammar. A grammar is specified by declaring the variables, terminals, and rules.

For example, consider the grammar for valid additions of 0's and 1's. (This is the grammar specified in the file g0.pl.)

s -> v + s | v
v -> 0 | 1 

You can see how this grammar is specified in file g0.pl Our convention is as follows: Variables are stated as facts. These facts simply state the names of the variables. In this example, the facts state that s and v are variables as shown below.

variable(s).
variable(v).

terminal(0).
terminal(1).
terminal(+).

Finally, the grammar rules are stated as ordered pairs, where the first element is the left-hand-side of a rule and the second argument is the LIST of elements appearing on the right-hand-side of that rule. For the grammar above, these rules are stated as shown below.

rule(s, [v, +, s]).
rule(s, [v]).
rule(v, [0]).
rule(v, [1]).

Your task is to write a general-purpose parser. This file will contain the rules for a predicate called parse. As described in class, parse takes as input a sentential form, i.e., lists of terminals and nonterminals, as its first argument. The second argument will be a list of symbols (terminals) to parse. Then, parse should respond Yes if and only if the sentential form derives the list of symbols using a leftmost derivation for the grammar.

In particular, we will only test your parse predicate with two fully-instantiated lists: the first will be the list of the grammar's start variable (not a Prolog variable) and the second will be a list of symbols to be parsed by that grammar (also not a Prolog variable).

For example, here are some sample inputs and outputs:

| ?- [part4].            <--- HERE WE ARE LOADING IN OUR parse PROGRAM
yes 

| ?- [g0].            <--- HERE WE ARE LOADING IN A GRAMMAR
yes

| ?- parse([s], [1, +, 0, +, 1]).   <--- note that everything is instantiated...
yes

| ?- parse([s], [1, +]).
no

| ?- parse([s], [1, 0, +]).
no

You should write the parse inference rules in a file called parser.pl and submit that file. Keep in mind that although we will only call parse with a one-element list (of the start symbol) as a first argument, you may want to write the predicate more generally than this to help with the recursion... .

Your code will assume that there are facts already defined for the grammar using the names variable, terminal, and rule as illustrated above. Keep your code simple and elegant and be sure to test it thoroughly on the supplied grammars before submitting it. This can be done using fewer than 10 new lines of Prolog code - if you are writing much more than that you are doing too much work!

Problem 5: The paths less traveled

[10 points, pair or individual]

This problem asks you to write a predicate that can generate minimum-length paths from one node to another in a general, directed graph: genminpath. It's only a small change from last week's extra credit predicates.

Submit your genminpath predicate in a file named paths.pl. A starter file is available from the usual place: /cs/cs60/hwfiles/a9.

Write a predicate genminpath(A, B, Graph, Path), whose arguments are identical in format to the path predicate from Hw #8: a source node, a destination node, a graph, and a path represented as a list of nodes. However, genminpath should work for completely general graphs, i.e., even when the graph Graph contains cycles! Also, genminpath should only return minimal-length paths.

For example, you might try graph1(G), genPath( a, d, G, Path ) with

graph1( [ [a,b], [b,c], [c,a], [c,d], [c,z], [z,a], [z,d] ] )

Path = [ a, b, c, d ] ; 

No

Optional Bonus Problems

[up to +15 points, pair or individual]

You may submit either or both of these two problems for +5 and +10 points, respectively. The first one you should include in your parser.pl file. The second one should be submitted in a file named puzzle.pl.

Generating parsable statements (token lists)

For this problem, add a predicate named parseGen to your parser.pl file. This parseGen predicate should be identical in interface to problem #4's parse predicate. However, it should be able to generate all of the valid statements (actually, lists of tokens) that the second input represents. That is, parseGen should be able to be called as

parseGen( [s], TokenList ).

All?    Note that there are likely to be infinitely many token lists that work. Prolog will be OK with this and your parseGen should be happy to keep generating new ones, as long as you're willing to type semicolons. However, because there are infinitely many, testing with setof will not work.

Include a comment next to parseGen that explains your approach and why it will, given enough time and memory, generate any valid (parsable) token list.

Choose-your-own-puzzle

We've seen several puzzles and the solutions for these puzzles written in Prolog. For up to +10 bonus points (depending on the complexity), write a Prolog program to solve your favorite puzzle. Here are the requirements:

• Name your file puzzle.pl.
• Write very clear documentation at the top of your file explaining what the game is, it's rules, and how to run your program.
• In the spirit of Prolog, your solution should specify the rules and constraints of the game and not the explicit algorithm for solving it!