Foundations of AI
1. Write a Prolog program, in a file named crypta.pl, to solve the cryptarithmetic puzzle which
Recall that in such a puzzle, each letter (S, E, N, D, T, H, M, O and Y) stands for a single digit in
the range 0 to 9. No two letters can be bound to the same digit – that is, each letter stands for a
different digit. When the digits are substituted for the letters, the arithmetic equation should be
correct! The solution is a set of variables with values, like: E = …, O = …, S = etc. Your program,
given the problem details, must print out the solution (any valid solution, though usually these
puzzles have unique solutions).
Optional: For fun, if you are done with the problem above, you can also try to solve the puzzle:
The fun part is to see how easy it is to change the data for a different problem,
and have it churn out the answer.
In solving this problem, you will need to use an alldiff condition. For simplicity,
since it includes the confusing “!” operator, that function is provided here:
% Succeeds if all elements in the argument list are bound and all different.
% Fails if any of the elements are unbound, or equal to some other element.
alldiff([H | T]) :- member(H, T), !, fail.
alldiff([_ | T]) :- alldiff(T).
This problem is worth 4 points.
2. In this problem, you will develop a Prolog program named puzzle.pl to solve a specific logic
puzzle. What’s a logic puzzle?
“Logic puzzles come in all shapes and sizes, but the kind of puzzles we offer here are most
commonly referred to as "logic grid" puzzles. In each puzzle you are given a series of categories,
and an equal number of options within each category. Each option is used once and only once.
Your goal is to figure out which options are linked together based on a series of given clues. Each
puzzle has only one unique solution, and each can be solved using simple logical processes (i.e.
educated guesses are not required).”
That’s the kind we’ll see here, though the problems are from another source. These problems
are usually solved by hand with a grid, but you will solve it using Prolog.
Here is the statement of the problem:
Bill eats a snack every night, having a different fruit and different nuts each night. From the
statements below, identify what Bill had for a snack for each weeknight last week.
1. The apple was eaten later in the week than the mango.
2. The banana was eaten later in the week than both the almonds and peanuts, but earlier
in the week than the pear.
3. The cashews were eaten earlier in the week than both the banana and the apricot, but
later in the week than the peanuts.
4. The pecans were not eaten the evening after the almonds.
5. Bill ate walnuts one night.
Note that the problem is about 5 weeknights (Monday through Friday), and mentions 5
kinds of fruit and 5 kinds of nuts. Your program should solve the problem and print out
the solution, which will be a set of 5 triples like (Monday, apple, pecans), … (Friday,
mango, walnuts). Clearly, these are not the correct answers, but just values to show you
what the solution will look like.
1. You will again need to use the alldiff function, since all options are used only once.
2. How do you verify the solution? Examine it, and make sure all the constraints are satisfied.
3. You will need to use negation to express one or more constraints, for example condition 4
above. Negation is tricky in Prolog and needs some understanding. Normally, Prolog tries to
prove things, and in the process bind values to unbound variables. Given an expression E
with unbound variables, Prolog tries to find variable bindings that make E true. But if you
use the negation operator \+ with an expression E that contains unbound variables, as
usual, \+E will try to find variable bindings that make E true. If it succeeds, \+E will fail, and
no new bindings are formed. If it fails, (i.e. it cannot find bindings to make E true), no new
bindings are formed either.
The thing to remember is that negation is useful to stop certain (unifications or) bindings
from happening. You cannot use it to identify new bindings.
This problem is worth 6 points.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
1. Answer to problem 1
Answer to the optional problem.
2. Answer to the problem 2
[tuesday, apple, cashew...