3/5/09

Intermediate / Advanced
Programming
Recursion and Backtracking

Lynn Robert Carter

2009-03-03

© Copyright 2009, Lynn Robert Carter

Agenda
 N Queens
+ Finding solutions
+ Backtracking
+ The N Queens solution

Intermediate/Advanced Programming 2
Recursion and Backtracking

1
 3/5/09

The N Queens Puzzle

+ Consider a board, like a chess board, but
one where you can specify the board size
+ How many chess queens can be placed
on this “board” so that no queen can “take”
another?
+ How many different placements of queens
can be made for a given sized board?

Intermediate/Advanced Programming 3
Recursion and Backtracking

A board of size 5

Intermediate/Advanced Programming 4
Recursion and Backtracking

2
 3/5/09

What does “take” mean?

+ In chess a piece “takes” another piece
when it can move to the same square as
the piece it is going to take
+ The various pieces on a chess board
move in very different ways
+ Some pieces, such are rooks (castles) can
move all the way across the board, but
only up, down, left, or right
Intermediate/Advanced Programming 5
Recursion and Backtracking

How does a Queen move?

♕!

Intermediate/Advanced Programming 6
Recursion and Backtracking

3
 3/5/09

The moves of a Queen

♕!

Intermediate/Advanced Programming 7
Recursion and Backtracking

Safe places for a second Queen

♕! ♕!
♕! ♕!
♕!
♕! ♕!
♕! ♕!
Intermediate/Advanced Programming 8
Recursion and Backtracking

4
 3/5/09

Agenda
 N Queens
 Finding solutions
+ Backtracking
+ The N Queens solution

Intermediate/Advanced Programming 9
Recursion and Backtracking

Finding solutions
+ Start in the first row, we
have a choice of five
possible moves
+ Any of these five choices
could lead to a solution
+ To move forward, we
have to choose one and
then see if that can lead
to a solution
Intermediate/Advanced Programming 10
Recursion and Backtracking

5
 3/5/09

The first move

+ To be systematic, pick the
first one; place a queen in
♕!
the first square
+ We know than no other
queen can be in that row
+ So start with the second
row and see which
squares are “safe”

Intermediate/Advanced Programming 11
Recursion and Backtracking

Possible safe places

+ The first column is not
safe
♕!
+ The second square in the
second row is not safe
+ All of the others in the row
are safe
+ Let’s use the first one

Intermediate/Advanced Programming 12
Recursion and Backtracking

6
 3/5/09

Examine row three

+ Which of the squares in
row three are “safe”?
♕!
♕!

Intermediate/Advanced Programming 13
Recursion and Backtracking

Examine row three

+ The only “safe” square in
this situation is the right
♕!
most square ♕!
+ So place a queen there

Intermediate/Advanced Programming 14
Recursion and Backtracking

7
 3/5/09

Examine row four

+ Where are the safe
squares in row four?
♕!
♕!
♕!

Intermediate/Advanced Programming 15
Recursion and Backtracking

Examine row four

+ There is just one possible
square for the fourth row
♕!
+ Once again, place the ♕!
next queen there!
♕!

Intermediate/Advanced Programming 16
Recursion and Backtracking

8
 3/5/09

Examine the last row

+ Once again, there is only
one choice
♕!
♕!
♕!
♕!

Intermediate/Advanced Programming 17
Recursion and Backtracking

A solution
+ Using this process, we
have found a solution
♕!
+ How many more solutions ♕!
are possible?
♕!
♕!
♕!

Intermediate/Advanced Programming 18
Recursion and Backtracking

9
 3/5/09

Agenda
 N Queens
 Finding solutions
 Backtracking
+ The N Queens solution

Intermediate/Advanced Programming 19
Recursion and Backtracking

4 Queens
+ Consider the 4 Queens case
+ There are four possible first
moves

Intermediate/Advanced Programming 20
Recursion and Backtracking

10
 3/5/09

4 Queens row 2 choice

+ Start with a Queen in the
first row and first column
♕!
+ There are just two possible
choices for the second row
+ Let’s pick the first one

Intermediate/Advanced Programming 21
Recursion and Backtracking

4 Queens row 2
+ Given this sized board and
these two queens, where
♕!
can a queen go for row 3? ♕!

Intermediate/Advanced Programming 22
Recursion and Backtracking

11
 3/5/09

4 Queens row 3
+ There is no “safe” move in
this situation, so be have to
♕!
back up and try a different ♕!
choice
+ This “backing up” is known
as “backtracking”
+ So, let’s back up to the most
recent point where we had a
choice, the choice in row 2
Intermediate/Advanced Programming 23
Recursion and Backtracking

Back up to row two

+ We know that the first of
these two choices does not
♕!
lead to a solution
+ Let’s try the second of the
two choices

