What signals in a problem statement indicate the Constraint satisfaction sub-pattern?

"well-formed parentheses"; "no two queens attack each other"; "fill the board so every row, column and box has 1–9"

Constraint satisfaction (Backtracking Sub-pattern)

Q: What makes Constraint satisfaction different from other sub-patterns?

**Generate Parentheses** has a simple rule: `(` while open < n, `)` while close < open, so every leaf is valid. **N-Queens** places a queen per row and checks columns and both diagonals with three `bool` arrays. **Sudoku Solver** looks for **one** solution: the function returns `bool` and stops at the first success; bitmasks per row/column/box make checks O(1), and choosing the cell with the fewest options shrinks the tree.

Place items one by one, and before each placement check the rules so a bad partial answer is dropped early.

Signals in the problem statement

›
"well-formed parentheses"
›
"no two queens attack each other"
›
"fill the board so every row, column and box has 1–9"

What makes it different

Generate Parentheses has a simple rule: ( while open < n, ) while close < open, so every leaf is valid. N-Queens places a queen per row and checks columns and both diagonals with three bool arrays. Sudoku Solver looks for one solution: the function returns bool and stops at the first success; bitmasks per row/column/box make checks O(1), and choosing the cell with the fewest options shrinks the tree.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Generate Parentheses
Basic Anchor·LeetCode #22
WalkthroughMedium
2
N-Queens
Basic Reinforcement·LeetCode #51
WalkthroughHard
3
Sudoku Solver
Slight Variation·LeetCode #37
WalkthroughHard

Template

placement-template.cpp

// Constraint satisfaction: place one item per step (a queen per row), check the rules in O(1)
// with "taken" arrays, and undo all of them on the way back.
void place(int r, int n, vector<string>& board, vector<bool>& col, vector<bool>& diag,
           vector<bool>& anti, vector<vector<string>>& out) {
    if (r == n) { out.push_back(board); return; }        // every row has a queen
    for (int c = 0; c < n; c++) {
        if (col[c] || diag[r + c] || anti[r - c + n - 1]) continue; // attacked: prune
        board[r][c] = 'Q'; col[c] = diag[r + c] = anti[r - c + n - 1] = true;
        place(r + 1, n, board, col, diag, anti, out);
        board[r][c] = '.'; col[c] = diag[r + c] = anti[r - c + n - 1] = false;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    vector<bool> col(n), diag(2 * n - 1), anti(2 * n - 1);
    vector<vector<string>> out;
    place(0, n, board, col, diag, anti, out);
    return out;
}

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

String partitioning Grid / path search