Programming Assignment 6: Prolog
Programming Assignment 6: Prolog
Due: Wednesday 1 December by 11:59 PM
Note on Academic Dishonesty. Although you are allowed to discuss these problems
with other people, your work must be entirely your own. It is considered academic
dishonesty to read anyone else’s solution to any of these problems or to share your
solution with another student or to look for solutions to these questions online. See the
syllabus for more information on academic dishonesty.
Instructions. Implement this project in a file called pa6 and submit it on lectura using
the following turnin command:
turnin cs372pa6 pa6
Upon successful submission, you will see this message:
Turning in:
pa6 — ok
All done.
Grading. In order for this program to be graded, it must run on lectura. You are allowed
to use any Prolog predicates that have been covered in class. Please label each
question clearly with a comment so that they are easy to find in case TAs need to check
your code.
Each one of these questions is asking you to solve a variation on an NP-Complete
problem, using Prolog’s ability to search for solutions. Make sure your solutions can
return an answer within a reasonable amount of time. (If it’s taking longer than a minute
or so, it’s too slow.)
Question 1. The SAT Solving Problem.
An atom in propositional logic can be a single variable, a single value (t or f), or either
one of those things, negated. Examples: .𝑝, ~𝑝, 𝑡, ~𝑡, 𝑓
A disjunct in propositional logic is a combination of one or more atoms combined with
OR’s. Examples: 𝑝 ∨ ~𝑞, 𝑡 ∨ 𝑓
A proposition in conjunctive normal form (CNF) is a series of one or more disjuncts
combined with AND’s. Examples: (𝑝 ∨ 𝑞) ∧ (~𝑞 ∨ 𝑟 ∨ ~𝑠)
The SAT solving problem seeks to find assignments for variables in a propositional
expression (usually in CNF) that will make the whole proposition true. Sometimes this is
possible and the goal will be to give a variable assignment that will work. Sometimes
this is impossible and the goal will be to determine that no variable assignment will
make the expression true (i.e. the proposition is a contradiction–always false).
Recall that if any part of a disjunct is true, the whole disjunct is true, but for a conjunct to
be true, every part must be true.
Examples:
1. will be true if and . This is just one possible(𝑝 ∨ 𝑞) ∧ (~𝑞 ∨ 𝑟 ∨ ~𝑠) 𝑝 = 𝑡 𝑞 = 𝑓
variable assignment that will make the conjunct true. There are others.
2. has no solution because the expression is a contradiction.(𝑝 ∨ 𝑞) ∧ (~𝑝) ∧ (~𝑞)
In this problem, we will model expressions in CNF as a list of lists. The outer list will be
a list of the disjuncts, combined with AND’s, and each of the inner lists will be the
disjuncts.
Example: will be [[P,Q],[neg(Q),R,neg(S)]] and(𝑝 ∨ 𝑞) ∧ (~𝑞 ∨ 𝑟 ∨ ~𝑠)
will be [[P,Q],[neg(P)],[neg(Q)]].(𝑝 ∨ 𝑞) ∧ (~𝑝) ∧ (~𝑞)
Start with the following rules to help with the negations:
neg(t) :- f.
neg(f) :- t.
The goal is to write the following predicate:
conjunctTrue(X): X is a proposition in CNF and is true.
I suggest you start with a similar predicate called disjunctTrue(X).
Example Queries.
?- conjunctTrue([[P,Q],[neg(Q),R,neg(S)]]).
P = t,
Q = f ;
P = Q, Q = R, R = t ;
P = Q, Q = t,
R = neg(f) ;
P = Q, Q = t,
R = S, S = f ;
P = Q, Q = t,
R = neg(t),
S = f ;
P = neg(f),
Q = f ;
P = neg(f),
Q = R, R = t ;
P = R, R = neg(f),
Q = t ;
P = neg(f),
Q = t,
R = S, S = f ;
P = neg(f),
Q = t,
R = neg(t),
S = f ;
P = f,
Q = R, R = t ;
P = f,
Q = t,
R = neg(f) ;
P = R, R = S, S = f,
Q = t ;
P = S, S = f,
Q = t,
R = neg(t) ;
P = neg(t),
Q = R, R = t ;
P = neg(t),
Q = t,
R = neg(f) ;
P = neg(t),
Q = t,
R = S, S = f ;
P = R, R = neg(t),
Q = t,
S = f ;
false.
?- conjunctTrue([[P,Q],[neg(P)],[neg(Q)]]).
false.
Question 2. The Clique Problem
In an undirected graph, a clique is a subset of the vertices where each vertex in the
subset is directly connected to the others in the set with an edge.
Example.
There are several cliques in this graph, but the two largest are: {1, 2, 4}, and {2, 3, 4}.
A maximal clique is a largest clique in a graph. In this problem, you are not required to
find a maximal clique. Instead, you are looking for a clique that is greater than or equal
to a particular size.
Example Queries (using the above graph):
?- clique(X, [zero, one, two, three, four], 2).
X = [zero, one] ;
X = [one, two, four] ;
X = [one, two] ;
X = [one, four] ;
X = [two, three, four] ;
X = [two, three] ;
X = [two, four] ;
X = [three, four] ;
false.
?- clique(X, [zero, one, two, three, four], 3).
X = [one, two, four] ;
X = [two, three, four] ;
false.
?- clique(X, [zero, one, two, three, four], 4).
false.
Here are some edge and graph facts to start with and to use as examples for testing.
graph([a, b, c, d, e]).
graph([zero, one, two, three, four]).
edge(a, b).
edge(b, e).
edge(a, e).
edge(b, c).
edge(c, d).
edge(d, e).
edge(d, f).
edge(zero, one).
edge(one, two).
edge(one, four).
edge(two, three).
edge(two, four).
You will probably want to write several predicates, but the one that is required is:
clique(X, Y, M): X is a clique of graph Y whose size is greater than
or equal to M.
Question 3. The Sudoku Problem
This problem is similar to the 8-Queens problem, but instead we are dealing with a mini
version of a Sudoku puzzle. The board for this problem is a square. A solution to4 × 4
the puzzle is a placement of 1’s, 2’s, 3’s, and 4’s so that
● every row has a 1, a 2, a 3, and a 4
● every column has a 1, a 2, a 3, and a 4
● each of the four quarters of the grid has a 1, a 2, a 3, and a 4.(2 × 2 𝑠𝑞𝑢𝑎𝑟𝑒𝑠)
● no row has two of the same number
● no column has two of the same number
● none of the four quarters of the grid has two of the same number
Example (the four quarters are shown by shading):
1 2 3 4
3 4 1 2
2 3 4 1
4 1 2 3
Start with the following fact that represents the locations in the board:
board([1/1, 1/2, 1/3, 1/4, 2/1, 2/2, 2/3, 2/4, 3/1, 3/2, 3/3, 3/4,
4/1, 4/2, 4/3, 4/4]).
You will probably need several predicates to solve this problem, but the one that will be
used in the queries is:
fullPlacement(X): X is a possible placement for all the numbers in the
grid (X is a list of lists).
Example Queries.
?- fullPlacement([Ones, Twos, Threes, Fours]).
Ones = [1/1, 2/3, 3/2, 4/4],
Twos = [1/2, 2/4, 3/1, 4/3],
Threes = [1/3, 2/1, 3/4, 4/2],
Fours = [1/4, 2/2, 3/3, 4/1] .
?- Ones = [1/1, 2/3, 3/4, 4/2], fullPlacement([Ones, Twos, Threes,
Fours]).
Ones = [1/1, 2/3, 3/4, 4/2],
Twos = [1/2, 2/4, 3/1, 4/3],
Threes = [1/3, 2/1, 3/2, 4/4],
Fours = [1/4, 2/2, 3/3, 4/1] .
Note that these queries will have multiple answers. I am only printing out one of the
possible answers.
Question 4. The Traveling Salesperson Problem
In the traveling salesperson problem, we start with a graph where vertices are cities and
the edges are the distances between those cities. The goal is to find a route that
● starts and ends at the same city
● visits every city exactly once
● minimizes the total distance traveled
Since finding a route that is actually optimal is difficult, this version of the problem
specifically looks for a route that
● starts and ends at the same city
● visits every city exactly once
● has a total distance that is less than or equal to a maximum distance parameter
Note that this variation is an NP-Complete problem.
Start with the following database information to represent the graph.
fullGraph([albany, annapolis, atlanta, austin, baton_rouge, boston]).
dist(albany, annapolis, 469).
dist(albany, atlanta, 1356).
dist(albany, austin, 2538).
dist(albany, baton_rouge, 2056).
dist(albany, boston, 224).
dist(atlanta, annapolis, 915).
dist(atlanta, austin, 1318).
dist(atlanta, baton_rouge, 736).
dist(atlanta, boston, 1507).
dist(annapolis, austin, 2168).
dist(annapolis, baton_rouge, 1639).
dist(annapolis, boston, 593).
dist(austin, baton_rouge, 634).
dist(austin, boston, 2729).
dist(baton_rouge, boston, 2225).
Like previous problems, you will probably need to write several predicates, but the
required one that will be used in queries is:
tsp(G, M, C, D): C is a cycle in G that visits every city exactly once
and whose total distance D is less than or equal to M.
Example Query:
?- tsp(G, 5700, C, D).
G = [albany, annapolis, atlanta, austin, baton_rouge, boston],
C = [boston, albany, austin, baton_rouge, atlanta, annapolis, boston],
D = 5640 .
Note that there are multiple possibilities for this query. I just printed one to show the
format.