Blog 5: N-Queens & Constraint Satisfaction Problems (CSPs) 👑

This blog dives into the N-Queens puzzle, one of the most famous constraint satisfaction problems (CSPs) solved elegantly using backtracking.

---

🔹 Problem Definition

Place N queens on an N×N chessboard such that no two queens attack each other.

• A queen can attack horizontally, vertically, and diagonally.
• We must generate all valid board configurations.

📌 Example:

Input: N = 4
Output:

[
 [".Q..",  // Column 1
  "...Q",  // Column 3
  "Q...",  // Column 0
  "..Q."], // Column 2

 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

---

🔹 Why N-Queens is Important?

• Classic example of constraint satisfaction.
• Showcases how to systematically prune invalid states.
• Forms the foundation for Sudoku solving, scheduling, AI planning, CSP solvers.

---

🔹 Intuition

1. Place queens row by row.
2. At each row, try placing a queen in each column.
3. Before placing, check constraints:

• No other queen in the same column.
• No other queen in diagonals.
  1. If valid → recurse to the next row.
  2. If all rows are filled → save solution.
  3. Backtrack by removing the queen and trying another column.

---

🔹 Standard Backtracking Approach (Java)

import java.util.*;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');

        backtrack(0, board, results, n);
        return results;
    }

    private void backtrack(int row, char[][] board, List<List<String>> results, int n) {
        if (row == n) {
            results.add(construct(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q';
                backtrack(row + 1, board, results, n);
                board[row][col] = '.';
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col, int n) {
        // Check column
        for (int i = 0; i < row; i++)
            if (board[i][col] == 'Q') return false;

        // Check diagonal ↖
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;

        // Check diagonal ↗
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
            if (board[i][j] == 'Q') return false;

        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board)
            res.add(new String(row));
        return res;
    }
}

---

🔹 Dry Run Example (N = 4)

Row 0: Try col 0 → valid
Row 1: col 0 invalid, col 1 invalid, col 2 valid
Row 2: col 0 invalid, col 1 invalid, col 2 invalid, col 3 valid
Row 3: col 1 valid
Solution found → Save

---

🔹 Optimization with HashSets

Instead of checking column & diagonals every time (O(N)),
we use HashSets to track used columns and diagonals in O(1).

public class NQueensOptimized {
    Set<Integer> cols = new HashSet<>();
    Set<Integer> diag1 = new HashSet<>(); // row - col
    Set<Integer> diag2 = new HashSet<>(); // row + col

    List<List<String>> results = new ArrayList<>();
    char[][] board;

    public List<List<String>> solveNQueens(int n) {
        board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0, n);
        return results;
    }

    private void backtrack(int row, int n) {
        if (row == n) {
            results.add(construct(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;

            board[row][col] = 'Q';
            cols.add(col); diag1.add(row - col); diag2.add(row + col);

            backtrack(row + 1, n);

            board[row][col] = '.';
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col);
        }
    }

    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board)
            res.add(new String(row));
        return res;
    }
}

---

🔹 Complexity Analysis

• Time Complexity: O(N!) (worst case, trying all placements).
• Space Complexity: O(N) recursion depth + sets for columns/diagonals.

---

🔹 Variations of N-Queens in Interviews

1. Count Solutions (LeetCode 52)

• Instead of generating all, just count how many exist.
• Modify recursion to increment a counter instead of saving boards.

1. N-Rooks Problem

• Place N rooks such that no two attack each other → simpler than queens (only check columns).

1. N-Knights Problem

• Place knights so they don’t attack each other → different movement constraints.

1. Sudoku Solver (LeetCode 37)

• Same constraint satisfaction pattern but on a 9x9 grid with number constraints.

1. Constraint Satisfaction in AI

• CSPs extend beyond chess → timetabling, resource allocation, scheduling.
• N-Queens is a simplified version of constraint-based optimization problems.

---

🔹 Key Takeaways

✅ N-Queens is the classic backtracking + CSP problem.
✅ Optimize using HashSets for constant-time safety checks.
✅ Variants include Sudoku Solver, N-Rooks, N-Knights.
✅ Forms the backbone for real-world CSPs in AI and operations research.

---

🔹 What’s Next?

In Blog 6: Word Search & Grid Backtracking Problems, we’ll dive into searching paths in 2D boards like Word Search, Rat in a Maze, and Knight’s Tour — all leveraging grid-based backtracking.