Code: N Queen using Recursion | DSA in C++ - Software Development PDF Download

Here's a code example in C++ for solving the N-Queens problem using recursion:

#include <iostream>

#include <vector>

using namespace std;

// Function to check if a queen can be placed at the given position

bool isSafe(vector<vector<int>>& board, int row, int col, int N) {

    // Check for queens in the same column

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

        if (board[i][col] == 1) {

            return false;

        }

    }

    // Check for queens in the upper left diagonal

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {

        if (board[i][j] == 1) {

            return false;

        }

    }

    // Check for queens in the upper right diagonal

    for (int i = row, j = col; i >= 0 && j < N; i--, j++) {

        if (board[i][j] == 1) {

            return false;

        }

    }

   return true;  // The position is safe for placing a queen

}

// Recursive function to solve the N-Queens problem

bool solveNQueensUtil(vector<vector<int>>& board, int row, int N) {

    if (row == N) {

        // All queens have been placed successfully

        return true;

    }

    for (int col = 0; col < N; col++) {

        if (isSafe(board, row, col, N)) {

            // Place the queen at the current position

            board[row][col] = 1;

           // Recursively place the remaining queens

            if (solveNQueensUtil(board, row + 1, N)) {

                return true;

            }

            // Backtrack if the current arrangement leads to no solution

            board[row][col] = 0;

        }

    }

    return false;  // No solution found

}

// Function to solve the N-Queens problem

void solveNQueens(int N) {

    vector<vector<int>> board(N, vector<int>(N, 0));

    if (solveNQueensUtil(board, 0, N)) {

        // Print the solution

        cout << "Solution exists:" << endl;

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

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

                cout << board[i][j] << " ";

            }

            cout << endl;

        }

    } else {

        cout << "No solution exists." << endl;

    }

}

int main() {

    int N;

    cout << "Enter the value of N: ";

    cin >> N;

   solveNQueens(N);

    return 0;

}

This code uses a recursive approach to solve the N-Queens problem. The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. In this solution, we represent an empty cell with 0 and a cell with a queen with 1.
The code starts by defining a helper function 'isSafe' to check if it is safe to place a queen at a given position '(row, col)'. It checks for conflicts with queens in the same column and the upper-left and upper-right diagonals.
The recursive function 'solveNQueensUtil' is called to solve the problem. It takes the current row, the size of the board (N), and the board configuration as parameters. It starts by checking if all queens have been successfully placed (base case). If all queens are placed, it returns 'true' to indicate a solution has been found.
Otherwise, it iterates through each column in the current row. For each column, it checks if it is safe to place a queen at the current position using the 'isSafe' function. If it is safe, it marks the cell as 1 and makes a recursive call to 'solveNQueensUtil' for the next row. If this recursive call returns 'true', it means a solution is found, and the function returns 'true' as well.
If no solution is found for the current arrangement, the function backtracks by marking the current cell as 0 and continues to the next column.
The main function 'solveNQueens' initializes the board and calls 'solveNQueensUtil' to solve the problem. It then prints the solution if one exists, or a message indicating that no solution is found.
To use this code, you can simply compile and run it. It will ask for the value of N, which represents the size of the chessboard and the number of queens to be placed. The output will be the board configuration with 1 representing the queens and 0 representing empty cells, or a message indicating that no solution exists for the given value of N.