Read the introduction to the "Eight Queens Problem". Don't read past where it says "Stop Here". We will be using a slightly different approach.
We will have two classes: a "Board" class to represent the chessboard and a "Queen" class to represent a single Queen.
A Board object 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 which row it is in, this vector will fully specify the state of the board.
Here is the pseudocode that I highly recommend. Note that to simplify the wording we will use the word "safe" to mean "not under attack by a queen in an earlier column".
Hint! My most common response to requests for help on this assignment is, "You should have stayed closer to the pseudocode." You should try to follow the pseudocode as closely as possible. In my solution, every line of the pseudocode corresponds to exactly one line in the solution.
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 {
Beginning with row "row", find the next square in column "col" that is safe;
while (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(0, col + 1)) {
return true;
} else {
// placing the queen in column "col" into row "row" didn't work, so:
(1) Move the queen in column "col" to the next square in that column
(2) row = queens[col].getRow();
// note that these are two separate steps.
}
Beginning with row "row", find the next square in column "col" that is safe;
}
// exited the while loop, which means that all rows in this column have been considered.
return false;
}You must use the following code as a starting point. Do not add anything to the class declarations. Your only task is to complete the definitions of the member functions for the "Queen" and "Board" classes.
Strong Recommendation: Don't wait until you have implemented all of these functions before you start doing your testing! If you write these in the right order, you can exhaustively test each function that you write before you move on to the next one.
Hint: There's no reason to use pointers anywhere in this assignment
#include <iostream>
#include <vector>
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 doQueens();
void display() const;
private:
bool placeQueens(int row, int col);
bool findNextSafeSquare(int& row, int col);
bool isUnderAttack(int row, int col);
vector<Queen> queens;
};
Board::Board() {
queens.resize(BOARD_SIZE);
}
void Board::doQueens() {
if (placeQueens(0, 0)) {
display();
} else {
cout << "No solution found." << endl;
}
}
bool Board::placeQueens(int row, int col) {
// use the pseudocode above to complete this function.
}
bool Board::isUnderAttack(int testRow, int testCol) {
}
// Sets "row" to the row of the next safe square in column col. Important note:
// The first square to be considered will be the given row and column.
// In other words, the given row and col may be the "next safe square".
// returns true if a safe square is found, false if no safe square is found. If
// return value is false, row is undefined.
bool Board::findNextSafeSquare(int& row, int col) {
}
// Displays a visual representation of the current state of the board. For each position
// on the board, displays "X" if a queen is located at that position, otherwise displays
// "_" (underscore).
void Board::display() const {
}
int main() {
Board board;
board.doQueens();
}