/* * CS 60, Homework 9. * * Due Sun. Apr. 6, 11:59 p.m. * */ /* * 1 of 3: 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. * * 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, Exp) * will solve for an expression using operators Ops on the set Values * to give the value Result. For example, alluding to the original game * a dialog with Prolog would be: * * | ?- solve([+, *, -], [2, 3, 4, 5], 24, Exp). * * Exp = (3-2+5)*4 * * meaning that the expression evaluates to the target 24. * Assume that the set of operators will always be a subset of * [+, *, -]. * * Below we provide some predicates that could be helpful in solving this * problem. Use recursion and back-tracking to do the work for you. */ solve(_Ops, _Values, _Result, _Tree) :- tbd. test(1) :- test_exp(1, Exp, solve([+, *, -], [2, 3, 4, 5], 24, Exp), [2* (3+ (4+5)), 2* (3+ (5+4)), 2* (4+ (3+5)), 2* (4+ (5+3)), 2* (5+ (3+4)), 2* (5+ (4+3)), 2* (3+4+5), 2* (3+5+4), 2* (4+3+5), 2* (4+5+3), 2* (5+3+4), 2* (5+4+3), 4* (3+ (5-2)), 4* (5+ (3-2)), 4* (3-2+5), 4* (5-2+3), 4* (3- (2-5)), 4* (5- (2-3)), 4* (3+5-2), 4* (5+3-2), (3+ (4+5))*2, (3+ (5+4))*2, (3+ (5-2))*4, (4+ (3+5))*2, (4+ (5+3))*2, (5+ (3+4))*2, (5+ (4+3))*2, (5+ (3-2))*4, (3+4+5)*2, (3+5+4)*2, (4+3+5)*2, (4+5+3)*2, (5+3+4)*2, (5+4+3)*2, (3-2+5)*4, (5-2+3)*4, (3- (2-5))*4, (5- (2-3))*4, (3+5-2)*4, (5+3-2)*4 ]). test(2) :- test_exp(2, Exp, solve([+], [1, 1, 1, 1], 24, Exp), []). /* * Problem 2 of 3: Construct a Sudograph solver. * * Sudograph is a generalization of the popular sudoku puzzles. * * A single puzzle specifies: * 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). * * The objective is to find a solution of the puzzle, which is defined to be * an assignment of a color to each node, such that no two nodes in any * constraint are assigned the same color. */ test(3) :- Nodes = [A, B, C, D, E, F, G], Constraints = [[A, B, C], [B, C, D], [C, D, E], [D, E, F], [E, F, G], [G, A, B]], Colors = [red, blue, green, yellow], test_sudograph(Nodes, Constraints, Colors). /* Sample output: ?- test(3). Colors: [red, blue, green, yellow] Nodes: [red, blue, green, red, blue, green, yellow] Constraints: [red, blue, green] [blue, green, red] [green, red, blue] [red, blue, green] [blue, green, yellow] [yellow, red, blue] */ /* * Problem 3 of 3: * * 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, snickers, 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 snickers and donuts. * 4. The hmc student brought spam as a snack and sat in the middle seat. * 5. snickers 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, so they must be * tested after the variables are instantiated with values. */ /* The following will be used for testing your 24 puzzles. */ test_exp(Name, Var, Query, Desired) :- setof(Var, Query, Ans), !, ( Ans == Desired -> write('*** test '), write(Name), write(' passed'), nl ; write('*** test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' actual was '), write(Ans), nl ). test_exp(Name, _Var, _Query, []) :- !, write('*** test '), write(Name), write(' passed'), nl. test_exp(Name, _Var, _Query, Desired) :- write('*** test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' no answer produced'), nl. /* The following will be used for testing your sudograph puzzles. */ test_sudograph(Nodes, Constraints, Colors) :- sudograph( Nodes, Constraints, Colors), write('Colors: '), write(Colors), nl, write('Nodes: '), write(Nodes), nl, write('Constraints: '), nl, showConstraints(Constraints). showConstraints([]). showConstraints([Constraint | Constraints]) :- write(' '), write(Constraint), nl, showConstraints(Constraints). /* test all solutions */ test :- test(_), fail; true.