COMP 333
Prolog Project #1: Eight Queens
Part 2: Prolog Solution
After completing Part 1 in Java, you should understand the Eight Queens problem and the general logic
of backtracking as a solution technique. Writing a solution in Prolog is going to be very different because
Prolog is a logic or predicate based language, plus its interpreter or listener has the unification plus
acktracking algorithm built in, so the programmer does not have to define it.
In Part 2, your assignment is to write a Prolog version of the same program Most of this document is
ackground and discussion, please read it through before starting to write you code. It contains some
helpful Prolog hints. A detailed description of the assignment is found at the end of the document.
Prolog does not directly support data structures like a
ays. However, Prolog makes frequent use of lists,
and provides them as a fundamental built-in data type. Lists are the best way to represent the solution.
We can create a list of length 8 where each index represents a column and each value represents the
queen’s row position for that column, which we can treat similarly to a one-dimension a
ay. But we no
longer need to keep track of which row positions have been tried and which haven’t, as we did in Java.
Prolog maintains its own internal bookkeeping to support backtracking, the programmer doesn’t need
to keep track.
We must still define appropriate predicates to define for Prolog how to recognize conflicts between
queen positions in two different columns and how to recognize when all conflicts have been cleared.
An important way that the Prolog solution is different from the Java version is that in Java, the
programmer directly constructs a potential solution then changes it to remove conflicts, while in Prolog,
we describe a more general template for an acceptable solution and let Prolog search for a value with
no conflicts. In other words, in the Prolog solution, the programmer is not explicitly moving values
around and changing the positions of the queens. Rather, the programmer gives Prolog a general
description of what a solution looks like, then lets Prolog check possible solutions against the constraints
until it finds a solution that satisfies all the constraints.
Approach to Finding a Solution
We can divide problems in computer science into two main classes based on the time complexity of the
est known solution algorithm: the P (polynomial or efficient) class and the NP (nondeterministic
polynomial or inefficient) classes.
An algorithm that belongs to P is called efficient, which means the time complexity of finding the
solution is a polynomial function of the size of problem n, also written O(nk).
NP algorithms in contrast are inefficient, which means the time complexity is exponential, written O(kn).
NP-complete problems are an important subset of the larger NP class but the difference between NP
and NP-complete is not discussed here.
Another way to describe the difference between P and NP problems is that P class problems have
solutions that can be constructed in polynomial time, while NP problem solutions require exponential
time. But to say that it takes exponential time to find a solution is another way of saying that we really
can’t do any better than guessing a solution. If finding the solution takes exponential time, we are really
doing no better than trying every possible solution and keep trying until we find one that works.
The Eight Queens problem is known to be an NP-complete problem. An obvious and simple approach to
writing a Prolog solution is as follows:
• Define form of solution (for example, a list of length 8 with possibly other properties)
• Identify pool of potential solutions (for example, permutations of a specific list)
• Define constraint check for any two columns (row, column, and diagonal constraints)
• Enumerate all pairs of columns to check
• Identify solutions as potential solutions that satisfy all the constraints
The complete Prolog code for this solution is provided below. This is a useful example to give you insight
into the problem and its solution. But the program you will write for your assignment will use a different
approach described later in the document.
Identify Potential Solutions
A Prolog solution will depend on unification and backtracking to examine potential solutions and
ecognize an actual solution when it is checked. So we want to start our Prolog program with a pool of
potential solutions.
One way is to use the constant list
[0,1,2,3,4,5,6,7]
where each element has a value equal to its index. This has the co
ect form of an 8q solution, but it is
not an actual solution because it contains conflicts. To use this as a starting point and convert it into a
pool of potential solutions, we can use the built in permutation/2 predicate. Experiment with
permutation/2 for a moment to get familiar with how it works.
Examples
?- permutation( [1,2,3], [3,1,2] ).
true . % 2nd list is a permutation of the 1st
?- permutation( [1,2,3], [4,5,6] ).
false. % 2nd list is not a permutation of the 1st
?- permutation( [1,2,3], X ).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ; % X is unified to some permutation
false. % there are 3! = 6 possible solutions
% backtracking eventually finds all 6
First argument is a list, second argument is a permutation of the first. If we use a variable for the 2nd
argument, then unification and backtracking will step us through all possible permutations of the first
argument. So
permutation( [0, 1, 2, 3, 4, 5, 6, 7] , QP ).
is goal that defines a pool of potential 8q solutions consisting of every permutation of the original list.
This goal can be used as the starting point for a query in the finished program to find solutions. The
variable QP will be unified to these permutations one at a time, and the interpreter will backtrack if
equested to find another one, until the user stops or it runs out of permutations. There are 8! = 40,320
possible permutations, so this goal defines 40,320 potential solutions to our problem.
Another way to define an initial pool of potential solutions is to be less restrictive and accept any list of 8
elements where each element has a value from 0 to 7. There are 88 = 16,777,216 potential solutions in
the pool in this case. The permutation approach has two advantages: (1) it’s a lot smaller so there will
e less pointless searching to find a solution, and (2) it automatically eliminates row conflicts, since in
the permutation approach, no two columns can have the same value.
Such a constraint can still be useful. But the easiest way to write this in Prolog will use the clpfd li
ary
which will be discussed later. So using the permutation/2 predicate is the best way for now.
List of Row Values vs List of (column,row) Pairs
The list format described above is the best way to represent potential solutions. But note that the values
in the list represent row positions for each column, while the columns themselves are not represented
explicitly, they are represented only as index values into the list. The list
[ 5, 3, 7, 0, 2, 1, 4, 6 ]
means that the row value for column 0 is 5, the row value for column 1 is 3, etc. This format will work
fine for most solutions. But we will have to be careful performing recursion on the list in this case. If we
start
eaking the list apart into head and remainder, we will lose the index information and will no
longer know which column each position in the list represents.
For this reason, some solutions start off with a list format that explicitly represents each column, row
pair as a sublist of 2 elements. The above list would be rewritten like this:
[ [0,5] , [1,3] , [2,7] , [3,0] , [4,2] , [5,1] , [6,4] , [7,6] ]
So now the solution is represented as a “list of lists”, each element is 2-element list representing a
[column, row] pair. The main advantage of this approach is that we will always know which row belongs
to which column, even if we
eak up the list into smaller parts during recursion. The disadvantage is
that we can no longer use the permutation/2 predicate to define a pool of potential solutions. For now
we will continue to use the original pool of solutions based on permutation/2.
Confirm No Conflicts Between Columns
It will be useful to define a predicate that isolates the check for no conflict in a potential solution for any
two columns. We will call this predicate nc/3 for “no conflicts”
nc( L, A, B)
The first argument is the solution list, and the 2nd and 3rd arguments are indexes within the list to check
for conflicts. Definition of this predicate is left as an exercise. Hint: use the nth0/3 built in predicate to
find the element of a list at a specific index.
Also see discussion below, there is an alternative way to define nc/3, you’ll want to consider both
versions.
Simple Solution For Reference
Use No Conflict Checker on All Pairs of Columns
The last step to construct a complete simple solution is to explicitly apply the nc/3 predicate to every
possible pair of columns. Note that this is not the approach that you will use for your final version of the
project. But try it out as an exercise to help understand how the Prolog solution works.
For