Assignment 9 "Lite": Some Fun (and Games) with Prolog [75 points]!
Due Wednesday, November 8 by 11:59 PM

Note that the second midterm will be handed out on Wednesday, Nov 8 at 8am and due at 10am on Friday, Nov 10. I STRONGLY suggest that you finish the homework before taking the midterm.

This assignment has 4 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.

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: Lights Out! (15 points)

For example, the following example illustrates a winning set of moves:

Start with: [1, 0, 1, 0, 0, 0]
Choose square 2: [1, 1, 0, 1, 0, 0]
Choose square 0: [0, 0, 0, 1, 0, 0] 
Choose square 5: [0, 0, 0, 1, 1, 1]
Choose square 4: [0, 0, 0, 0, 0, 0]

You have probably written a lights out implementation in another programming class (like CS5). However, now we are going to write a "program" in Prolog that will find winning lists of moves for us!

Your task is to write a predicate lightsOut(Config, Moves) that returns true if applying the moves in the list Moves starting with the configuration Config will yield a winning configuration. You do not have to handle lists of moves that contain "loops", or moves that toggle the lights back to a state you have seen before (i.e., it's OK if prolog says No to such lists of moves). However, your predicate should support the situation where Moves is a variable, hence "tricking" prolog into solving the game for us!  (You can assume Config will always be bound).

For example:

| ?- lightsOut([1, 1, 1, 0, 0, 0], X).

X = [0,1,0] ;

X = [0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,5] ;

X = [0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,4] ;

X = [0,1,0,2,0,1,0,3,0,1,0,2,3] ;

X = [0,1,0,2,2] ;

X = [1] ;

no

Part 3: Towers of Hanoi (25 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 before embarking on this program. I also recommend that you solve problem 2 (lights out!) before solving this problem.  The big ideas in all three 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!)
  
  
• A few notes on this program:
  
  
  • You'll need to use dynamic and assert in much the same way that we did in the "fox, lettuce, hare" problem that we saw in class.
    
    
  • If you run your hanoi 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... .