## Introduction

The N-Queens problem is a classic example of combinatorial optimization and backtracking. It involves placing N chess queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. The problem is a fundamental example of the application of backtracking algorithms and is often used to teach the concept of constraint satisfaction in computer science.

In this article, we will discuss the N-Queens problem, explain the backtracking approach to solve it, and provide a C++ program with examples to illustrate the solution and outputs.

## Prerequisites

Before diving into the implementation, it’s beneficial to have:

**Basic understanding of algorithms**: Knowledge of backtracking and recursion.**Familiarity with C++ programming**: Proficiency in C++ syntax, arrays, and functions.

## The N-Queens Problem

### Definition and Formula

The N-Queens problem is defined as placing N queens on an N×N chessboard such that no two queens threaten each other. A queen can move horizontally, vertically, or diagonally, meaning that for a valid arrangement:

- No two queens share the same row.
- No two queens share the same column.
- No two queens share the same diagonal.

The solution to the N-Queens problem can be approached using backtracking, a technique for solving constraint satisfaction problems. Backtracking incrementally builds candidates for the solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly lead to a valid solution.

## Implementing the N-Queens Problem in C++

### 1.1 Backtracking Approach

Below is a C++ implementation of the N-Queens problem using backtracking.

```
#include <iostream>
#include <vector>
#define N 4
void printSolution(const std::vector<std::vector<int>>& board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
std::cout << board[i][j] << " ";
std::cout << std::endl;
}
}
bool isSafe(const std::vector<std::vector<int>>& board, int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(std::vector<std::vector<int>>& board, int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
bool solveNQ() {
std::vector<std::vector<int>> board(N, std::vector<int>(N, 0));
if (!solveNQUtil(board, 0)) {
std::cout << "Solution does not exist" << std::endl;
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
```

### 1.2 Example Usage

The example above initializes the N-Queens problem with a 4×4 chessboard. The output will show a possible solution to the problem.

### 1.3 Output for Example 1

```
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
```

## Additional Examples

### 2.1 Example 2: 8-Queens Problem

In this example, we increase the number of queens to 8 to illustrate how the solution scales.

```
#define N 8
int main() {
solveNQ();
return 0;
}
```

#### Output for Example 2

```
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
```

### 2.2 Example 3: Customizing the Board Size

Here, we solve the N-Queens problem for a 5×5 board.

```
#define N 5
int main() {
solveNQ();
return 0;
}
```

#### Output for Example 3

```
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
```

## Conclusion

The N-Queens problem is an excellent example of the power of backtracking algorithms. It demonstrates how complex problems can be broken down into smaller, manageable subproblems, making it a valuable teaching tool in computer science. This article provided a detailed C++ implementation of the N-Queens problem, complete with examples and outputs to illustrate its practical application. Understanding and implementing this problem enhances your problem-solving skills and provides a solid foundation in recursive and backtracking techniques.