Intermediate/Advanced Programming 24
Recursion and Backtracking

12
 3/5/09

A second try at row three

+ With queens positioned as
shown here, where are the
♕!
possible “safe” moves in row ♕!
three?

Intermediate/Advanced Programming 25
Recursion and Backtracking

Possible row three moves

+ With queens positioned as
shown here, there is just
♕!
one possible “safe” move, ♕!
so let’s take it

Intermediate/Advanced Programming 26
Recursion and Backtracking

13
 3/5/09

Possible row four moves

+ Where are the “safe” moves
in row four?
♕!
♕!
♕!

Intermediate/Advanced Programming 27
Recursion and Backtracking

Another failure
+ There are no safe moves
here, so… we have to back
♕!
track again ♕!
♕!

Intermediate/Advanced Programming 28
Recursion and Backtracking

14
 3/5/09

Once again at row two

+ Now we know that neither of
the two choices for row 2
♕!
will lead us to a solution
+ Therefore, we must back up
to row 1 and try a different
choice there

Intermediate/Advanced Programming 29
Recursion and Backtracking

Backup all the way to row 1

+ We now know that it is not
possible for 4 Queens to
have a solution with a queen
in the first row and first
column
+ Let’s try the queen in the
first row and second column

Intermediate/Advanced Programming 30
Recursion and Backtracking

15
 3/5/09

4 Queens row 2 choice

+ With a queen in this position
in the first row, there is only
♕!
one choice for row 2
+ So, let’s make that move

Intermediate/Advanced Programming 31
Recursion and Backtracking

4 Queens row 3 choice

+ Queens in these positions
for the first two rows means
♕!
that there is again just one ♕!
choice for row three
+ So, let’s make that move

Intermediate/Advanced Programming 32
Recursion and Backtracking

16
 3/5/09

4 Queens row 4 choice

+ Queens in these positions
for the first three rows
♕!
means once again just one ♕!
choice is possible
+ So, let’s make that move ♕!

Intermediate/Advanced Programming 33
Recursion and Backtracking

4 Queens solution
+ A queen in the first row and
second column leads to a
♕!
solution ♕!
+ How many more solutions
are possible? ♕!
♕!

Intermediate/Advanced Programming 34
Recursion and Backtracking

17
 3/5/09

Number of possible solutions

+ We know about two of the
choices in the first row
+ What is your intuition about
the other two positions?

Intermediate/Advanced Programming 35
Recursion and Backtracking

A tree of possible solutions

♕ ♕ ♕ ♕

♕ ♕ ♕ ♕
♕ ♕ ♕ ♕ 12 more
not shown

♕ ♕ ♕ ♕
♕ ♕ ♕ ♕ 60 more
♕ ♕ ♕ ♕
not shown

♕ ♕ ♕ ♕
♕ ♕ ♕ ♕ 252 more
♕ ♕ ♕ ♕
♕ ♕ ♕ ♕ not shown

Intermediate/Advanced Programming 36
Recursion and Backtracking

18
 3/5/09

A solution strategy
+ Build a tree of all possible valid queen
placements
+ Traverse the whole tree
+ Whenever there is a board where the
number of queens is equal the number of
rows in the board, add that board to a
collection of solutions

Intermediate/Advanced Programming 37
Recursion and Backtracking

Possible valid placements?

+ Assume you are given a valid board and a
row number where you are to try to place
as many queens as possible
+ How can you do this?

Intermediate/Advanced Programming 38
Recursion and Backtracking

19
 3/5/09

Possible valid placements

+ Perform a loop that iterates once for each
possible placement in the new row using
the index col
+ Make a temporary copy of the board
+ Try to place the queen in the columns
specified by col
+ If that placement is valid, use it to try to place
queens in the rest of the rows (recursively)
Intermediate/Advanced Programming 39
Recursion and Backtracking

Possible placement example

♕ ♕ ♕ ♕

♕ ♕ ♕ ♕
♕ ♕ ♕ ♕

Intermediate/Advanced Programming 40
Recursion and Backtracking

20
 3/5/09

addQueen
/**
* Method to add a Queen to the board
* @param b The Board
* @param rowNum The starting row number to try to add the queen
*
* @return The board after placing the Queen, if possible else null
*/
public Board addQueen(Board b, int rowNum) {
// base case: number of Queens on the board is equal to the board size
if([Link]() == [Link]())
return b;

for(int x =0; x < [Link](); x++){

Board tempBoard = new Board(b);

// try to place the queen in the board at column x within row, rowNum
if([Link](new [Link](rowNum, x))){
// If it was added successfully
// recursively try adding a queen into the next row
Board nextBoard = addQueen(tempBoard, rowNum+1);

// If it comes back null, no solution is possible

if(nextBoard != null)
// The board is not null, so this is a solution
return nextBoard;
}
}
return null;
}

