1#1
1#1
Introduction to
Object Oriented Programming 2E
Timothy A. Budd
1#1
Chapter 5
1#1
A Case Study : Eight Queens

Statement of the Problem

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

2#2

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.

3#3

CRC Card for Queen

4#4

CRC Card for Queen - Backside

5#5

Initialization

Initialization will set each queen to point to neighbor, and set column value. C++ version is shown:

6#6

Finding First Solution

Finding first solution, in pseudo-code:

7#7

Finding Next Solution

8#8

Test or Advance

9#9

Can Attack

10#10

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.

Final Analysis

• No single controlling program - control is decentralized
• Active objects determine their own actions and behavior.