Introduction to Object Oriented Programming, 3rd Ed
Chapter 6
A Case Study : Eight Queens
Outline
 Statement of the Problem
 OOP Approach
 Observations
 Pointers
 CRC Card for Queen
 CRC Card for Queen  Backside
 Initialization
 Finding First Solution
 Advancing to Next Position
 Printing Solution
 Can Attack
 The Last Queen
 Chapter Summary
Source Code
Other Material
 A printer friendly version of all slides
 HTML page for queen program in Java
(not available on CD, see explanation)
 A puzzle related to the 8queens is the knightstour problem.
While slightly more advanced, in Chapter 18 we will introduce
the idea of frameworks. In another book I have written an
example backtracking framework illustrated
using this puzzle.
Intro OOP, Chapter 6, Slide 1
Statement of the Problem
Problem  how to place eight queens on a chessboard so that no two queens
can attack each other:
Intro OOP, Chapter 6, Slide 1
OOP Approach
More than just solving the problem, we want to solve the problem in an OOP
manner.

Structure the program so that the data values themselves discover the
solution.

Similar to creating a universe and setting it in motion.

No single controlling manager.
Intro OOP, Chapter 6, Slide 2
Observations
Here are a few observations we can make concerning this problem:

Queens can be assigned a column, problem is then to find row positions.

One obvious behavior is for a queen to tell if it can attack a given position.

Can structure the problem using generators  each queen can be asked to
find one solution, then later be asked to find another solution.
Intro OOP, Chapter 6, Slide 3
Pointers
We can make each queen point to the next on the left, then send messages only
to the rightmost queen. Each queen will in turn send messages only to the
neighbor it points to.
Intro OOP, Chapter 6, Slide 4
CRC Card for Queen
Intro OOP, Chapter 6, Slide 5
CRC Card for Queen  Backside
Intro OOP, Chapter 6, Slide 6
Initialization
Initialization will set each queen to point to a neighbor, and set column
value. C++ version is shown:
main() {
Queen * lastQueen = 0;
for (int i = 1; i <= 8; i++) {
lastQueen = new Queen(i, lastQueen);
if (! lastQueen>findSolution())
cout << "no solution";
}
if (lastQueen>first())
lastQueen>print();
}
Queen::Queen (int col, Queen * ngh)
{
column = col;
neighbor = ngh;
row = 1;
}
Intro OOP, Chapter 6, Slide 7
Finding First Solution
Finding first solution, in pseudocode:
function queen.findSolution > boolean
while neighbor.canAttack (row, column) do
if not self.advance then
return false;
// found a solution
return true;
end
We ignore for the moment the question of what to do if you don't have
a neighbor
Intro OOP, Chapter 6, Slide 8
Advancing to Next Position
function queen.advance > boolean
if row < 8 then begin
row := row + 1;
return self.findSolution
end
// cannot go further, move neighbor
if not neighbor.advance then
return false
row := 1
return self findSolution
end
Intro OOP, Chapter 6, Slide 9
Printing Solution
Just recursively ripple down the list of queens, asking each to
print itself.
procedure print
neighbor.print
write row, column
end
Intro OOP, Chapter 6, Slide 10
Can Attack
function canAttack(r, c)
if r = row then
return true
cd := column  c;
if (row + cd = r) or (row  cd = r) then
return true;
return neighbor.canAttack(r, c)
end
For a diagonal, the difference in row must equal the difference
in columns.
Intro OOP, Chapter 6, Slide 11
The Last Queen
Two approaches to handling the leftmost queen 

Null pointers  each queen must then test for null pointers before sending
a message

Special ``sentinel'' value  indicates end of line for queens
Both versions are described in text.
Intro OOP, Chapter 6, Slide 12
The complete solutions in each language are not described in the slides,
but are presented in detail in the text.
A Java applet version is available.
Chapter Summary
Important not for the problem being solved, but how it is solved.

Solution is the result of community of agents working together

No single controlling program  control is decentralized

Active objects determine their own actions and behavior.
Intro OOP, Chapter 6, Slide 13