Assignment 9: Fun (and Games) with Prolog [100 points]!
Due Monday, November 12 by 11:59 PM

This assignment has 3 parts. Please be sure to name your prolog rules exactly as we've specified in the assignment. This is important since some of your code will be tested by an automatic code tester which will look for precisely these names.

Recall Prolog's built-in rules that may be useful here:

• length(L, N) which is true if and only if list L has length N.
• append(A, B, C) which is true if and only if the result of appending list B to the end of list A results in list C.
• member(E, L) which is true if and only if E is an element in the list L.

Finally, remember that it's fine if your prolog rule finds the same solution more than once as long as it doesn't find it an infinite number of times! In other words, your prolog rules should halt, but may find the same solution a finite number of time.

Part 1: The Game of 24! (35 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 an arbitrary value, 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 rule called solve such that

 solve(Operators, Numbers, Result, Tree)
 

 | ?- solve(['+'], [1, 2, 3], 6, ['+', 1, ['+', 2, 3]]).
 yes

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

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

This means that we have found a solution Tree using operators +, *, and - on that will combine with set of numbers [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, '/' is performed using // (which is why 1-line comments in prolog are prefaced by % and not //).

We provide an eval predicate that will be quite useful in solving this problem. Here it is:

eval(R, R) :- number(R).
eval(['+', A, B], R) :- eval( A, R1 ), eval( B, R2 ), R is R1 + R2.
eval(['-', A, B], R) :- eval( A, R1 ), eval( B, R2 ), R is R1 - R2.
eval(['*', A, B], R) :- eval( A, R1 ), eval( B, R2 ), R is R1 * R2.
eval(['/', A, B], R) :- eval( A, R1 ), eval( B, R2 ), R is R1 // R2.

You may also use any of Prolog's built-in rules and any helper rules that you like (including those that we wrote in class).

Here are some other examples of solve in action:

 ?- solve(['+'], [1, 1, 1, 1], 24, Tree).

 no.


 ?- solve(['+'], [24], 24, Tree).

 Tree = 24


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

 Tree = [*,1,[*,2,[*,3,4]]]
 

This problem will require that you to think very carefully about the order in which rules are specified in your prolog rules. Remember from class that order matters!

A very good approach to this problem is to write a helper rule called tree that takes as input a list Operations of valid operations to be used, a list Numbers of numbers to be used and a Tree which is a tree in which the leaves of the tree are the numbers, where each number is used exactly once, the internal nodes in the tree are selected from Operations (with operations permitted to be used more than once). In fact, you might find it convenient to stipulate that the numbers at the leaves must occur exactly in the order (from left-to-right) that they are given in Numbers. (You can deal with permuting these numbers someplace else.) For example:

| ?- tree(['+', '*'], [1, 2, 3, 4], ['*', ['+', 1, 2], ['*', 3, 4]]).
yes

| ?- tree(['+', '*'], [1, 2, 3], X).

X = [+,1,[+,2,3]] ;
X = [+,1,[*,2,3]] ;
X = [+,[+,1,2],3] ;
X = [+,[*,1,2],3] ;
X = [*,1,[+,2,3]] ;
X = [*,1,[*,2,3]] ;
X = [*,[+,1,2],3] ;
X = [*,[*,1,2],3] ;
no

Notice that in the first case we gave tree all three lists and it verified that the third list (a tree) could be constructed from the operations in the first list and the numbers in the second list. Then, in the second case, we "tricked" prolog into generating all possible trees with a given set of operations and numbers. Once you can do this, you're nearly done!

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

Part 2: SudoGraph (35 points)

•  a list of nodes, represented by logical variables,
•  a list of constraints, represented as lists of those same local variables,
•  a list of colors, which are atomic (atoms or numbers)

Part 3: Towers of Hanoi (30 Points)

In this part of the assignment, you will write a Prolog program to solve the Towers of Hanoi puzzle. Please submit your solution in a file called part3.pl. You should carefully review the "fox, lettuce, hare" solution that we examined in class (on Thursday) before embarking on this program. The big ideas in these two programs are very similar. Fortunately though, this Hanoi program is considerably shorter than the fox, lettuce, hare problem. (You should expect your program to be about 20 lines of Prolog code, not including comments and spacing between rules.) Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer correct solutions to the puzzle. Here are the details:

• The disks will be represented by positive integers. There will always be only three pegs but there may be any number of disks. The program must be able to handle an arbitrary number of disks.
  
  
• A configuration of the puzzle will be represented by a list of three lists. The first list contains the disks (from smallest to largest) on peg 1, the second list contains the disks (from smallest to largest) on peg 2, and the third list contains the disks (from smallest to largest) on peg 3. For example, the list

   [ [1, 2], [3, 4], [] ]
   

  represents disk 1 on top of disk 2 on peg 1, disk 3 on top of disk 4 on peg 2, and nothing on peg 3.
  
  
• The initial configuration contains all disks on peg 1. For the case of four disks, for example, the initial configuration would be

   [ [1, 2, 3, 4], [], [] ]
   

• The final configuration contains all disks on peg 3. For the case of four disks, for example, the final configuration would be

   [ [], [], [1, 2, 3, 4] ]
   

• The number "12" represents moving the top disk on peg 1 to peg 2. Similarly, the number "13" represents moving the top disk on peg 1 to peg 3. The other possible moves are "21", "23", "31", and "32". You should write a set of Prolog rules called valid which take as input a configuration, the move number, and a new configuration. The rule evaluates to true if and only if it is a valid move to go from the first configuration to the new configuration via that move. For example, consider the following input and output assuming just three disks are being used:

   | ?- valid([ [1, 2, 3], [], [] ], 12, [ [2, 3], [1], [] ]).
   yes
   

  This is valid because we went from the first configuration to the second configuration via move "12". Here's another example:

   | ?- valid([ [1, 2], [], [3] ], 12, [ [2], [], [1, 3] ]).
   no
   

  In this case, it's possible to move from the first configuration to the second configuration, but not by move "12". Here's yet another example:

   | ?- valid([ [1 , 2], [], [3] ], 31, [ [3, 1, 2], [], [] ]).
   no
   

  Although we did move a disk from peg 3 to peg 1 here, this move was invalid because disk 3 cannot be placed on top of disk 1.
  
  
• Once you've written the six valid move rules, you're almost done! (Write these rules and test them before going on!) Now, you'll write a rule called hanoi which takes as input a configuration and a list of moves. hanoi says "yes" if and only if starting at that configuration and making the sequence of moves described in the list results in getting to the final configuration. Here's an example using three disks:

   | ?- hanoi([ [1], [2], [3] ], [23, 13]).
   yes
   

  The answer here is "yes" because move "23" followed by "13" leaves us in the final configuration. Once this function is written, you can do the following:

   | ?- hanoi( [ [1, 2, 3], [], [] ], Solution).
   Solution = [12,13,21,13,12,31,12,31,21,23,12,13,21,13] 
   

  Your Prolog program may find a different solution. The solution found depends on the order in which the rules were defined. As long as your Prolog program finds a correct solution, that's fine!  Also, test out some small examples (1 or 2 disks) to make sure Prolog finds a finite number of solutions, but for more than 2 disks there will probably be too many solutions returned to practically look at them all.
  
  
• One note on this program: You'll need to use a "VisitedStates" list in much the same way that we did in the "fox, lettuce, hare" problem that we saw in class.