Intermediate/Advanced Programming 41
Recursion and Backtracking

getAllSolutions
/**
* Method to get all possible solutions to the Queens problem
*
* @param b The board to place the Queens at
* @param c All possible boards
* @param rowNum The initial row number to start placing queens
*/
public void getAllSolutions(Board b, Collection<Board> c, int rowNum){

if(rowNum < [Link]()){

for(int x =0; x< [Link](); x++){
Board tempBoard = new Board(b);

if([Link](new [Link](rowNum, x))){

// a queen is placed at that row
// recursively call the method on the next row
getAllSolutions(tempBoard, c, rowNum+1);
}
}
// getting here means that we have run past the end of the row
// so we return without adding any more boards to the collection
return;
}
// add the solved board to the Collection of boards
// this only happens when rowNum >= [Link]()
[Link](b);
}

Intermediate/Advanced Programming 42
Recursion and Backtracking

21
 3/5/09

The Class Design of NQueens

+ The program consists of
+ A class that defines the board (Board)
+ A class that solve the problem (NQueens)
+ A class that implements a Swing GUI window
(NQueensSwing)
+ A mainline class for the Swing version of the
puzzle solver (NQueensGUI)
+ A mainline class for a text version (Driver)

Intermediate/Advanced Programming 43
Recursion and Backtracking

The NQueen Board-1

public class Board {
protected enum BoardState implements Cloneable {
UNTHREATENED, THREATENED, QUEEN
};

protected BoardState[][] board;

private int n;

private int numQueens;

public static class Position {

int x = 0, y = 0;

public Position(int i, int j) {

x = i;
y = j;
}

public boolean equals(Position p) {

return x == p.x && y == p.y;
}
}

public int getSize(){

return this.n;
}

Intermediate/Advanced Programming 44
Recursion and Backtracking

22
 3/5/09

The NQueen Board-2

/**
* Constructs an empty board sizeXsize
*
* Complains if you attempt to construct a negative board Boards of size 0
* are allowed
*/
public Board(int size) {
if (size < 0) {
[Link]("Negative boards are not allowed.");
return;
}

n = size;
numQueens = 0;
board = new BoardState[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = [Link];
}

public Board(Board b) {
board = new BoardState[b.n][b.n];

for (int i = 0; i < b.n; i++)

for (int j = 0; j < b.n; j++)
board[i][j]=[Link][i][j];
n = b.n;
numQueens = [Link];
}

Intermediate/Advanced Programming 45
Recursion and Backtracking

isThreatened and more

/**
* Determines if a position can be reached in one or zero moves by any of
* the queens currently on the board
*
* @param p
* the position to determine the state of
* @return true if Position p is being threatened
*/
public boolean isThreatened(Position p) {
return board[p.x][p.y] != [Link];
}

/**
* accessor for the number of queens currently placed on the board
*/
public int numQueens() {
return numQueens;
}

/**
* returns true if the maximum number of queens have been placed.
*/
public boolean done() {
if (n < 1 || n == 2 || n == 3)
return (numQueens == 0);
return (numQueens == n);
}

Intermediate/Advanced Programming 46
Recursion and Backtracking

23
 3/5/09

place
/**
* Places a queen on the board at Position P if that is an empty
* unthreatened place
*
* @param p
* the position to place the queen in
*
* @return true if placement is sucsessful
*/
public boolean place(Position p) {
if (board[p.x][p.y] != [Link])
return false;

// mark the row and col as threatened

for (int i = 0; i < n; i++) {
board[p.x][i] = [Link];
board[i][p.y] = [Link];
}

// mark the diagonals as threatened

for (int x = p.x, y = p.y; x < n && y < n; x++, y++) board[x][y] = [Link];
for (int x = p.x, y = p.y; x >= 0 && y >= 0; x--, y--) board[x][y] = [Link];
for (int x = p.x, y = p.y; x >= 0 && y < n; x--, y++) board[x][y] = [Link];
for (int x = p.x, y = p.y; x < n && y >= 0; x++, y--) board[x][y] = [Link];

board[p.x][p.y] = [Link];
numQueens++;

return true;
}

Intermediate/Advanced Programming 47
Recursion and Backtracking

Agenda
 N Queens
 Finding solutions
 Backtracking
 The N Queens solution

Intermediate/Advanced Programming 48
Recursion and Backtracking

24
 3/5/09

A sample solution
+ Download the NQueens archive from the
blackboard and get it to work
+ A solution written by Hatem Alismail
+ Study the solution and be able to answer
some questions about this code

Intermediate/Advanced Programming 49
Recursion and Backtracking

Intermediate / Advanced
Programming
Recursion and Backtracking

Lynn Robert Carter

2009-03-03

© Copyright 2009, Lynn Robert Carter

25