Typically puzzles ask the user to satisfy a set of constraints -- and this is precisely what prolog was designed to do. In this assignment you will be using prolog to sovlve several different types of puzzles. The work involved is primarily in representing the puzzles and their rules. In order to help the graders, please check that you name your prolog rules (predicates) as they're specified in the assignment.
Feel free to use Prolog's built-in predicates in solving these puzzles. In particular,
Prolog has a built-in length(L, N) which is true if and only
if list L has length N. member( X, L ) is built-in to at least some versions
of Prolog. You may use your remove from the previous hw (or use this
one:
remove(X,[X|R],R).
remove(X,[F|R],[F|S]) :- remove(X,R,S).
Printing all the elements of the resulting lists...
By default Prolog will use ellipses (...) to represent items in
a list nested more than 10 deep. For example,
?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]
Yes
?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16], write(L).
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]
Yes
set_prolog_flag( toplevel_print_options,
[quoted(true), portray(true), attributes(portray), max_depth(0)] ).
?- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
Yes
Submission Please submit your problems in separate files named part1.pl, part2.pl, part3.pl, part4.pl, and, if you try the extra credit, part5.pl. You will find starter files for each of these parts at the top-level assignment page.
/*
* 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 values -- they can
* only check for consistency of already-instantiated values. Thus,
* they must be tested _after_ variables are instantiated with values.
*/
Be sure to format your output in an easy-to-read manner.
In addition, make sure that you leave a comment for the graders so that they
know how to generate and print the solution to the puzzle. As an example,
consider the solve predicate in the einstein.pl example. It
first generates the solution to the Zebra puzzle, and then it prints the
five houses in a reasonable fashion:
solve :-
einstein( [ H1, H2, H3, H4, H5 ] ),
write( ' first house: '), write(H1), nl,
write( 'second house: '), write(H2), nl,
write( ' third house: '), write(H3), nl,
write( 'fourth house: '), write(H4), nl,
write( ' fifth house: '), write(H5), nl.
?- solve.
first house: [norwegian, cat, dunhill, water, yellow]
second house: [dane, horse, marlboro, tea, blue]
third house: [brit, bird, pallmall, milk, red]
fourth house: [german, zebra, rothmans, coffee, green]
fifth house: [swede, dog, winfield, beer, white]
Yes
Please submit this part of the assignment in a file called part1.pl.
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 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, Tree)
will solve for an arithmetic tree named Tree using operators
Ops among the integers in
Values to give the final value Result. For example,
| ?- 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 //).
Here is an eval predicate (for evaluating trees of
opreations) that will be helpful in solving this
problem. You may copy
this code and use it freely. Note that eval can handle
numbers and it can handle trees that are bound to some value (using the
nonvar predicate)
Thus, the eval predicate can not generate
trees -- allowing eval to generate trees
can lead to infinite recursion, as it looks in the (unbounded) space of
trees for operations possibly leading to R.
eval(R, R) :- number(R).
eval(['+', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR + BR.
eval(['*', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR * BR.
eval(['-', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), R is AR - BR.
eval(['/', A, B], R) :- nonvar(A), nonvar(B), eval(A, AR), eval(B, BR), BR\==0, R is AR // BR.
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. Warning: You may especially want to check the second of these. In particular, a common partially working solution to this problem handles the first example below, but not the second example. Notice how the list of values is being split into sublists in the second case:
?- solve(['+', '*', '-'], [1, 2, 3, 4], 24, Tree), Tree = [*,1,[*,2,[*,3,4]]] % other solutions are certainly possible! ?- solve(['+','-','*','/'], [2,8,22,424], 42, Tree). % only one solution possible! Tree = [-,[/,424,8],[/,22,2]] ?- solve(['+'], [1, 1, 1, 1], 24, Tree). % no solution no. ?- solve(['+'], [24], 24, Tree). % base case Tree = 24Notice that a plain integer is the simplest possible solution tree (not [24]), and there are many more answers to the third example above.
Please submit this part of the assignment in a file called part2.pl.
[ [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.
[ [1, 2, 3, 4], [], [] ]
[ [], [], [1, 2, 3, 4] ]
| ?- 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.
| ?- 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!)
| ?- retractall(marked(_)).
yes
Then, you should be able to run it again... .
In Assignment 5 you wrote a recursive descent parser in Java for a grammar for arithmetic expressions involving addition, multiplication, and exponentiation. In this assignment you will write a general "parse engine" in Prolog which will allow you to determine if a given string can be parsed by virtually ANY grammar that you give it! Amazing, but true!
Here, the goal is not to determine a parse tree, but we DO want to know if there EXISTS a parse tree for a given string using the given grammar. For example, IF we had a grammar for the English language, we would be able to ask our parser if a particular sentence was valid in English. The neat thing is that we won't tell Prolog how to parse, we'll just tell it what a grammar is and what string we're interested in and ask: "Hey Prolog, can this string be parsed by the given grammar?"
Take a look at the files g0.pl,g1.pl, g2.pl, g3.pl and g4.pl supplied to you at the top-level assignment directory. Each of these files specifies a different grammar. A grammar is specified by declaring the variables, terminals, and rules.
For example, consider the grammar for valid additions of 0's and 1's. (This is the grammar specified in the file g0.pl.)s -> v + s | v v -> 0 | 1
Here, s and v are the variables and 0 and 1 are the terminals. Notice that no upper-case letters are used. This is important, since Prolog uses upper-case letters to represent its own variables.
You can see how this grammar is specified in file gr0.pl Our convention is as follows: Variables are stated as facts. These facts simply state the names of the variables. In this example, the facts state that s and v are variables as shown below.
variable(s). variable(v).We also specify which symbols are terminals as shown below.
terminal(0). terminal(1). terminal(+).Finally, the grammar rules are stated as ordered pairs, where the first element is the left-hand-side of a rule and the second argument is the LIST of elements appearing on the right-hand-side of that rule. For the grammar above, these rules are stated as shown below.
rule(s, [v, +, s]). rule(s, [v]). rule(v, [0]). rule(v, [1]).
Your task is to write a general-purpose parser. This file will contain the rules for a predicate called parse. As described in class, parse takes as input a sentential form and a list of symbols to parse and says "yes" (or "true") if and only if the sentential form derives the list of symbols using a leftmost derivation for the grammar.
In particular, we will only test your parse predicate
with two fully-instantiated lists: the first will be the list of
the grammar's start variable (not a Prolog variable) and the
second will be a list of symbols to be parsed by that grammar
(also not a Prolog variable).
For example, here are some sample inputs and outputs:
| ?- [part4]. <--- HERE WE ARE LOADING IN OUR parse PROGRAM yes | ?- [g0]. <--- HERE WE ARE LOADING IN A GRAMMAR yes | ?- parse([s], [1, +, 0, +, 1]). <--- note that everything is instantiated... yes | ?- parse([s], [1, +]). no | ?- parse([s], [1, 0, +]). no
You should write the parse inference rules in a file called
part4.pl and submit that file. Keep in mind that although
we will only call parse with a one-element list (of the start symbol)
as a first argument, you may want to write the predicate more generally than
this to help with the recursion... .
Your code will assume that there are facts already defined for the
grammar
using the names variable, terminal, and
rule as illustrated above.
Keep your code simple and
elegant and be sure to test it
thoroughly on the supplied grammars before submitting it.
This can be done using fewer than 10
new lines of Prolog code - if you are writing much more than that
you are doing too much work!
fourFours( N, Tree )