Assignment 2 n-Queens problem, for 1 ≤ 𝑛 ≤ 15

1
CMPS 12B
Introduction to Data Structures
Programming Assignment 2
In this project, you will write a Java program that uses recursion to find all solutions to the n-Queens
problem, for 1 ≤ 𝑛 ≤ 15. (Students who took CMPS 12A from me worked on an iterative, non-recursive
approach to this same problem. You can see it at https://classes.soe.ucsc.edu/cmps012a/Spring18/pa5.pdf.)
Begin by reading the Wikipedia article on the Eight Queens puzzle at:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
In the game of Chess a queen can move any number of spaces in any linear direction: horizontally,
vertically, or along a diagonal.

The Eight Queens puzzle is to find a placement of 8 queens on an otherwise empty 8 × 8 chessboard in
such a way that no two queens confront each other. In particular, no two queens lie on the same row,
column or diagonal. One solution to this problem is pictured below.

The n-Queens problem is the natural generalization, in which n queens are placed on an 𝑛 × 𝑛 chessboard
in such a way that no two queens lie on the same row, column or diagonal. There are many ways of solving
this problem, some of which are described in the Wikipedia article linked above. Our algorithm will
2
recursively locate a square on the next row down, where a queen can be placed, without being attacked by
(or attacking) a previously placed queen. The illustration below is a partial box trace of the case 𝑛 = 4.
At the top (level 0) of the recursion, we have placed no queens, which is illustrated by an empty 4 × 4
chessboard. Notice that initially there are no restrictions on where a queen can be placed on row 1. At level
1 of the recursion therefore, we place a queen on each of the 4 safe positions in row 1. These 4 queen
placements generate 4 separate recursive calls.
 2
 0 1 1 0
 ⋮ ⋮
 1 0 0
 X
 1 0
 X
 1
In the above illustration we have color-coded the queens, so that the queen on row 1 is blue, that on row 2
is red, that on row 3 is green and the queen on row 4 is black. For each queen placement, it is necessary to
keep track of which squares it attacks on the rows below it. To this end, the squares on rows 2, 3 and 4
Q
-1 -1
-1 -1
-1 -1
Q
-1 -1 -1
-1 -1
-1
Q
-1 -1 -1
-1 -1
-1
Q
-1 -1
-1 -1
-1 -1
Q
-1 -1 -1 Q
-1 -1 -2
-2 -1
Q
Q -1 -1
-1 -2 -1
-2 -1 -1
Q
Q -1 -1
-1 -2 -1 -1
-1 -1 -2
Q
-1 -1 -1 Q
Q -1 -1 -2
-1 -3 -1
Q
Q -1 -1
-1 -2 Q -1
-2 -1 -2 -2
Q
-1 -1 -1 Q
Q -1 -1 -2
-1 -3 Q -1
3
which are attacked by the blue queen, are shaded blue, and no subsequent queens can be placed on those
squares. For instance, after placing a blue queen on row 1, column 2, we have:
Observe that there is only one safe square in row 2, namely square (2, 4). Therefore the placement of a
queen on (1, 2) generates just one recursive call, and this box has only one child in the box trace, in which
a red queen is placed on (2, 4). The squares on rows 3 and 4 that are attacked by the red queen are of course
shaded red. Note however that two of these squares ((3, 4) and (4, 2)) are attacked by both the red queen
and the blue queen, and are accordingly shaded purple (since red+blue=purple).
In what follows, we will see that it is most important to keep track of the number of queens attacking a
given square from a row above. We signify this in the box trace by placing the negative of that number in
the given square. Thus (3, 2) contains -1 since it is attacked by only the blue queen, (3, 3) contains -1 since
it is attacked by only the red queen, and (3, 4) contains -2 since it is attacked by both.
If we succeed in placing a queen on row 4, then we have found a solution to 4-queens, and the algorithm
returns value 1 from that box. If the next row contains no safe squares, then the box generates no recursive
calls, and returns 0. For instance, after placing a red queen on (2, 2) below, row 3 has no safe square on
which to place a queen. We signify this by placing an X under the dead-end box.
In general, each box returns the sum of the returned values of each of its children. As an exercise, complete
the box trace on the preceding page by determining the children of the boxes with the symbol ⋮ under
them. (Don't try to determine the colors, which were given here only for illustration, but do try to determine
the number of queens attacking each square from above.) As a further (more challenging) exercise, try to
construct a complete box trace for the case 𝑛 = 5, which has 10 solutions.
Let 𝑎(𝑛) denote the number of solutions to the n-Queens problem. Much research has been done on the
sequence (𝑎(𝑛))
𝑛=0
∞
, which begins (1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, … ). See the article
1 2 3 4
1 Q
2 -1 -1 -1
3 -1 -1
4 -1
1 2 3 4
1 Q
2 -1 -1 -1 Q
3 -1 -1 -2
4 -2 -1
1 2 3 4
1 Q
2 Q -1 -1
3 -1 -2 -1 -1
4 -1 -1 -2
4
https://oeis.org/A000170 for links to some of this work. The algorithm we are studying in this project is
practical for values of 𝑛 up to 𝑛 = 15, or 16 at most. Beyond that, it slows significantly. (I managed to
compute 𝑎(16) = 14,772,512 in under 2 minutes on my Windows machine.) The iterative algorithm we
studied in CMPS 12A was useful only up to about 𝑛 = 13.
Program Operation
Your program for this project will be called Queens.java. You will include a Makefile that creates an
executable Jar file called Queens, allowing one to run the program by typing Queens at the command line.
Your program will read an integer n from the command line, indicating the size of the Queens problem to
solve. The program will operate in two modes: normal and verbose (which is indicated by the command
line option "-v"). In normal mode, the program prints only the number of solutions to n-Queens. In verbose
mode, all solutions to n-Queens will be printed in the order they are found by the algorithm, and in a format
described below, followed by the number of such solutions. Thus to find the number of solutions to 8-
Queens you will type:
% Queens 8
To print all 92 unique solutions to 8-Queens type:
% Queens –v 8
If the user types anything on the command line other than the option –v and a number 𝑛, the program will
print a usage message to stderr and quit. A sample session is included below (remember that % is the unix
prompt and you do not type it.)
% Queens
Usage: Queens [-v] number
Option: -v verbose output, print all solutions
% Queens blah
Usage: Queens [-v] number
Option: -v verbose output, print all solutions
% Queens 4
4-Queens has 2 solutions
% Queens -v 4
(2, 4, 1, 3)
(3, 1, 4, 2)
4-Queens has 2 solutions
% Queens -v 5
(1, 3, 5, 2, 4)
(1, 4, 2, 5, 3)
(2, 4, 1, 3, 5)
(2, 5, 3, 1, 4)
(3, 1, 4, 2, 5)
(3, 5, 2, 4, 1)
(4, 1, 3, 5, 2)
(4, 2, 5, 3, 1)
(5, 2, 4, 1, 3)
(5, 3, 1, 4, 2)
5-Queens has 10 solutions
%
5
Solutions are encoded as an 𝑛-tuple where the 𝑖
th element is the column number of the queen residing in
row 𝑖. For instance, in the case 𝑛 = 4, the 4-tuple (2, 4, 1, 3)encodes the solution:
and the 4-tuple (3, 1, 4, 2) encodes the other solution:
Observe that these solutions are given in the order in which they would be found by our algorithm, as
illustrated by the (partial) box trace on page 2 of this document, provided we work from left to right in each
row. It is recommended that you write helper functions to perform basic subtasks such as printing the usage
message then quitting.
Program Representation of the Chessboard
Your program will represent an 𝑛 × 𝑛 chessboard by a 2-dimensional int array of size (𝑛 + 1) × (𝑛 + 1).
The extra row and column are there so row and column numbers in the array correspond directly with row
and column numbers on the chessboard. Specifically, if the array is called B, then B[i][j] corresponds
to the square in row i, column j of the chessboard. The following encoding of chessboard states will be
used. For 1 ≤ 𝑖 ≤ 𝑛 and 1 ≤ 𝑗 ≤ 𝑛,
𝐵[𝑖][𝑗] = {
1 if square (𝑖,𝑗) contains a queen
0 if square (𝑖,𝑗) is empty, and not under attack from any square above it
−𝑘 if square (𝑖,𝑗) is under attack from 𝑘 queens lying above it
In this context, "above" means "having a smaller row number". Furthermore, since column 0 does not
correspond to anything on the chessboard, we will use it to encode a solution in the required format. For
1 ≤ 𝑖 ≤ 𝑛 and 𝑗 = 0,
𝐵[𝑖][0] = {
0 if row 𝑖 is contains no queen
𝑗 if square (𝑖,𝑗) contains a queen
Thus, to print out a solution, enter a loop that prints: (𝐵[1][0], 𝐵[2][0], 𝐵[3][0], … , 𝐵[𝑛][0]). The contents
of row 0 are not specified, so you can put anything you like in 𝐵[0][0 ⋯ 𝑛].
You may wish to write a helper function to initialize this array to all zeros, though this is not required. Your
program will contain two functions with the following headings:
1 2 3 4
1 Q
2 Q
3 Q
4 Q
1 2 3 4
1 Q
2 Q
3 Q
4 Q
6
static void placeQueen(int[][] B, int i, int j)
and
static void removeQueen(int[][] B, int i, int j)
The first function increments 𝐵[𝑖][𝑗] from its initial value of 0 to 1, and sets 𝐵[𝑖][0] to 𝑗, thus indicating
the existence of a queen on square (𝑖,𝑗). It will also will also decrement 𝐵[𝑘][𝑙] for every square (𝑘, 𝑙)
under attack from the new queen at (𝑖,𝑗), where 𝑖 < 𝑘 ≤ 𝑛 and 1 ≤ 𝑙 ≤ 𝑛. The second function undoes
everything the first function does. So, it decrements 𝐵[𝑖][𝑗] from 1 to 0, resets 𝐵[𝑖][0] from 𝑗 to 0, and
increments 𝐵[𝑘][𝑙] for every square (𝑘, 𝑙) no longer under attack from the now absent queen at (𝑖,𝑗), where
𝑖 < 𝑘 ≤ 𝑛 and 1 ≤ 𝑙 ≤ 𝑛. All of this serves to implement the encoding of states described above. Your
program will also contain a function with the heading
static void printBoard(int[][] B)
that prints out a solution to 𝑛-queens in the format described above. Finally, your program will contain a
function with the heading
static int findSolutions(int[][] B, int i, String mode)
that implements the recursive algorithm we have been describing. If the string argument mode has the value
"verbose", then findSolutions() will print out solutions as it finds them by calling the function
printBoard(). If mode has any other value, findSolutions() will print nothing. The int returned by
findSolutions() is the number of solutions to 𝑛-queens that have queens placed on rows 1 to (𝑖 − 1),
as represented by the current state of array B[][]. A top level call to findSolutions() that does not
print solutions would be findSolutions(B, 1, ""). High level pseudo-code for this function is given
below.
1. if 𝑖 > 𝑛 (a queen was placed on row 𝑛, and hence a solution was found)
2. if we are in verbose mode
3. print that solution
4. return 1
5. else
6. for each square on row 𝑖
7. if that square is safe
8. place a queen on that square
9. recur on row (𝑖 + 1), then add the return value to an accumulating sum
10. remove the queen from that square
11. return the accumulated sum
Your program's function main() will read the command line arguments, and determine the value of 𝑛, and
what mode (normal or verbose) to run in. It will initialize an int array of size (𝑛 + 1) × (𝑛 + 1) to all zeros,
call function findSolutions() on this array in the correct mode, then print out the number of solutions
to 𝑛-queens that were found.
What to turn in
Write a Makefile for this project that creates an executable Jar file called Queens, and that includes a clean
target (as in lab1). Submit the files Makefile and Queens.java to the assignment name pa2. As always start
early and ask questions in lab sessions and on Piazza.