# 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.