N-Queens Problem

The N-Queens problem is a classic problem in computer science that tests your understanding of backtracking. The goal of the problem is to place N queens on an N x N chessboard such that no two queens threaten each other.

To solve this problem using backtracking, we need to generate all possible configurations of the queens and check if each configuration is valid. If a valid configuration is found, we add it to the list of solutions.

Let's take a look at an example implementation in C++:

1#include <iostream>
2#include <vector>
3using namespace std;
4
5bool isSafe(int row, int col, vector<int>& board) {
6  // Check if any queen attacks the current position
7  for (int i = 0; i < row; i++) {
8    if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
9      return false;
10    }
11  }
12
13  return true;
14}
15
16void solveNQueens(int row, int n, vector<int>& board, vector<vector<string>>& solutions) {
17  // Base case: all queens have been placed
18  if (row == n) {
19    vector<string> solution;
20    for (int i = 0; i < n; i++) {
21      string rowString(n, '.');
22      rowString[board[i]] = 'Q';
23      solution.push_back(rowString);
24    }
25    solutions.push_back(solution);
26    return;
27  }
28
29  // Try placing the queen in each column of the current row
30  for (int col = 0; col < n; col++) {
31    if (isSafe(row, col, board)) {
32      board[row] = col;
33      solveNQueens(row + 1, n, board, solutions);
34    }
35  }
36}
37
38vector<vector<string>> solveNQueens(int n) {
39  vector<int> board(n);
40  vector<vector<string>> solutions;
41  solveNQueens(0, n, board, solutions);
42  return solutions;
43}
44
45int main() {
46  int n = 4;
47  vector<vector<string>> solutions = solveNQueens(n);
48
49  // Print the solutions
50  for (const vector<string>& solution : solutions) {
51    for (const string& row : solution) {
52      cout << row << endl;
53    }
54    cout << endl;
55  }
56
57  return 0;
58}

In this example, we have a function solveNQueens that finds and prints all possible solutions to the N-Queens problem. The function takes as input the number of queens (n) and returns a list of valid solutions. It uses the backtracking approach to recursively explore all possible combinations of queen placements.

The isSafe function checks if a queen can be placed at the current position without being attacked by other queens. It checks if there is any queen in the same column or on the same diagonal as the current position.

The solveNQueens function uses a vector called board to keep track of the column position of each queen in each row. It starts by placing a queen in the first row and tries all possible positions in the first column. If a valid position is found, the function recursively calls itself to place the next queen in the next row. This process continues until all queens have been placed.

Try running this code with different values of n to see the different solutions that can be found using backtracking.