/* * CS 42, Fall 2012, Assignment 10 * * Logic Programming * * Due: Wed. December 12 by 11:59 PM * * Note: This is a skeletal Prolog file, a10.pro, which you can complete * with your own solutions. * * Load this file from the command-line, using e.g. * * swipl -f a10.pro * * assuming you are using SWI-Prolog. * * This assignment has three distinct parts, all of which can be expected * to use backtracking in some form: * * Part 1: "42" puzzle. * Part 2: Sudograph solver * Part 3: Snack logic problem */ /***************************************************************************** * Part 1: Construct a solver for the generalized "42" (formerly "24") puzzle. * * In the original game, players view a card with four numbers on it and * try to make an arithmetic expression 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 an arbitrary positive value, called the target, * 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 * solve42(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: * * | ?- solve42([+, *, -], [2, 3, 4, 5], 24, Exp). * * Exp = [*, [+, [-, 3, 2], 5], 4] * * meaning that the expression evaluates to the target 24. * * The test harness will cause your solve42 to generate all solutions, * and it will compare the solutions to the answer key as a set. * * Assume that the set of operators will always be a subset of * [+, *, -]. * *****************************************************************************/ solve42(_Operators, _Numbers, _Target, _Expression) :- tbd. /* The following will be used for testing your 42 puzzles. */ test42(Name, Var, Query, Desired) :- setof1(Var, Query, Ans), !, ( (nonvar(Ans), Ans == Desired) -> write('*** forty-two test '), write(Name), write(' passed'), nl ; write('*** forty-two test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' actual was '), write(Ans), nl ). test42(Name, _Var, _Query, Desired) :- write('*** forty-two test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' no answer produced'), nl. setof1(X, G, Z) :- setof(X, G, Z). setof1(X, G, []) :- \+setof(X, G, _). % Test cases test42(1) :- test42(1, Exp, solve42([+, -], [2, 3], 9, Exp), []). % Note: The test above will pass currently, as solve42 produces no solution. test42(2) :- test42(2, Exp, solve42([+, -], [2, 2], 4, Exp), [[+, 2, 2]]). test42(3) :- test42(3, Exp, solve42([*, -], [3, 3], 9, Exp), [[*, 3, 3]]). test42(4) :- test42(5, Exp, solve42([+, *, -], [4, 6], 10, Exp), [[+, 4, 6], [+, 6, 4]]). test42(5) :- test42(6, Exp, solve42([+, *, -], [4, 5, 6], 10, Exp), [ [*, 5, [-, 6, 4]], [*, [-, 6, 4], 5]]). test42(6) :- test42(7, Exp, solve42([+, *], [1, 3, 4, 5], 42, Exp), [ [*, [+, 1, 5], [+, 3, 4]], [*, [+, 1, 5], [+, 4, 3]], [*, [+, 3, 4], [+, 1, 5]], [*, [+, 3, 4], [+, 5, 1]], [*, [+, 4, 3], [+, 1, 5]], [*, [+, 4, 3], [+, 5, 1]], [*, [+, 5, 1], [+, 3, 4]], [*, [+, 5, 1], [+, 4, 3]]]). test42 :- test42(_), fail; true. /***************************************************************************** * Part 2: Construct a Sudograph solver. * * Sudograph is a generalization of the popular sudoku puzzles. * * A single puzzle specifies: * an id number for the puzzle case, * 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. Ideally a puzzle has only one * solution. * * Your solver should be named as follows: * * sudographSolver(Nodes, Constraints, Color) * *****************************************************************************/ sudographSolver(_Nodes, Constraints, Colors) :- tbd. /* The following will be used for testing your sudograph puzzles. */ testSudograph(IdNumber) :- sudographPuzzle(IdNumber, Nodes, Constraints, Colors), write('sudograph number '), write(IdNumber), ( sudographSolver( Nodes, Constraints, Colors) -> ( nl, write('Colors: '), write(Colors), nl, write('Nodes: '), write(Nodes), nl, write('Constraints: '), nl, showConstraints(Constraints) ) ; write(' failed'), nl ). showConstraints([]). showConstraints([Constraint | Constraints]) :- write(' '), write(Constraint), nl, showConstraints(Constraints). % Sudograph puzzles sudographPuzzle(1, Nodes, Constraints, Colors) :- A = red, Nodes = [A, B, C], Constraints = [[A, B], [B, C]], Colors = [red, blue]. sudographPuzzle(2, Nodes, Constraints, Colors) :- A = red, C = green, E = blue, G = yellow, 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]. sudographPuzzle(3, Nodes, Constraints, Colors) :- B = red, E = green, D = blue, Nodes = [A, B, C, D, E, F, G], Constraints = [[A, B, C, D], [B, C, D, G], [D, E, F, B]], Colors = [red, blue, green, yellow]. % This is a 4x4 sudoku grid sudographPuzzle(4, Nodes, Constraints, Colors) :- X12 = 3, X13 = 1, X23 = 2, X32 = 2, X42 = 1, X43 = 3, Nodes = [X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44], Constraints = [[X11, X12, X13, X14], [X21, X22, X23, X24], [X31, X32, X33, X34], [X41, X42, X43, X44], [X11, X21, X31, X41], [X12, X22, X32, X42], [X13, X23, X33, X43], [X14, X24, X34, X44], [X11, X12, X21, X22], [X13, X14, X23, X24], [X31, X32, X41, X42], [X33, X34, X43, X44]], Colors = [1, 2, 3, 4]. testSudograph :- testSudograph(_), fail; true. /***************************************************************************** * Part 3: College snack logic problem * 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? * Construct a Prolog predicate snacks of one argument * that yields each solution for the given set of clues, in the form of a * list of triples of the form (Student, College, Snack). * * 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 can't generate, so they must be * tested after the variables are instantiated with values. *****************************************************************************/ testSnacks :- snacks([Triple1, Triple2, Triple3, Triple4, Triple5]) -> ( write('snacks:'), nl, write(Triple1), nl, write(Triple2), nl, write(Triple3), nl, write(Triple4), nl, write(Triple5), nl ) ; write('snack test failed'), nl. test :- test42, fail. test :- testSudograph, fail. test :- testSnacks, fail. test :- true.