CS 5100代写、Prolog program代做、代写Python，Java程序语言

日期：2020-02-23 07:47

CS 5100 Foundations of AI

Assignment 3 Logic Puzzles

Value: 10%

1. Write a Prolog program, in a file named crypta.pl, to solve

the cryptarithmetic puzzle which says

Recall that in such a puzzle, each letter (T, W, O, F, U, R) 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: T = …, O = …, R = etc. Your program, given the

problem details, must print out the solution (any valid solution, though usually these puzzles

have unique solutions). Verify the solution (by doing simple math) before submission!

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. Note that this problem may need more CPU time to come up with a solution.

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).

alldiff([_]).

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? From http://www.logic-puzzles.org/:

“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,

2

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.

a. The apple was eaten later in the week than the mango.

b. The banana was eaten later in the week than both the almonds and peanuts, but earlier in the

week than the pear.

c. The cashews were eaten earlier in the week than both the banana and the apricot, but later in

the week than the peanuts.

d. The pecans were not eaten the evening after the almonds.

e. 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.

Note:

i. You will again need to use the alldiff function, since all options are used only once.

ii. How do you verify the solution? Examine it, and make sure all the constraints are satisfied.

iii. 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.

3

General Prolog hints

• Download the appropriate version of SWI-Prolog to solve this assignment, from

http://www.swi-prolog.org/download/stable .

• Watch out for spelling mistakes, and accidental changes of uppercase

and lowercase terms. Prolog can be unforgiving.

Submission

You will need to submit on BlackBoard the two Prolog files you created, namely crypta.pl and puzzle.pl.

In addition, include a README.txt file with the following:

1. Answers to Problem 1. This will be a list of variables (letters) with associated digit values. If you

did the optional problem, add the answer to that as well.

2. Answers to Problem 2. This will be in the form of 5 triples as shown above.

3. Your answer to the question: What was the easiest part of the assignment?

4. Your answer to the question: What was the hardest part of the assignment?

Put these three files in a folder and zip them up. Please name the zip file using the format:

yourFirstName_yourLastName_Assign3 . Submit the zip file.

Have fun!