/* * CS 60, Fall 2010, Assignment 11 * * Logic Programming * * Due: Wed. December 8 by 11:59 PM * * Note: This is a skeletal Prolog file, a11.pro, which you can complete * with your own solutions. * * Load this file from the command-line, using e.g. * * swipl -f a11.pro * * assuming you are using SWI-Prolog. * * This assignment has four distinct parts, all of which can be expected * to use backtracking in some form: * * Part 1: Movies Database * Part 2: "42" puzzle. * Part 3: Sudograph solver * Part 4: Snack logic problem */ /***************************************************************************** * Part 1: Movies Database * * First download the file movies.pro from the course website and put it * in your working directory. */ /* * The following will load movies.pro into Prolog from your working directory. */ :- ensure_loaded('movies.pro'). tbd :- nl, write('Answer to be Provided'), nl, fail. % ans0 is solved for you % ans0 is true for the director of ['American Beauty', 1999]? ans0(Director) :- movie(['American Beauty', 1999], Director, _). % ans1 is true for any movie [Title, Year] in which Harrison Ford played a role. ans1(_Movie) :- tbd. % ans2 is true for any movie [Title, Year] having comedy as a descriptor. ans2(_Movie) :- tbd. % ans3 is true for the title of two movies with the same title but produced in different years. ans3(_Title) :- tbd. % ans4 is true for an actress or actor born in New Jersey ans4(_Person) :- tbd. % ans5 is true for an actress or actor born before 1950. ans5(_Person) :- tbd. % ans6 is true for an actress or actor born in New Jersey before 1950. ans6(_Person) :- tbd. % ans7 is true for a pair of an actor and actress who played together in the same movie. ans7(_Actor, _Actress) :- tbd. % ans8 is true for a pair of an actor and actress who played together in more than one movie. ans8(_Actor, _Actress) :- tbd. % ans9 is true for an actor or actress who both directed and played in the same movie. ans9(_Person) :- tbd. % ans10 lists actors and actresses together in order of increasing birth year, giving the year first. ans10(_List) :- tbd. % ans11 is true for the youngest actress or actor (give multiple results if there is a tie). ans11(_Person) :- tbd. % ans12(Degree, Person1, Person2) is true if Person1 is within Degree degrees of Person2. % within degree 1 means that Person1 and Person2 acted in the same movie. % within degree N > 1 means either Person1 is within degree N-1 of Person2, or % Person1 acted in a movie with some Person3, and Person2 is within degree N-1 of Person3. % % Degree is assumed to be instantiated. It is preferrable that each instance of Person2 be % given only once for an instance of Person1, and vice-versa. ans12(_N, _Person1, _Person2) :- tbd. % ans13(N) means that N is the number of actors and actresses not within 6 degress of Kevin Bacon. ans13(_N) :- tbd. /***************************************************************************** * 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 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]]]). /***************************************************************************** * 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 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. *****************************************************************************/ 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. tests1 :- nl, write('ans1: '), ans1(Movie), nl, write(Movie), nl. tests1 :- nl, write('ans2: '), ans2(Movie), nl, write(Movie), nl. tests1 :- nl, write('ans3: '), ans3(Title), nl, write(Title), nl. tests1 :- nl, write('ans4: '), ans4(Person), nl, write(Person), nl. tests1 :- nl, write('ans5: '), ans5(Person), nl, write(Person), nl. tests1 :- nl, write('ans6: '), ans6(Person), nl, write(Person), nl. tests1 :- nl, write('ans7: '), ans7(Actor, Actress), nl, write(Actor), nl, write(' '), nl, write(Actress), nl. tests1 :- nl, write('ans8: '), ans8(Actor, Actress), nl, write(Actor), nl, write(' '), nl, write(Actress), nl. tests1 :- nl, write('ans9: '), ans9(Person), nl, write(Person), nl. tests1 :- nl, write('ans10: '), ans10(List), nl, write(List), nl. tests1 :- nl, write('ans11: '), ans11(Person), nl, write(Person), nl. tests1 :- nl, write('ans12: '), ans12(1, 'Liv Tyler', Person), nl, write(1), write(': '), nl, write(Person), nl. tests1 :- nl, write('ans12: '), ans12(2, 'Liv Tyler', Person), nl, write(2), write(': '), nl, write(Person), nl. tests1 :- nl, write('ans12: '), ans12(3, 'Liv Tyler', Person), nl, write(3), write(': '), nl, write(Person), nl. tests1 :- nl, write('ans13: '), ans13(N), nl, write(N), nl. tests2 :- testSudograph. tests3 :- test42. tests4 :- testSnacks. test :- tests1, fail. test :- tests2, fail. test :- tests3, fail. test :- tests4, fail. test :- true.