# A Case Study : Eight Queens

Outline

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 8-queens is the knights-tour 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.

# Statement of the Problem

Problem - how to place eight queens on a chessboard so that no two queens can attack each other:

# 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.

# 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.

# 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.

# 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;
}

```

# Finding First Solution

Finding first solution, in pseudo-code:

```
function queen.findSolution -> boolean

while neighbor.canAttack (row, column) do
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

```

if row < 8 then begin
row := row + 1;
return self.findSolution
end

// cannot go further, move neighbor
return false

row := 1
return self findSolution

end
```

# Printing Solution

Just recursively ripple down the list of queens, asking each to print itself.
```
procedure print
neighbor.print
write row, column
end

```

# 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.

# 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.