N Queen Problem - C++ Solution

1. Introduction

In this blog post, we'll delve into the classic N–Queens puzzle, a well-known problem in computer science and combinatorics. The challenge is to place N queens on an N × N chessboard so that no two queens can attack each other, which means no two queens share the same row, column, or diagonal.

Problem

The N–Queens puzzle asks for all possible arrangements of N queens on an N × N chessboard, such that no two queens threaten each other. The solution should return a set containing all such possible arrangements.

2. Solution Steps

1. Use backtracking to explore all possible placements of queens.

2. Place a queen in a row and recursively place the remaining queens in the following rows.

3. Check for any conflicts with previously placed queens before placing a new queen.

4. If a valid placement is found for all queens, add the solution to the set.

5. Return the set of all valid queen placements.

3. Code Program

#include <iostream>
#include <vector>
#include <set>
using namespace std;

bool isSafe(int row, int col, const vector<string>& board, int N) {
    // Check this row on the left side
    for (int i = 0; i < col; i++)
        if (board[row][i] == 'Q') return false;

    // Check upper diagonal on the left side
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] == 'Q') return false;

    // Check lower diagonal on the left side
    for (int i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j] == 'Q') return false;

    return true;
}

void solveNQUtil(int col, vector<string>& board, set<vector<string>>& solutions, int N) {
    if (col == N) {
        solutions.insert(board);
        return;
    }

    for (int i = 0; i < N; i++) {
        if (isSafe(i, col, board, N)) {
            board[i][col] = 'Q';
            solveNQUtil(col + 1, board, solutions, N);
            board[i][col] = '.'; // Backtrack
        }
    }
}

set<vector<string>> solveNQ(int N) {
    set<vector<string>> solutions;
    vector<string> board(N, string(N, '.'));
    solveNQUtil(0, board, solutions, N);
    return solutions;
}

int main() {
    int N = 4;
    set<vector<string>> solutions = solveNQ(N);

    // Output all solutions
    for (const auto& solution : solutions) {
        for (const string& row : solution) {
            cout << row << endl;
        }
        cout << "----" << endl;
    }
    return 0;
}

Output:

. . Q .
Q . . .
. . . Q
. Q . .
----
. Q . .
. . . Q
Q . . .
. . Q .
----

Explanation:

The function solveNQ finds all solutions to the N-Queens puzzle. It uses backtracking to try placing queens in each column. The isSafe function checks if a queen can be placed in a given cell without being attacked. Once all queens are placed correctly, the solution is added to the set. For example, with N = 4, there are two solutions to the puzzle, each representing a unique arrangement of queens where no two can attack each other. The solutions are displayed as chessboard representations with 'Q' indicating the position of a queen.