Assignment 4: Fun (and Games) with Prolog!
Due Monday, February 20, 2012 by 11:59pm

Individual or pairs    This week's problems may be done individually or in pairs (on a per-problem basis). Please be sure to indicate your partner if you do work in pairs, and make sure that you share the work fairly, as noted in the syllabus's pair-programming guidelines.

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, and member( X, L ) is built-in to SWI Prolog. You may use your removeOne from the previous hw (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)
• puzzle.pl (for the ex. cr.)

You will find starter files for each of these parts at the top-level assignment page. The Java problems are solved separately, on-line.

Part 1: Logic-constraint puzzles (30 Points)

Note on spelling: Be careful with the various names in this problem -- you'll want to keep the spelling consistent. In particular, be sure collette is with two l's and two t's. (We've tried to be consistent ourselves; if you see any problems, let us know!)

For this problem, your task is to write a set of prolog rules that will solve the following logic puzzle (in the spirit of the Zebra Puzzle):

/*
 * 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 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 persons with jots and 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.
 *
 * Here is the solution (which is helpful to have for debugging!)
 *
 * Seats =
   [[bruno,cmc,jots],          % Seat 1
    [algird,pomona,donuts],    % Seat 2
    [collette,hmc,spam],       % Seat 3
    [edwina,scripps,chocolate],% Seat 4
    [dino,pitzer,pez]]         % Seat 5
 *
 */

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 zebra.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! (30 Points)

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 known trees. (The nonvar predicate is used here to check that A and B are not undetermined variables.) 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. Be careful to only allow non-empty splits; otherwise, you'll end up with an infinite recursion!

  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
 

For 20 points, your solve predicate should work as above, generating trees (with a value provided for Result). For the final 10 points, your predicate should also be able to generate the Result value (as well as the tree):

?- solve(['+', '*', '-'], [1, 10,100, 1000], N, Tree).

N = 1111,
Tree = [+,1,[+,10,[+,100,1000]]] ;

N = 1110,
Tree = [*,1,[+,10,[+,100,1000]]] ;

N = -1109,
Tree = [-,1,[+,10,[+,100,1000]]] ;

N = 11001,
Tree = [+,1,[*,10,[+,100,1000]]]   % and many, many more...

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

Part 3: Mudder, Alien, Spampede, Spam! (30 Points)

In this part of the assignment (riverpuzzle.pl), you will write a Prolog program to solve the famous Mudder, Alien, Spampede, and Spam puzzle described in class (this is similar, but far superior to, a puzzle known as "Man, Fox, Hare, and Lettuce" problem you may have seen before). Please submit your solution in a file called riverpuzzle.pl.

You might want to look at the the solution to the Towers of Hanoi problem that is posted on the assignments page. 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. Thus, it will be

   solve( InitialConfig, ListOfMoves )
   

• A configuration itself is a list with two elements: the first element is a list representing the state of the left bank of the river and the second element is a list representing the state of the right bank of the river. The initial configuration of the overall puzzle will thus be [[mudder, alien, spampede, spam], []] 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 [[], [mudder, alien, spampede, spam]] indicating that everyone has made it safely to the right bank.
• Recall that in this puzzle, a configuration cannot have the alien and the spampede on the same side of the river together without the mudder there to keep the spampede safe. Similarly, the spampede and the spam cannot be left without the mudder. Therefore, for example, the configuration [[alien, spampede], [mudder, spam]] is not a valid configuration in this puzzle whereas [[alien, spam], [mudder, spampede]] is valid.
• The list of moves is a list of zero or more symbols -- each symbol describes a motion. The symbols have the following names:
  • mudder_goes_left (the mudder goes in the canoe by himself from the right bank to the left bank).
  • mudder_goes_right (the mudder goes in the canoe by himself from the left bank to the right bank).
  • mudder_takes_alien_left (the mudder takes the alien from the right bank to the left bank).
  • mudder_takes_alien_right (the mudder takes the alien from the left bank to the right bank).
  • mudder_takes_spampede_left (the mudder takes the spampede from the right bank to the left bank).
  • mudder_takes_spampede_right (the mudder takes the spampede from the left bank to the right bank).
  • mudder_takes_spam_left (the mudder takes the spam from the right bank to the left bank).
  • mudder_takes_spam_right (the mudder takes the spam from the left bank to the right bank).

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

