3. Eight Queens

Write a program that places eight queens on a chessboard (8 x 8 board) such that no queen is "attacking" another. Queens in chess can move vertically, horizontally, or diagonally.

How you solve this problem is entirely up to you. You may choose to write a recursive program or an iterative (i.e., non-recursive) program. You will not be penalized/rewarded for choosing one method or another. Do what is easiest for you.

3.1. Output

Below is one solution to the eight queens problem, there may be others. Your program only needs to find one solution, any solution, and print it. Assuming the name of your program is queens, executing your program should look like this:

z123456@turing:~/csci241/Assign2$ ./queens 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 z123456@turing:~/csci241/Assign2$ 

where a '1'; means a queen is on that square of the board and a '0' means the square is empty.

Note that it is very important that your output be formatted exactly as shown above. In grading your program, its output will be checked by another program (we wrote) that expects as input a solution in this format.

3.2. Files You Must Write

Write the code for this part of the assignment in a single file which must be called queens.cpp.

3.3. Files We Give You

If you use the setup command to get ready for this assignment, you will find an executable file called test_queens in your ~/csci241/Assign2 directory.

You can use test_queens to test the output of your program (rather then checking it by hand). test_queens reads the output (in the format described above) of queens and prints either "SUCCESS" or "failure".

You can run test_queens in one of two ways.

z123456@turing:~/csci241/Assign2$ ./queens > queens.out z123456@turing:~/csci241/Assign2$ ./test_queens < queens.out SUCCESS z123456@turing:~/csci241/Assign2$ 

In this method you are storing the output from queens in a file called queens.out and then passing that file to test_queens. You might want to run queens this way while debugging; in case test_queens reports "failure", you can hand-inspect queens.out to find the error.

z123456@turing:~/csci241/Assign2$ ./queens | ./test_queens SUCCESS z123456@turing:~/csci241/Assign2$

"here is the Code to work on"

#include

using namespace std;

#define N 8

class queen_solver { private:

bool board[N][N] = {{false}};

public:

queen_solver() = default; bool place_queens(); bool place_queen_in_row(int); bool is_safe(int, int) const; void print_solution() const; };

int main() { queen_solver q;

if (q.place_queens()) print_solution(); else cout << "Error - no solution found ";

return 0; }

bool queen_solver::place_queens() { return place_queen_in_row(0); }

bool queen_solver::place_queen_in_row(int row) { // Base case #1 - All queens have been placed successfully. if (row >= 8) return true;

for (int col = 0; col < N; col++) { if (is_safe(row, col)) { // Put a queen at board[row][col]

if (place_queen_in_row(row + 1)) // Base case #2 - All queens in rows below this one // have been successfully placed. return true;

// Remove the queen at board[row][col] } } // Base case #3 - We were not able to place a queen anywhere in // this row. return false; }

bool queen_solver::is_safe(int row, int col) const { // Check the rows above this column. col stays the same, row varies // from row - 1 down to 0.

// Check the left diagonal above this row. col varies from col - 1 // down to 0, row varies from row - 1 down to 0.

// Check the right diagonal above this row. col varies from col + 1 // up to 7, row varies from row - 1 down to 0.

return true; }

void queen_solver::print_solution() const {

}