Section 5.3.2 of the text describes the “Eight Queens Problem”. Read the description of the problem very carefully, but stop reading when the details of the implementation begin to be discussed. I believe that I have a simpler approach. This means you should read through the paragraph that ends with “you need to backtrack, as has already been described.” This is bottom-of-page-177 through the first complete paragraph on page 179.
We will have two classes: a “Board” class to represent the chessboard and a “Queen” class to represent a single Queen.
The Board class could be represented in a number of ways. The most intuitive representation might be a two-dimensional array; however, such an array wastes space because only eight squares out of 64 are used. Instead we will use an STL vector that contains the 8 Queens. Each Queen will be stored in the position of the vector that corresponds to the Queen’s column (i.e., the Queen in column 0 will be stored in position 0 of the vector, the Queen in column 1 will be stored in position 1 of the vector, and so on). Since each Queen will know its own location on the board, this vector will fully specify the state of the board.
Here is the pseudocode that I highly recommend. I have modified it from the pseudocode given in the text after a lot of experimentation with different approaches to determine the simplest approach.
pre: row < BOARD_SIZE && col < BOARD_SIZE
post: places a queen in each column of the calling object, beginning with the column "col", and
considering rows in that column beginning with row "row", in such a way that none of them are
under attack by any others. Returns true if successful, false if no such configuration can be
found
placeQueens(row: integer, col: integer): boolean {
while (unconsidered squares exist in column "col" AND the problem is unsolved) {
Beginning with row "row", find the next row in column "col" that is not under attack
by a queen in an earlier column;
if (such a square exists) {
Set the location of the Queen in column "col" to that square
if (this was the final queen to be placed OR placeQueens(firstRow, col + 1)) {
return true;
} else {
// placing the queen in column "col" into row "row" didn't work, so:
Move the queen in column "col" to the next square in that column
row = queens[col].getRow();
}
}
}
// exited the while loop, which means that all rows in this column have been considered.
return false;
}
#include
#include
using namespace std;
class Queen {
public:
void setRow(int inRow);
int getRow() const;
private:
int row;
};
int Queen::getRow() const {
}
void Queen::setRow(int inRow) {
}
class Board {
public:
static const int BOARD_SIZE = 8;
Board();
void do8Queens();
void display() const;
private:
bool placeQueens(int row, int col);
bool findNextNotUnderAttackSquare(int& row, int col);
bool isUnderAttack(int row, int col);
vector
};
Board::Board() {
queens.resize(BOARD_SIZE);
}
void Board::do8Queens() {
placeQueens(0, 0);
}
bool Board::placeQueens(int row, int col) {
// use the pseudocode above to complete this function.
}
bool Board::isUnderAttack(int testRow, int testCol) {
}
bool Board::findNextNotUnderAttackSquare(int& row, int col) {
}
void Board::display() const {
}
int main() {
Board board;
board.do8Queens();
board.display();
}