?- solve([[mudder, alien, spampede, spam], []], X).

X = [mudder_takes_spampede_right, mudder_goes_left, mudder_takes_alien_right, 
     mudder_takes_spampede_left, mudder_takes_spam_right, 
     mudder_goes_left, mudder_takes_spampede_right]

true

• Your program should not produce a solution that revisits the same configuration twice! For example, if the solution begins by taking the mudder right, and then taking the mudder 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 [[mudder, alien, spampede, spam], []] is different as a list from [[alien, mudder, spampede, spam], []] although we can see that these are really the same configuration.
  
  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, mudder comes before alien (although we are, happily, unaware of mudders eating aliens), alien comes before spampede, and spampede comes before spam. For example, this would allow [[mudder, alien, spampede, spam], []] but disallow [[alien, mudder, spampede, spam], []] as configurations. Similarly, the configuration [[alien, spam], [mudder, spampede]] would be valid but the logically identical configuration [[spam, alien], [spampede, mudder]] would not.
  
  You will need to explicitly encode these sorting rules in your Prolog program as part of the code that rejects invalid configurations.
  
  
• You'll need to use dynamic and assert as seen 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!.

Tips!   

• Mac users who are using the built-in TextEdit editor will find the Command-l (command-ell) keyboard shortcut helpful: it allows you to move to any line in the file.
  
  
• Watch out!    Prolog considers it a syntax error if you leave a space between a predicate name and the left-parenthesis that starts its argument list! (aargh!). For example

  sort (L,S).
  

  is a syntax error, but

  sort(L,S).
  

  is OK.



• Testing things out!    If you've tested your validmove (or similar) predicates with lines such as

  validmove( [ [mudder,spampede,spam], [alien] ], Move, NewC ).
  

  and they all work well, then you'll want to test

  solve( [ [mudder,alien,spampede,spam],[] ], LoM ).
  

  What if solve doesn't work? Then, it helps to work backwards through the puzzle. That is, start with

  solve( [ [], [mudder,alien,spampede,spam] ], LoM ).
  

  which should yield LoM = [] (the base case). Before you try more tests, be sure to clear your marked predicate with the line

  retractall( marked(_) ).
  

  to which Prolog should say true. Then, try

  solve( [ [mudder,spampede], [alien,spam] ], LoM ).
  

  which should yield LoM = [mudder_takes_spampede_right] and (after another retractall( marked(_) ) you should be able to try

  solve( [ [spampede], [mudder,alien,spam] ], LoM ).
  

  which should yield LoM = [mudder_goes_left,mudder_takes_spampede_right] ... and so on, making sure it can find the answer to longer and longer partial versions of the puzzle -- until it can solve the whole thing. Note that there are small differences in order of moves that will solve the puzzle -- this is completely OK.

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

Part 4: Java!

This problem continues the introduction to the syntax and some of the idiosyncrasies of Java, a language very different from Racket. We will consider the big ideas of Java and object-oriented programming next week -- this problem is about Java "in the small," as warm-up for larger applications later.

So, to start getting used to Java, we will use an online resource known as CodingBat or JavaBat. Go to its site, at

  http://codingbat.com/java

Once you're there, you might try the first problem in the Warmup-1 set of problems.

What to do?    The tasks here are

• Log into the site.
• Then, solve 10 more problems of your choice. We particularly recommend you do a few that include loops.

There are many other good Java resources online, including David Matusek's Website:

   

Optional Extra Credit Problem

NEW: As long as the other problems are submitted on time, you may submit the extra credit through 11:59pm Tuesday without using a euro.

You may submit a puzzle of your choice - and its solution - for up to +5 or +10 points, depending on its complexity... .

Choose-your-own-puzzle

We've seen several puzzles and the solutions for these puzzles written in Prolog. For up to +5 or +10 bonus points (depending on the complexity), write a Prolog program to solve a puzzle of your choice. 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!
• Also, be sure to provide the graders with guidelines as to how they can use prolog to solve your puzzle!