Question

in c++

Purpose: This lab will give you experience harnessing an existing backtracking algorithm for the eight queens problem, and seeing its results displayed on your console window (that is, the location of standard output).

Lab

A mostly complete version of the eight queens problem has been provided for you to download. This version has the class Queens nearly completed.

You are to provide missing logic for the class Queens that will enable it to create a two-dimensional array that will represent a chess board with eight rows and eight columns. You are also to modify logic to display the chess board such that the display uses a nested loop to print the rows and columns of the chessboard. To do this, you must write logic for:

+clearBoard()

and modify logic for:

+displayBoard()

After this is done, you are to write a driver program named Lab4 that has a main() function responsible for making an object from the Queens class. The main() function must also use that Queens object to start the first queen of the chess board in the first column of the chess board. Once the first queen has been placed on the chess board, you must use its displayBoard() method to show you the solution to the eight queens problem

(Actually, the eight queens problem has many solutions, but the solution you will be displaying is based on the queen being placed in a specific position the first column of the chess board based on logic already programmed into the Queens class).

You are to submit for this lab:

(1) The modified Queens class with clearBoard() and displayBoard() properly working

(2) The new program driver class that has the main() method fully implemented as described previously.

The Queens class is available in these files for you to download:

Queens.h

Queens.cpp

/* File: Queens.h */

#ifndef QUEENS_H

#define QUEENS_H

#include <iostream>

using std::cout;

/** @class Queens

* The Queen class. */

class Queens

{

private:

// chess board -- a C++ 2-dimensional dynamic array

int **board;

// squares per row or per column

const static int BOARD_SIZE = 8;

//used to indicate empty square

const static int EMPTY = 0;

//used to indicate square contains a queen

const static int QUEEN = 1;

public:

Queens();

// --------------------------------------------------

// Constructor: Create an empty square board.

// --------------------------------------------------

void clearBoard();

// --------------------------------------------------

// Clears the board.

// Precondition: None.

// Postcondition: Sets all squares to EMPTY

// --------------------------------------------------

void displayBoard();

// --------------------------------------------------

// Displays the board.

// Precondition: None.

// Postcondition: Board is written to standartd

// output; zero is an EMPTY square, one is a square

// containing a queen (QUEEN)

// --------------------------------------------------

bool placeQueens(int column);

// --------------------------------------------------

// Place queens in columns of the board beginning

// at the column specified.

// Precondition: Queens are placed correctly in

// columns 1 thro coulumn-1.

// Postcondition: If a solution is found, each

// column of the board contains one queen and method

// returns true; otherwise retruns false (no

// solution existis for a queen anywhere in column

// specified).

// --------------------------------------------------

void setQueen(int row, int column);

// --------------------------------------------------

// Set a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to QUEEN.

// --------------------------------------------------

void removeQueen(int row, int column);

// --------------------------------------------------

// Remove a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to EMPTY.

// --------------------------------------------------

bool isUnderAttack(int row, int column);

// --------------------------------------------------

// Determines whether the square on the board at a

// given row and column is under attack by any queens

// in the columns 1 through column-1.

// Precondition: Each column between 1 and column-1

// has a queen placed in a square at a specific row.

// None of these queens can be attacked by any other

// queen.

// Postcondition: If the deignated square is under

// attack, returns true; otherwise, returns false.

// --------------------------------------------------

}; // end Queens

#endif

/* File: Queens.cpp */

#include "Queens.h"

Queens::Queens() {

int rows = BOARD_SIZE;

int columns = BOARD_SIZE;

// memory allocated for elements of rows.

board = new int *[rows] ;

// memory allocated for elements of each column.

for( int i = 0 ; i < rows ; i++ )

board[i] = new int[columns];

} // end constructor

void Queens::clearBoard() {

// place your logic to implement this method here

} // end clearBoard

void Queens::displayBoard() {

for (int i=0; i<BOARD_SIZE; i++) {

for (int j=0; j<BOARD_SIZE; j++) {

// place your logic to implement this method here

// that prints a single row of the chess board

// to the console window (i.e., standard output)

}

std::cout << "\n";

// this newline prints after a row

// of the chess board has been printed

}

} // end displayBoard

bool Queens::placeQueens(int column) {

if (column > BOARD_SIZE) {

return true; // base case

}

else {

bool queenPlaced = false;

int row = 1; // number of square in column

while ( !queenPlaced && (row <= BOARD_SIZE) ) {

// if square can be attacked

if (isUnderAttack(row, column)) {

++row; // consider next square in column

} // end if

else { // place queen and consider next column

setQueen(row, column);

queenPlaced = placeQueens(column+1);

// if no queen is possible in the next column,

if (!queenPlaced) {

// backtrack: remove queen placed earliers

// and try next square in column

removeQueen(row, column);

++row;

} // end if

} // end if

} // end while

return queenPlaced;

} // end if

} // end placeQueens

void Queens::setQueen(int row, int column) {

board[row-1][column-1] = QUEEN;

} // end setQueen

void Queens::removeQueen(int row, int column) {

board[row-1][column-1] = EMPTY;

} // end setQueen

