COMP 333
Prolog Project #1: Eight Queens
Part 1: Backtracking Based Solution for Eight Queens in Java
In Part 2 of this project, you will write a Prolog program to solve the Eight Queens problem. But before
trying to solve it in Prolog, you will first solve it in Java. The reason for this is that you first need to
understand the problem and its solution without trying to learn Prolog at the same time. Another
eason is that solving it in Java requires you to implement backtracking explicitly. This experience will be
useful when you solve in Prolog since Prolog provides backtracking automatically as part of its
unification and backtracking search strategy.
Java Solution
Here is a description of the solution to the Eight Queens problem for implementation in Java. We will
define the size of the board by a variable named n:
int n;
We will set n to 8 to represent a traditional chess board holding 8 queens. But the value can be changed
later to find solutions to a generalized version of the problem with a different number of queens.
Tracking Queen Positions
The goal of the program is to find one or more solutions to the problem of positioning all queens on the
oard such that no queen attacks another (no conflicts). There are a total of n queens, and we will find
the solution by positioning the queens one column at a time. For each column, we will choose a row
position for the queen in that column and check that the position creates no attacks or conflicts for any
previously positioned queen. When we successfully position the last queen in column n-1, then we have
“solved” the problem by finding a solution. We will keep track of the cu
ent solution with an a
ay of n
elements, where each index represents a column and the value at that index represents the row
position of the queen for that column.
int [] queensPositions;
The initial value of the a
ay will be all positions marked -1.
{ -1, -1, -1, -1, -1, -1, -1, -1 }
This value indicates that none of the queens have been given a position yet. Later on, positions of
queens will be marked in each column. For example, the a
ay
{ 7, 3, 0, 2, 5, 1 ,6 , -1 }
means queen in column 0 is in row 7, queen in column 1 is in row 3, queen in column 2 is in row 0, and
so on.
Tracking Tried and Untried Row Positions in Each Column
The solution proceeds by finding a row position for the queen in a specific column that has no conflicts
with the queens already positioned in previous columns, then moving on to the next column. If we try a
ow position for some column but it generates conflicts, we have to mark that row position for that
column as tried and try another untried row position in the same column. So for each column, we have
to keep track of which rows in that column have been tried so far and which rows haven’t. Since rows
are tried in numerical order, for each column we only have to record the index of the first untried row
for that column.
int [] firstUntried;
For example, the a
ay
{ 3, 4, 2, 6, 0, 0, 0, 0 }
means that in column 0, rows 0 through 2 have already been tried, so the first untried row is row 3, and
similarly for other columns. A value of 0 means none of the rows have been tried yet. A value of n
means that all the rows have been tried and we will soon be backtracking to keep the search for a
solution alive.
Functions on Queen Position A
ay
void initQueensPositions()
allocate space for the a
ay based on value of n
set all position values to -1 to indicate no queen positions have been chosen yet
oolean hasConflict(int a, int b, int bpos)
check for conflicts between columns a and b
assume a < b
get cu
ent queen position for column a from queensPositions a
ay
find out if row position bpos in column b has a conflict with column a
if has conflict return true
if no conflict return false
see figure below for more visualization
oolean hasConflictCumulative(int b, int bpos)
check for conflicts between column b and all previous columns 0 through b – 1
use previous function to check for conflicts with specific columns
void setQueenPosition(int col, int pos)
set queen position for column col to be pos
int getQueenPosition(int col)
get queen position for column col and return it
String getPositionsSnapshot()
create a string showing the cu
ent values of all queen positions for all columns
so that it can be printed out, this is for tracing and debugging
Functions for Managing Tried and Untried Row Positions or States For Each Column
void initStates()
allocate space for the firstUntried a
ay based on value of n
set all index values to 0 to indicate no row positions have been tried yet
int getUntriedPosition(int col)
return the value of the first untried row position for that row
if the first untried row equals n, then there are no remaining untried rows, so return -1
otherwise return the value of the row position
void setPositionTried(int col)
increment the first untried row position for that column
this indicates that cu
ent row position is marked tried and the next try will use next row
void setAllPositionsUntried(int col)
reset first untried row position for that column back to 0
this means that we are erasing the tried positions for that column and starting over
this happens during backtracking when we erase all the tries for the cu
ent column
and backup to the previous column
How to Check for Conflicts Between Columns
Solving the puzzle proceeds by setting the position of the queen for each column, one column at a time.
Supposing we are working on column c, we pick an unused row r for column c as a potential position for
the queen in column c. We then have to check if row r in column c creates a conflict with any of the
previous columns 0 through c-1.
• Column Conflict: there can be no column conflicts in this solution because there is only one
queen per column
• Row Conflict: if we pick row r for column c, then there is a row conflict if any of the previous
columns 0 through c-1 also have row value r.
• Diagonal Conflict: let a and b be two column indexes and assume a
. Now let arow and
ow
e the row positions for the two columns. Let diff = b – a, the difference between the column
indexes. Then there is a diagonal conflict between columns a and b if
ow = arow +/- diff.
Another way of saying it: if
ow-arow = +/- (b-a), then there is a diagonal conflict between
columns a and b.
• See visualization below
So when we choose a position for cu
ent column, we confirm that there are no conflicts with the row
positions of any of the previous columns 0 through cu
ent column - 1. If there are no conflicts, we
position the queen at that position for the cu
ent column and move to the next column. If there are
conflicts, we must set the position to “tried” and try another position for the same column. See the
complete “solve” algorithm above.
Example Visualization
Look at the following chess board. We are cu
ently considering how to place the queen into column 3,
(CC or cu
ent column = 3) and the cu
ent candidate for row position is row 4, indicated by “Q?”. Before
confirming our placement, we must check for potential conflicts in columns 0, 1, and 2. There are no
column conflicts possible, but we must check for row and diagonal conflicts. The positions of the D?
marks indicate conflicts. Columns 4 through 7 have not yet been reached so they can be ignored.
0
1 D?
2 D?
3 D?
4 R? R? R? Q?
5 D?
6 D?
7 D?
XXXXXXXXXX
CC
Let a be one of the column indexes 0 through 2 and let b be the cu
ent column index, in this case 3. Let
qp[a] be the row position for column a and qp[b] be the row position for column b.
Example: check for conflicts between columns a = 0 and b = 3
Row conflict:
if qp[a] == qp[b] then there is a row conflict
For example, if qp[0] and qp[3] both have value 4, then there is a row conflict
Diagonal conflict:
Let diff = b – a, the difference in column indexes
diff = b – a = 3 – 0 = 3
Let pdiff = qp[b] – qp[a], the difference between row positions
If qp[0] is 1 and qp[3] is 4, then pdiff = 3 and pdiff = diff
If qp[0] is 7 and qp[3] is 4, then pdiff = -3 and pdiff = -diff
So if pdiff = +diff or –diff, then there is a diagonal conflict between the columns
So when checking for conflicts for column 3, you must perform a separate check for all previous columns
0, 1, and 2.
Note that simply finding a conflict does not trigger backtracking. Finding a conflict only triggers a choice
of another position for the cu
ent column. Only