♛ N-Queens Problem – Complete In-Depth Explanation

The N-Queens problem is a classic chessboard puzzle where the goal is to place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

📌 Why is N-Queens Important?

  • 💡 Demonstrates backtracking algorithms.
  • ⚙️ Illustrates constraint satisfaction problems.
  • 🧩 A good example for understanding recursive problem-solving.
  • 🎓 Frequently used in coding interviews.

📌 Understanding N-Queens with an Example

Let's consider the 4-Queens problem (N=4). We need to place 4 queens on a 4x4 board. One possible solution is: 


                  _ Q _ _
                  _ _ _ Q
                  Q _ _ _
                  _ _ Q _

Here, each 'Q' represents a queen, and '_' represents an empty square. Notice how no two queens share a row, column, or diagonal.

🔹 Key Points

  • Each row must have exactly one queen.
  • Each column must have exactly one queen.
  • No two queens can be on the same diagonal.

🛠 Solution Approach (Backtracking)

The most common approach to solving the N-Queens problem is using backtracking. Here's the general idea:

  1. Start with an empty board.
  2. Try placing a queen in the first row.
  3. For each valid placement in the first row, try placing a queen in the second row.
  4. Continue this process until all rows are filled.
  5. If a row cannot accommodate a queen, backtrack to the previous row and try a different placement.

                  bool isSafe(vector& board, int row, int col, int n) {
                      // Check column
                      for (int i = 0; i < row; i++) {
                          if (board[i][col] == 'Q') {
                              return false;
                          }
                      }
              
                      // Check diagonals
                      for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                          if (board[i][j] == 'Q') {
                              return false;
                          }
                      }
                      for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                          if (board[i][j] == 'Q') {
                              return false;
                          }
                      }
                      return true;
                  }
              
                  bool solveNQueensUtil(vector& board, int row, int n, vector>& result) {
                      if (row == n) {
                          result.push_back(board);
                          return true; // Found a solution
                      }
              
                      for (int col = 0; col < n; col++) {
                          if (isSafe(board, row, col, n)) {
                              board[row][col] = 'Q';
                              if (solveNQueensUtil(board, row + 1, n, result)) {
                                  return true; // If a solution is found further down, return true.
                              }
                              board[row][col] = '.'; // Backtrack: Remove the queen and try a different column.
                          }
                      }
                      return false; // No solution found for this row.
                  }
              
                  vector> solveNQueens(int n) {
                      vector> result;
                      vector board(n, string(n, '.')); // Initialize empty board
                      solveNQueensUtil(board, 0, n, result);
                      return result;
                  }

⏳ Time Complexity Analysis

The time complexity of the backtracking solution for N-Queens is difficult to express precisely. In the worst case, it can be exponential, as we might explore a large portion of the search space. However, pruning through the `isSafe()` check significantly reduces the actual execution time.

🌍 Real-World Applications of Backtracking

  • 🧩 Constraint Satisfaction Problems: Solving puzzles like Sudoku.
  • 🤖 Artificial Intelligence: Pathfinding and game playing.
  • 📈 Optimization: Finding optimal solutions in complex scenarios.

🔗 Next Topics