🗓️ Day 26: Backtracking with Constraints – N-Queens, Sudoku

🧠 Concept Deep Dive

Backtracking with constraints means you’re not just exploring all paths — you’re pruning the invalid ones early.

Problems like N-Queens and Sudoku Solver require checking whether a current move violates any rules (e.g., no two queens attacking each other, no duplicate numbers in a Sudoku row).

This makes constraint-aware backtracking more intelligent and efficient than blind DFS.

Common applications:

N-Queens
Sudoku Solver
Word Search (grid constraints)

🎯 Visual Intuition (ASCII Diagram)

N-Queens 4x4:

  Q . . .       . Q . .     . . Q .     . . . Q
  . . Q .       . . . Q     Q . . .     . Q . .
  . . . Q       Q . . .     . . . Q     Q . . .
  . Q . .       . . Q .     . Q . .     . . Q .

Each recursive step places a queen and skips invalid columns or diagonals.

🛠️ Key Patterns

🧩 N-Queens Setup (Diagonal Checks)

function solveNQueens(n: number): string[][] {
  const res: string[][] = [];
  const board = Array(n).fill('').map(() => '.'.repeat(n).split(''));

  const cols = new Set<number>();
  const posDiag = new Set<number>(); // r + c
  const negDiag = new Set<number>(); // r - c

  function backtrack(r: number) {
    if (r === n) {
      res.push(board.map(row => row.join('')));
      return;
    }

    for (let c = 0; c < n; c++) {
      if (cols.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) continue;

      board[r][c] = 'Q';
      cols.add(c);
      posDiag.add(r + c);
      negDiag.add(r - c);

      backtrack(r + 1);

      board[r][c] = '.';
      cols.delete(c);
      posDiag.delete(r + c);
      negDiag.delete(r - c);
    }
  }

  backtrack(0);
  return res;
}

📘 Example

Input: n = 4\ Output:

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

Each sub-array is a valid board layout with 4 queens placed correctly.

🧪 Homework

Solve N-Queens using backtracking with constraints

function solveNQueens(n: number): string[][] {
  // your code here
}

Also try: Solve a 9x9 Sudoku board.

🧠 Big-O Cheat Sheet

Time Complexity: O(n!) (worst case, pruned with constraints)
Space Complexity: O(n^2) (board + sets)

🔮 Up Next

▶️ Day 27: Permutations and Combinations with Backtracking