Question

please explain/ comment

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 10000000 0 0 0 0 1 0 0 0 00000001 00000100 00100000 O O O O O O 1 0 01 OOOOOO 00010000 z123456@turing:-/csci241/Assign2$ where a '1'; means a queen is on that square of the board and a 'o' 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 that format. 3.2. File You Must Write Write the code for this assignment in a single file which must be called queens.cpp.

Answer 1

#include<bits/stdc++.h> //function to check if a queen is placed at left side of (x,y) bool check(int board[8][8], int x, int y) { for (int i=0; i<y;i++) if (board[x][i] == 1) return false; for (int i=x,j=y;i>=0 && j>=0; i--,j--) if (board[i][j] == 1) return false; for (int i=x, j=y;j>=0 && i<8;i++,j--) if (board[i][j] == 1) return false; return true; //recursive function to place the queens on the board using backtracking bool solve(int board[8][8], int col) { //base case if (col>=8) return true; for (int i=0;i<8; i++) { if (check(board, i, col)) { board[i][col] = 1; if (solve(board, col+1) == true) return true; board[i][col] = 0; return false; ଟିଟି int main() { int board[8][8] = { { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0} }; solve (board, 0); for (int i=0;i<8;i++) { for (int j=0; j<8; j++) printf("%d ", board[i][j]); printf("\n"); return 0;

Output: 1 еееееее eeeeee1e еееееее eeeeeee1 01 ееееее eee1oooo eeeee1ee ee1eeeee

Code:

#include<bits/stdc++.h>
//function to check if a queen is placed at left side of (x,y)
bool check(int board[8][8], int x, int y) {
    for (int i=0;i<y;i++)
        if (board[x][i] == 1)
            return false;
    for (int i=x,j=y;i>=0 && j>=0;i--,j--)
        if (board[i][j] == 1)
            return false;
    for (int i=x,j=y;j>=0 && i<8;i++,j--)
        if (board[i][j] == 1)
            return false;
    return true;
}
//recursive function to place the queens on the board using backtracking
bool solve(int board[8][8], int col) {
    //base case
    if (col>=8)
        return true;
    for (int i=0;i<8;i++) {
        if (check(board, i, col)) {
            board[i][col] = 1;
            if (solve(board,col+1) == true)
                return true;
            board[i][col] = 0;
        }
    }
    return false;
}
int main() {
    int board[8][8] = {
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0},
            { 0, 0, 0, 0, 0, 0, 0, 0} };
    solve(board, 0);
    for (int i=0;i<8;i++) {
        for (int j=0;j<8;j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
    return 0;
}