/* * CS 42, Fall 2009, Assignment 9 * * Constraint Solving using Backtracking * * Due: Sunday, April 4 by 11:59 PM * * Note: This is a skeletal Prolog file, a09.pro, which you can complete * with your own solutions. */ /***************************************************************************** * Part 1: List-processing exercises: *****************************************************************************/ /* * 1.a Construct a predicate member/3 that generalizes member/2. * * Whereas member/2 will generate all members of a given list, member/3 will * do that, as well as return the residue list when the generated member is * removed. * */ member(_Member, _List, _Residue) :- tbd. testMember(Name, List, Desired) :- setof1([Member, Residue], member(Member, List, Residue), Ans), (Ans == Desired -> write('*** member test '), write(Name), write(' passed'), nl ; write('*** member test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' actual was '), write(Ans), nl ). testMember(1) :- testMember(1, [a, b, c, d, e], [ [a, [b, c, d, e]], [b, [a, c, d, e]], [c, [a, b, d, e]], [d, [a, b, c, e]], [e, [a, b, c, d]]]). testMember :- testMember(1). /* * 1.b Construct a predicate transpose/2 that transposes a matrix represented * as a list of lists. For example * * transpose([[1, 2, 3], [4, 5, 6]], [[1, 4], [2, 5], [3, 6]]). * * You may assume that the matrix is rectangular, or if you wish, * check that it is before attempting the actual transposition. */ transpose(_Original, _Transpose) :- tbd. testTranspose(Name, Original, Desired) :- transpose(Original, Ans), (Ans == Desired -> write('*** transpose test '), write(Name), write(' passed'), nl ; write('*** transpose test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' actual was '), write(Ans), nl ). testTranspose(1) :- testTranspose(1, [[1]], [[1]]). testTranspose(2) :- testTranspose(2, [[1, 2, 3], [4, 5, 6]], [[1, 4], [2, 5], [3, 6]]). testTranspose :- testTranspose(1), testTranspose(2). /***************************************************************************** * Part 2: 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 42. * * 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 42 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. * * 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. *****************************************************************************/ 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), !, ( 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), []). 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(4, Exp, solve42([+, *, -], [3, 3, 5], 9, Exp), []). test42(5) :- test42(5, Exp, solve42([+, *, -], [4, 6], 10, Exp), [[+, 4, 6], [+, 6, 4]]). test42(6) :- test42(6, Exp, solve42([+, *, -], [4, 5, 6], 10, Exp), [[*, 5, [-, 6, 4]], [*, [-, 6, 4], 5]]). test42(7) :- test42(7, Exp, solve42([+, *, -], [5, 6, 7], 10, Exp), []). test42(8) :- test42(8, Exp, solve42([+, *, -], [5, 6, 7, 8], 10, Exp), [ [+, 5, [+, 6, [-, 7, 8]]], [+, 5, [+, 7, [-, 6, 8]]], [+, 5, [+, [-, 6, 8], 7]], [+, 5, [+, [-, 7, 8], 6]], [+, 5, [-, 6, [-, 8, 7]]], [+, 5, [-, 7, [-, 8, 6]]], [+, 5, [-, [+, 6, 7], 8]], [+, 5, [-, [+, 7, 6], 8]], [+, 6, [+, 5, [-, 7, 8]]], [+, 6, [+, 7, [-, 5, 8]]], [+, 6, [+, [-, 5, 8], 7]], [+, 6, [+, [-, 7, 8], 5]], [+, 6, [-, 5, [-, 8, 7]]], [+, 6, [-, 7, [-, 8, 5]]], [+, 6, [-, [+, 5, 7], 8]], [+, 6, [-, [+, 7, 5], 8]], [+, 7, [+, 5, [-, 6, 8]]], [+, 7, [+, 6, [-, 5, 8]]], [+, 7, [+, [-, 5, 8], 6]], [+, 7, [+, [-, 6, 8], 5]], [+, 7, [-, 5, [-, 8, 6]]], [+, 7, [-, 6, [-, 8, 5]]], [+, 7, [-, [+, 5, 6], 8]], [+, 7, [-, [+, 6, 5], 8]], [+, [+, 5, 6], [-, 7, 8]], [+, [+, 5, 7], [-, 6, 8]], [+, [+, 5, [-, 6, 8]], 7], [+, [+, 5, [-, 7, 8]], 6], [+, [+, 6, 5], [-, 7, 8]], [+, [+, 6, 7], [-, 5, 8]], [+, [+, 6, [-, 5, 8]], 7], [+, [+, 6, [-, 7, 8]], 5], [+, [+, 7, 5], [-, 6, 8]], [+, [+, 7, 6], [-, 5, 8]], [+, [+, 7, [-, 5, 8]], 6], [+, [+, 7, [-, 6, 8]], 5], [+, [+, [-, 5, 8], 6], 7], [+, [+, [-, 5, 8], 7], 6], [+, [+, [-, 6, 8], 5], 7], [+, [+, [-, 6, 8], 7], 5], [+, [+, [-, 7, 8], 5], 6], [+, [+, [-, 7, 8], 6], 5], [+, [-, 5, 8], [+, 6, 7]], [+, [-, 5, 8], [+, 7, 6]], [+, [-, 5, [-, 8, 6]], 7], [+, [-, 5, [-, 8, 7]], 6], [+, [-, 6, 8], [+, 5, 7]], [+, [-, 6, 8], [+, 7, 5]], [+, [-, 6, [-, 8, 5]], 7], [+, [-, 6, [-, 8, 7]], 5], [+, [-, 7, 8], [+, 5, 6]], [+, [-, 7, 8], [+, 6, 5]], [+, [-, 7, [-, 8, 5]], 6], [+, [-, 7, [-, 8, 6]], 5], [+, [-, [+, 5, 6], 8], 7], [+, [-, [+, 5, 7], 8], 6], [+, [-, [+, 6, 5], 8], 7], [+, [-, [+, 6, 7], 8], 5], [+, [-, [+, 7, 5], 8], 6], [+, [-, [+, 7, 6], 8], 5], [-, 5, [-, 8, [+, 6, 7]]], [-, 5, [-, 8, [+, 7, 6]]], [-, 5, [-, [-, 8, 6], 7]], [-, 5, [-, [-, 8, 7], 6]], [-, 6, [-, 8, [+, 5, 7]]], [-, 6, [-, 8, [+, 7, 5]]], [-, 6, [-, [-, 8, 5], 7]], [-, 6, [-, [-, 8, 7], 5]], [-, 7, [-, 8, [+, 5, 6]]], [-, 7, [-, 8, [+, 6, 5]]], [-, 7, [-, [-, 8, 5], 6]], [-, 7, [-, [-, 8, 6], 5]], [-, [*, 8, [-, 7, 5]], 6], [-, [*, [-, 7, 5], 8], 6], [-, [+, 5, 6], [-, 8, 7]], [-, [+, 5, 7], [-, 8, 6]], [-, [+, 5, [+, 6, 7]], 8], [-, [+, 5, [+, 7, 6]], 8], [-, [+, 6, 5], [-, 8, 7]], [-, [+, 6, 7], [-, 8, 5]], [-, [+, 6, [+, 5, 7]], 8], [-, [+, 6, [+, 7, 5]], 8], [-, [+, 7, 5], [-, 8, 6]], [-, [+, 7, 6], [-, 8, 5]], [-, [+, 7, [+, 5, 6]], 8], [-, [+, 7, [+, 6, 5]], 8], [-, [+, [+, 5, 6], 7], 8], [-, [+, [+, 5, 7], 6], 8], [-, [+, [+, 6, 5], 7], 8], [-, [+, [+, 6, 7], 5], 8], [-, [+, [+, 7, 5], 6], 8], [-, [+, [+, 7, 6], 5], 8] ]). test42(9) :- test42(9, 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]] ]). /***************************************************************************** * Part 3: 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. test42 :- test42(_), fail; true. /***************************************************************************** * Part 4: 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 clues 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. *****************************************************************************/ snacks([_Triple1, _Triple2, _Triple3, _Triple4, _Triple5]) :- tbd. 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. tbd :- fail. tests1a :- testMember. tests1b :- testTranspose. tests2 :- testSudograph. tests3 :- test42. tests4 :- testSnacks. test :- tests1a, fail. test :- tests1b, fail. test :- tests2, fail. test :- tests3, fail. test :- tests4, fail. test :- true.