ReviseAlgo Logo

Backtracking

Constraint Problems

Master advanced constraint backtracking: N-Queens threat checks, Sudoku grid solvers, and 2D matrix pathfinding.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What are Constraint Problems?

Constraint Problems are backtracking tasks with strict placement constraints:
  • N-Queens: Placing N non-attacking queens on an N × N chessboard.
  • Sudoku Solver: Completing a grid with digits 1-9 without row, column, or subgrid duplicates.
  • Grid Pathfinding / Word Search: Locating target sequences in 2D grids without visiting cells twice.

    • Why study them?

    These problems evaluate your ability to manage multi-dimensional state coordinates. You must optimize validation routines (checking if a choice is valid in O(1)) to prevent timeouts.

    2. Mental Model: The Eraser Pencil

    Imagine working on a grid puzzle with a pencil and eraser:

  • You write a candidate value (like digit 5 in Sudoku) in a blank cell.
  • If subsequent steps cause conflicts (no valid options left for downstream cells), you rub out your candidate (grid[r][c] = '.') and try another digit.
  • The state must return to its pristine state before backtracking.

    • 3. Core Algorithms & Implementations

    State Tracking Invariants

  • N-Queens Diagonal Math:
    • - Columns: Tracked using a set of indices c. - Positive Diagonals (bottom-left to top-right): Nodes sharing a diagonal have a constant sum of indices: r + c. - Negative Diagonals (top-left to bottom-right): Nodes sharing a diagonal have a constant difference of indices: r - c.
  • Sudoku subgrid math: The index of the 3 × 3 subgrid for cell (r, c) is: (r / 3) * 3 + (c / 3).

    • 4. Visualizing Diagonal Threat Math (N-Queens)

    Given cell (2, 1) on a 4 × 4 board:

  • Column: Threatened index is c = 1.
  • diag1 (Positive): Threat key is r + c = 2 + 1 = 3. Nodes sharing this diagonal are (0, 3), (1, 2), (2, 1), and (3, 0).
  • diag2 (Negative): Threat key is r - c = 2 - 1 = 1. Nodes sharing this diagonal are (1, 0), (2, 1), and (3, 2).

    • 5. Real-World Examples

  • Classroom Timetable Scheduler: Assigning slots to courses, resolving row (instructor) and column (room) conflicts.
  • Printed Circuit Board (PCB) Routing: Placing silicon gate coordinates on layout boards without electrical connection overlaps.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test index arithmetic:
  • "Explain how you optimize checking if a queen is threatened." -> Do not loop over the grid. Instead, maintain three sets: cols, diag1 (keys r + c), and diag2 (keys r - c). This check takes O(1) time.
  • "Solve Word Search in a 2D matrix." -> Traverse the grid. If a cell matches the starting character, run DFS in 4 directions. To prevent cycle paths without extra space, swap board[r][c] with # during the search, and swap it back on backtrack.

    • Common Mistakes

    Warning: 1. Forgetting to Restore Cell Val: Replacing empty board values during cell evaluations but forgetting to reset them (board[r][c] = '.') when downstream branches fail.
    > 2. Wrong Subgrid Formulas: Incorrect index mapping for 3 × 3 Sudoku cells, causing check scripts to miss box conflicts.

    7. Summary

  • State Checkers: Use coordinate sets (col, row, subgrid, diagonals) to validate moves in O(1) time.
  • Backtracking Erasures: Always reset modified values (board[r][c] = '.' or removing items from sets) when recursive calls return false.

    • 8. Quiz

    Question 1: What is the maximum number of solutions to the 8-Queens problem on an 8x8 board? Answer: 92 unique configurations.
    Question 2: In Sudoku, why does the helper function solve() return a boolean instead of void? Answer: Because we only need one valid completed board. A boolean return allows the algorithm to terminate search paths early and propagate success upwards as soon as a single solution is found.
    Question 3: Why are sets cols, diag1, and diag2 faster than checking the entire board manually? Answer: Checking the board manually takes O(N) time per placement. Using hash sets reduces threat checking to O(1) time, significantly optimizing the search.
    Question 4: True or False: Word Search (LeetCode 79) requires a separate visited[][] boolean array. Answer: False. You can track visited cells in-place by setting board[r][c] = '#' before recursing, and restoring the original character board[r][c] = temp on backtrack. This reduces auxiliary space complexity.
    Question 5: What is the subgrid index of cell (5, 7) in a 9x9 Sudoku grid? Answer: Subgrid index is 5. Calculated as 3 (5 / 3) + (7 / 3) = 3 1 + 2 = 5.