Assignment 6.1 [30 points]

Full documentation is required on this assignment.

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.

Note that to simplify the wording we will use the word "safe" to mean "not under attack by a queen in an earlier column".

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 row 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 place OR placeQueens(0, 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(); } Beginning with row "row", find the next row 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.

Hint: There's no reason to use pointers anywhere in this assignment

#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 findNextSafeSquare(int& row, int col); bool isUnderAttack(int row, int col); vector queens; }; 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) { } // Sets "row" to the row of the next safe square in column col. Important note: // Starts with the given row and col. 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) { } void Board::display() const { } int main() { Board board; board.do8Queens(); board.display(); }