Grid Backtracking
Place one item per row or cell, validate incrementally, recurse and undo. Pruning is what makes it finish.
Recursion & BacktrackingExponential with heavy pruningNew7 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
n queens
sudoku
word search
place items without conflict
The template
Get this into muscle memory, then adapt the condition per problem.
function place(row: number) {
if (row === n) { record(); return; }
for (let c = 0; c < n; c++) {
if (!safe(row, c)) continue;
mark(row, c); place(row + 1); unmark(row, c);
}
} Watch N-QueensIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Do not build a full candidate and then validate. Validate as you build.
- 2Track attacked columns and diagonals in sets for O(1) checks.
- 3Undo every mark you make, on every return path.
Drill it
Every problem in the bank that uses this pattern.
0 / 7 solved