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.

## Reviews

There are no reviews yet.