Assignment-03

Title

Implementing the N-Queens Problem Using Backtracking

Theory

The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens can attack each other. This means that no two queens share the same row, column, or diagonal. The problem can be solved using a backtracking algorithm, which is a form of recursion where the algorithm tries to build a solution incrementally and abandons a path ("backtracks") as soon as it determines that this path cannot possibly lead to a valid solution.

The backtracking algorithm follows these steps:

Base Case: If all queens are placed successfully, return true.
Try All Rows in Current Column: For each row, check if placing a queen at (row, col) is safe.
Check for Safety: Ensure no other queens can attack the position by checking the row, and both diagonals.
Place the Queen and Recur: Place the queen and make a recursive call to place the rest of the queens.
Backtrack: If placing the queen doesn't lead to a solution, remove the queen (backtrack) and try the next row.

Code Implementation

#include <iostream>
using namespace std;
 
class NQueen {
public:
    bool check(int **arr, int row, int col, int n);
    bool solveNQueen(int **arr, int col, int n);
};
 
bool NQueen::check(int **arr, int row, int col, int n) {
    int i, j;
 
    // Check row on the left side
    for (i = 0; i < col; i++) {
        if (arr[row][i]) {
            return false;
        }
    }
 
    // Check upper diagonal on the left side
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (arr[i][j]) {
            return false;
        }
    }
 
    // Check lower diagonal on the left side
    for (i = row, j = col; j >= 0 && i < n; i++, j--) {
        if (arr[i][j]) {
            return false;
        }
    }
 
    cout << "Placed queen q" << col + 1 << " at row " << row + 1 << "\n";
    return true;
}
 
bool NQueen::solveNQueen(int **arr, int col, int n) {
    // To check if all queens are placed
    if (col >= n) {
        cout << "===============================================================\n";
        cout << "ALL QUEENS ARE PLACED\n";
        cout << "===============================================================\n";
        return true;
    }
 
    for (int i = 0; i < n; i++) {
        if (check(arr, i, col, n)) {
            arr[i][col] = 1;
 
            // Displaying placed queens
            cout << "===============================================================\n";
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    if (arr[k][l] == 1) {
                        cout << "q" << l + 1 << "\t";
                    } else {
                        cout << "0\t";
                    }
                }
                cout << "\n";
            }
            cout << "===============================================================\n";
 
            // Iterate to the next column
            if (solveNQueen(arr, col + 1, n)) {
                return true;
            }
 
            cout << "===============================================================\n";
            cout << "Backtrack queen q" << col + 1 << "\n";
            cout << "===============================================================\n";
            arr[i][col] = 0; // Backtrack
        }
    }
 
    return false;
}
 
int main() {
    NQueen q1;
rep:
    int n;
    cout << "Enter the chessboard size (size should be greater than 3):\n";
    cin >> n;
    cout << "===============================================================\n";
 
    if (n <= 3) {
        cout << "Please enter a size greater than 3:\n";
        cout << "===============================================================\n";
        goto rep;
    }
 
    int **arr = new int*[n];
 
    cout << "Initially the board is:\n";
    // Initially setting value to 0
    for (int i = 0; i < n; i++) {
        arr[i] = new int[n];
        for (int j = 0; j < n; j++) {
            arr[i][j] = 0;
            cout << "0\t";
        }
        cout << "\n";
    }
 
    cout << "===============================================================\n";
    // Solve the problem
    q1.solveNQueen(arr, 0, n);
    cout << "===============================================================\n";
 
    cout << "AFTER PLACING THE QUEEN: \n";
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (arr[i][k] == 1) {
                cout << "q" << k + 1 << "\t";
            } else {
                cout << "0\t";
            }
        }
        cout << "\n";
    }
 
    cout << "===============================================================\n";
 
    // Clean up dynamic memory
    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
 
    return 0;
}

Setup and Run

Step 1: Save the Code

Save the code as nqueen.cpp.

Step 2: Compile the Code

Open a terminal and navigate to the directory where the file is saved. Compile the program using the GCC compiler:

g++ -o nqueen nqueen.cpp -std=c++11

Step 3: Run the Program

Run the compiled program:

./nqueen

Example

Input:

Enter the chessboard size (size should be greater than 3):
4

Output:

Initially the board is:
0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
===============================================================
Placed queen q1 at row 1
===============================================================
q1	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
===============================================================
Placed queen q2 at row 3
===============================================================
q1	0	0	0
0	0	0	0
0	q2	0	0
0

Contact

For any questions or clarifications, please contact Parth Sali at parthsali04@gmail.com.

Assignment 02 Assignment 01 A