bool Queens::isUnderAttack(int row, int column) {

// check column

for (int i=0; i<row-1; i++){

if (board[i][column-1]==1){

return true;

}

}

// check row

for (int i=0; i<column-1; i++) {

if (board[row-1][i] == 1){

return true;

}

}

// check lower diagnal

int lower_dir_row = row-2;

int lower_dir_column = column-2;

while (lower_dir_row>=0 && lower_dir_column>=0){

if (board[lower_dir_row][lower_dir_column]==1){

return true;

} else {

lower_dir_row = lower_dir_row -1;

lower_dir_column = lower_dir_column -1;

}

}

// check upper diagnal

int upper_dir_row = row;

int upper_dir_column = column-2;

while (upper_dir_row<BOARD_SIZE && upper_dir_column>=0){

if(board[upper_dir_row][upper_dir_column] ==1){

return true;

}else{

upper_dir_row = upper_dir_row +1;

upper_dir_column = upper_dir_column -1;

}

}

return false;

} // end isUnderAttack

Once you are done getting the lab to work, pay particular attention to the logic in the placeQueens() method. There are comments indicating how backtracking is used. See how the recursive call is used in the case that a queen is determined to be placed, and how backtracking occurs in the case that a queen has been found to have to be taken back from a position where it was placed. See that backtracking is a way of using decisions to determine if a current state of logic should be allowed, or if the logic should be undone since the logic does not lead to a solution. Understanding this is the essence of understanding how backtracking algorithms are implemented.

Answer 1

//Modified Queesn.java

public class Queens {

// squares per row or per column

public static final int BOARD_SIZE = 8;

//used to indicate empty square

public static final int EMPTY = 0;

//used to indicate square contains a queen

public static final int QUEEN = 1;

private int board[][]; // chess board

public Queens() {

// --------------------------------------------------

// Constructor: Create an empty square board.

// --------------------------------------------------

board = new int[BOARD_SIZE][BOARD_SIZE];

} // end constructor

public void clearBoard(){

// --------------------------------------------------

// Clears the board.

// Precondition: None.

// Postcondition: Sets all squares to EMPTY

// --------------------------------------------------

// place your logic to implement this method here

for(int i=0; i<BOARD_SIZE; i++) {

for(int j=0; j<BOARD_SIZE; j++) {

board[i][j]=EMPTY;

}

}

} // end clearBoard

public void displayBoard(){

// --------------------------------------------------

// Displays the board.

// Precondition: None.

// Postcondition: Board is written to standartd

// output; zero is an EMPTY square, one is a square

// containing a queen (QUEEN)

// --------------------------------------------------

for (int i=0; i<BOARD_SIZE; i++) {

for (int j=0; j<BOARD_SIZE; j++) {

// place your logic to implement this method here

// that prints a single row of the chess board

// to the console window (i.e., standard output)

System.out.print(board[i][j]+" ");

}

System.out.print(" ");

// this newline prints after a row

// of the chess board has been printed

}

} // end displayBoard

public boolean placeQueens(int column) {

// --------------------------------------------------

// Place queens in columns of the board beginning

// at the column specified.

// Precondition: Queens are placed correctly in

// columns 1 thro coulumn-1.

// Postcondition: If a solution is found, each

// column of the board contains one queen and method

// returns true; otherwise retruns false (no

// solution existis for a queen anywhere in column

// specified).

// --------------------------------------------------

if (column > BOARD_SIZE) {

return true; // base case

}

else {

boolean queenPlaced = false;

int row = 1; // number of square in column

while ( !queenPlaced && (row <= BOARD_SIZE) ) {

// if square can be attacked

if (isUnderAttack(row, column)) {

++row; // consider next square in column

} // end if

else { // place queen and consider next column

setQueen(row, column);

queenPlaced = placeQueens(column+1);

// if no queen is possible in the next column,

if (!queenPlaced) {

// backtrack: remove queen placed earliers

// and try next square in column

removeQueen(row, column);

++row;

} // end if

} // end if

} // end while

return queenPlaced;

} // end if

} // end placeQueens

private void setQueen(int row, int column) {

// --------------------------------------------------

// Set a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to QUEEN.

// --------------------------------------------------

board[row-1][column-1] = QUEEN;

} // end setQueen

private void removeQueen(int row, int column) {

// --------------------------------------------------

// Remove a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to EMPTY.

// --------------------------------------------------

board[row-1][column-1] = EMPTY;

} // end setQueen

private boolean isUnderAttack(int row, int column) {

// --------------------------------------------------

// Determines whether the square on the board at a

// given row and column is under attack by any queens

// in the columns 1 through column-1.

// Precondition: Each column between 1 and column-1

// has a queen placed in a square at a specific row.

// None of these queens can be attacked by any other

// queen.

// Postcondition: If the deignated square is under

// attack, returns true; otherwise, returns false.

// --------------------------------------------------

// check column

for (int i=0; i<row-1; i++){

if (board[i][column-1]==1){

return true;

}

}

// check row

for (int i=0; i<column-1; i++) {

if (board[row-1][i] == 1){

return true;

}

}

// check lower diagnal

int lower_dir_row = row-2;

int lower_dir_column = column-2;

while (lower_dir_row>=0 && lower_dir_column>=0){

if

(board[lower_dir_row][lower_dir_column]==1){

return true;

} else {

lower_dir_row = lower_dir_row -1;

lower_dir_column = lower_dir_column -1;

}

}

// check upper diagnal

int upper_dir_row = row;

int upper_dir_column = column-2;

while (upper_dir_row<BOARD_SIZE && upper_dir_column>=0){

if(board[upper_dir_row][upper_dir_column] ==1){

return true;

}else{

upper_dir_row = upper_dir_row +1;

upper_dir_column = upper_dir_column -1;

}

}

return false;

} // end isUnderAttack

}

//QueensDriver.java

public class QueensDriver {

public static void main(String[] args) {

Queens queens=new Queens();

queens.placeQueens(1);

queens.displayBoard();

}

}

Output: