LeetCode Solution 51 - N-Queens

Problem Statement

The N-Queens problem asks us to place N queens on an N x N chessboard such that no two queens attack each other. We need to return all possible solutions where each solution is a distinct board configuration.

Example:

Input:

n = 4

Output:

[
  [".Q..",  // Solution 1
   "...Q",
   "Q...",
   "..Q."],

  ["..Q.",  // Solution 2
   "Q...",
   "...Q",
   ".Q.."]
]

Constraints:

• 1 <= n <= 9

---

Optimal Approach: Backtracking

Explanation:

1. Use recursion to explore board placements.
2. Check if placing a queen is valid at each row.
3. Move to the next row if valid.
4. Backtrack when all rows are filled or no valid placement exists.

C++ Implementation (LeetCode-Compatible)

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> result;
    
    bool isValid(vector<string>& board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        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;
    }
    
    void solve(int row, int n, vector<string>& board) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';
                solve(row + 1, n, board);
                board[row][col] = '.'; // Backtrack
            }
        }
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        solve(0, n, board);
        return result;
    }
};

Step-by-Step Explanation

• Recursive Backtracking Approach:
  • Try placing a queen in each column of the current row.
  • Check if the placement is valid.
  • If valid, proceed to the next row.
  • If all rows are filled, store the solution.
  • Use backtracking to revert changes and explore other possibilities.

---

Dry Run Example:

Input:

n = 4

Execution Steps:

Step	Board State	Comment
1	["Q...", "....", "....", "...."]	Placed Queen in (0,0)
2	["Q...", "...Q", "....", "...."]	Placed Queen in (1,3)
3	["Q...", "...Q", ".Q..", "...."]	Placed Queen in (2,1)
4	["Q...", "...Q", ".Q..", "..Q."]	Placed Queen in (3,2) - Valid Solution
5	Backtrack and try alternatives	Explore other configurations

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force (Generate All Boards)	O(N^N)	O(N^2)	Too many invalid cases
Bitmask Optimization	O(N!)	O(N)	Used for large N
Backtracking	O(N!)	O(N^2)	✅ Best choice

Why Backtracking is Best?

• Efficient pruning eliminates invalid placements early.
• Only valid placements are explored.
• Scales well up to N = 9.

---

Conclusion

• Best Solution: Backtracking (Recursive Placement with Pruning).
• Why? Efficient O(N!) time complexity with manageable space usage.
• Alternative Solutions: Brute Force (too slow), Bitmask (not necessary for small N).

Practice More:

• Sudoku Solver
• Combination Sum
• Word Search