Backtracking on Grids and Constraints
The choices live on a board
The same choose, explore, unchoose, with two changes. The choices are places on a board: the next cell of a path, the square for a queen, the digit for a Sudoku cell. And every choice has to keep the board's rules. Check each one the moment it's made: a choice that breaks a rule ends its whole branch at once, before anything is built on it. On an 8 × 8 board the queens search makes 2,057 calls that way; placing a queen in every row and checking only full boards takes 19,173,961.
Walk a grid: mark the cell, unmark it after
Word Search asks if a word can be traced on a grid of letters through neighbouring cells, each cell used at most once. The path is the choice list. From a matching cell, try its four neighbours for the next letter; mark the cell while the path is on it, and put its letter back on the way out, so a different path can still use it:
bool found(vector<vector<char>>& board, const string& word, int r, int c, int k) {
if (k == (int)word.size()) return true; // every letter matched
if (r < 0 || c < 0 || r >= (int)board.size() || c >= (int)board[0].size() || board[r][c] != word[k])
return false;
char keep = board[r][c];
board[r][c] = '#'; // mark: this path is on the cell
bool ok = found(board, word, r + 1, c, k + 1) || found(board, word, r - 1, c, k + 1)
|| found(board, word, r, c + 1, k + 1) || found(board, word, r, c - 1, k + 1);
board[r][c] = keep; // unmark on the way back
return ok;
}
bool exist(vector<vector<char>>& board, const string& word) {
for (int r = 0; r < (int)board.size(); r++)
for (int c = 0; c < (int)board[0].size(); c++)
if (found(board, word, r, c, 0)) return true;
return false;
}
def exist(board, word):
rows, cols = len(board), len(board[0])
def found(r, c, k):
if k == len(word):
return True # every letter matched
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[k]:
return False
keep, board[r][c] = board[r][c], "#" # mark: this path is on the cell
ok = (found(r + 1, c, k + 1) or found(r - 1, c, k + 1)
or found(r, c + 1, k + 1) or found(r, c - 1, k + 1))
board[r][c] = keep # unmark on the way back
return ok
return any(found(r, c, 0) for r in range(rows) for c in range(cols))
static boolean found(char[][] board, String word, int r, int c, int k) {
if (k == word.length()) return true; // every letter matched
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(k))
return false;
char keep = board[r][c];
board[r][c] = '#'; // mark: this path is on the cell
boolean ok = found(board, word, r + 1, c, k + 1) || found(board, word, r - 1, c, k + 1)
|| found(board, word, r, c + 1, k + 1) || found(board, word, r, c - 1, k + 1);
board[r][c] = keep; // unmark on the way back
return ok;
}
static boolean exist(char[][] board, String word) {
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (found(board, word, r, c, 0)) return true;
return false;
}
function exist(board, word) {
const rows = board.length, cols = board[0].length;
function found(r, c, k) {
if (k === word.length) return true; // every letter matched
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[k]) return false;
const keep = board[r][c];
board[r][c] = "#"; // mark: this path is on the cell
const ok = found(r + 1, c, k + 1) || found(r - 1, c, k + 1)
|| found(r, c + 1, k + 1) || found(r, c - 1, k + 1);
board[r][c] = keep; // unmark on the way back
return ok;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (found(r, c, 0)) return true;
return false;
}
Each printed true, true, false for ABCCED, SEE and ABCB on the grid ["ABCE", "SFCS", "ADEE"]. Writing # over the letter is the visited set, kept in the grid itself, and restoring the letter is the unmark.
Rat in a Maze walks the same way, but wants every path from the top-left corner to the bottom-right one, as strings of D, L, R and U. Trying the four steps in that letter order makes the paths come out already sorted:
def find_paths(mat):
n = len(mat)
out, path = [], []
steps = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0)) # in letter order: the paths come out sorted
def walk(r, c):
if r == n - 1 and c == n - 1:
out.append("".join(path))
return
mat[r][c] = 0 # mark: the path is on this cell
for letter, dr, dc in steps:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and mat[nr][nc] == 1:
path.append(letter)
walk(nr, nc)
path.pop()
mat[r][c] = 1 # unmark on the way back
if mat[0][0] == 1 and mat[n - 1][n - 1] == 1:
walk(0, 0)
return out
On the example maze it returned ['DDRDRR', 'DRDDRR'].
Grids are where this blows up. On the problem's largest board, 6 × 6, all one letter but a B in the corner, the search for a 12-letter word ending in a letter the grid doesn't have made 1,156,248 calls (565 ms) to say no. Two checks before the search fix that kind of input:
from collections import Counter
def exist_pruned(board, word):
have = Counter(ch for row in board for ch in row)
if any(have[ch] < k for ch, k in Counter(word).items()):
return False # the board doesn't hold enough of some letter
if have[word[0]] > have[word[-1]]:
word = word[::-1] # start from the rarer end: fewer cells to start from
return exist(board, word)
Counting the letters first answers that word without a single call. And starting from the rarer end helps when the word is there: the word ending in the B took 26,195 calls from the A's; read backwards from the one B, it took 56.
Place under rules: N-Queens
N-Queens places n queens on an n × n board so that none attacks another: no two in a row, a column or a diagonal. One queen per row takes care of rows, so each call fills one row and tries its columns. The rest is knowing, in one step, whether a square is attacked. Keep three sets: the columns taken, and the two kinds of diagonal. On a down-right diagonal, row − column is the same for every square; on an up-right one, row + column is:
void place(int n, int row, vector<string>& board, vector<bool>& cols, vector<bool>& diag,
vector<bool>& anti, vector<vector<string>>& out) {
if (row == n) { // a queen in every row
out.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if (cols[c] || diag[row - c + n - 1] || anti[row + c]) continue; // attacked: skip it now
cols[c] = diag[row - c + n - 1] = anti[row + c] = true;
board[row][c] = 'Q';
place(n, row + 1, board, cols, diag, anti, out);
board[row][c] = '.';
cols[c] = diag[row - c + n - 1] = anti[row + c] = false;
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> out;
vector<string> board(n, string(n, '.'));
vector<bool> cols(n), diag(2 * n - 1), anti(2 * n - 1); // taken: columns, row - col, row + col
place(n, 0, board, cols, diag, anti, out);
return out;
}
def solve_n_queens(n):
out, board = [], [["."] * n for _ in range(n)]
cols, diag, anti = set(), set(), set() # taken: columns, row - col, row + col
def place(row):
if row == n: # a queen in every row
out.append(["".join(r) for r in board])
return
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue # attacked: skip it now
cols.add(c)
diag.add(row - c)
anti.add(row + c)
board[row][c] = "Q"
place(row + 1)
board[row][c] = "."
cols.remove(c)
diag.remove(row - c)
anti.remove(row + c)
place(0)
return out
static void place(int n, int row, char[][] board, boolean[] cols, boolean[] diag, boolean[] anti,
List<List<String>> out) {
if (row == n) { // a queen in every row
List<String> rows = new ArrayList<>();
for (char[] r : board) rows.add(new String(r));
out.add(rows);
return;
}
for (int c = 0; c < n; c++) {
if (cols[c] || diag[row - c + n - 1] || anti[row + c]) continue; // attacked: skip it now
cols[c] = diag[row - c + n - 1] = anti[row + c] = true;
board[row][c] = 'Q';
place(n, row + 1, board, cols, diag, anti, out);
board[row][c] = '.';
cols[c] = diag[row - c + n - 1] = anti[row + c] = false;
}
}
static List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] r : board) Arrays.fill(r, '.');
List<List<String>> out = new ArrayList<>();
// taken: columns, row - col, row + col
place(n, 0, board, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], out);
return out;
}
function solveNQueens(n) {
const out = [], board = Array.from({length: n}, () => new Array(n).fill("."));
const cols = new Set(), diag = new Set(), anti = new Set(); // taken: columns, row - col, row + col
function place(row) {
if (row === n) { // a queen in every row
out.push(board.map(r => r.join("")));
return;
}
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag.has(row - c) || anti.has(row + c)) continue; // attacked: skip it now
cols.add(c); diag.add(row - c); anti.add(row + c);
board[row][c] = "Q";
place(row + 1);
board[row][c] = ".";
cols.delete(c); diag.delete(row - c); anti.delete(row + c);
}
}
place(0);
return out;
}
Each printed the two boards for n = 4 and 92 for n = 8. In C++ and Java the sets are arrays of booleans: row − column runs from −(n − 1) to n − 1, so it's shifted by n − 1 to make an index. Step through the search for 4 to its first board:
Four queens, row by row — Purple: the queens placed. Indigo: the queen just placed. Dark: the squares of the row being filled that a placed queen attacks. Green: every row filled.
How much checking each queen as it's placed saves, counted:
| n | Boards | Calls, checked as placed | Calls, checked at the end |
|---|---|---|---|
| 4 | 2 | 17 | 341 |
| 5 | 10 | 54 | 3,906 |
| 6 | 4 | 153 | 55,987 |
| 7 | 40 | 552 | 960,800 |
| 8 | 92 | 2,057 | 19,173,961 |
At 8, checking only full boards took 153 ms, even in C++. A fairer baseline puts one queen in each row and each column, the permutations of the last lesson, and checks only the diagonals at the end: 109,601 calls at 8, still 53 times as many. The search stays exponential, but every branch that breaks a rule is cut where it breaks.
Below, you run it yourself. Click the square for the next queen, record a full board, or back up. The loop tries each row's columns left to right, and a square a queen attacks is refused, naming that queen.
Sudoku: three sets per cell, and stop when it's solved
Sudoku Solver fills a 9 × 9 board so every row, column and 3 × 3 box holds each digit once. The rules give three sets for each empty cell: the digits already in its row, its column and its box. With whole-number division, box r // 3 * 3 + c // 3 (r / 3 * 3 + c / 3 in C++ and Java) numbers the boxes 0 to 8, left to right and top to bottom. Each call fills the next empty cell with a digit in none of the three, and the solver stops the moment the last cell is filled, because the board itself is the answer:
bool fill(vector<vector<char>>& board, vector<array<bool, 10>>& rows, vector<array<bool, 10>>& cols,
vector<array<bool, 10>>& boxes, int cell) {
if (cell == 81) return true; // every cell is filled
int r = cell / 9, c = cell % 9, b = r / 3 * 3 + c / 3;
if (board[r][c] != '.') return fill(board, rows, cols, boxes, cell + 1);
for (int d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue; // d is already in its row, column or box
rows[r][d] = cols[c][d] = boxes[b][d] = true;
board[r][c] = char('0' + d);
if (fill(board, rows, cols, boxes, cell + 1)) return true; // solved: stop, and keep the board
board[r][c] = '.';
rows[r][d] = cols[c][d] = boxes[b][d] = false;
}
return false; // nothing fits: the caller tries its next digit
}
void solveSudoku(vector<vector<char>>& board) {
vector<array<bool, 10>> rows(9), cols(9), boxes(9);
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (board[r][c] != '.') {
int d = board[r][c] - '0';
rows[r][d] = cols[c][d] = boxes[r / 3 * 3 + c / 3][d] = true;
}
fill(board, rows, cols, boxes, 0);
}
def solve_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
if board[r][c] != ".":
rows[r].add(board[r][c])
cols[c].add(board[r][c])
boxes[r // 3 * 3 + c // 3].add(board[r][c])
def fill(cell):
if cell == 81:
return True # every cell is filled
r, c = divmod(cell, 9)
b = r // 3 * 3 + c // 3
if board[r][c] != ".":
return fill(cell + 1)
for d in "123456789":
if d in rows[r] or d in cols[c] or d in boxes[b]:
continue # d is already in its row, column or box
rows[r].add(d)
cols[c].add(d)
boxes[b].add(d)
board[r][c] = d
if fill(cell + 1):
return True # solved: stop, and keep the board
board[r][c] = "."
rows[r].remove(d)
cols[c].remove(d)
boxes[b].remove(d)
return False # nothing fits: the caller tries its next digit
fill(0)
static boolean fill(char[][] board, boolean[][] rows, boolean[][] cols, boolean[][] boxes, int cell) {
if (cell == 81) return true; // every cell is filled
int r = cell / 9, c = cell % 9, b = r / 3 * 3 + c / 3;
if (board[r][c] != '.') return fill(board, rows, cols, boxes, cell + 1);
for (int d = 1; d <= 9; d++) {
if (rows[r][d] || cols[c][d] || boxes[b][d]) continue; // d is already in its row, column or box
rows[r][d] = cols[c][d] = boxes[b][d] = true;
board[r][c] = (char) ('0' + d);
if (fill(board, rows, cols, boxes, cell + 1)) return true; // solved: stop, and keep the board
board[r][c] = '.';
rows[r][d] = cols[c][d] = boxes[b][d] = false;
}
return false; // nothing fits: the caller tries its next digit
}
static void solveSudoku(char[][] board) {
boolean[][] rows = new boolean[9][10], cols = new boolean[9][10], boxes = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (board[r][c] != '.') {
int d = board[r][c] - '0';
rows[r][d] = cols[c][d] = boxes[r / 3 * 3 + c / 3][d] = true;
}
fill(board, rows, cols, boxes, 0);
}
function solveSudoku(board) {
const rows = Array.from({length: 9}, () => new Set());
const cols = Array.from({length: 9}, () => new Set());
const boxes = Array.from({length: 9}, () => new Set());
const boxOf = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
for (let r = 0; r < 9; r++)
for (let c = 0; c < 9; c++)
if (board[r][c] !== ".") {
rows[r].add(board[r][c]); cols[c].add(board[r][c]); boxes[boxOf(r, c)].add(board[r][c]);
}
function fill(cell) {
if (cell === 81) return true; // every cell is filled
const r = Math.floor(cell / 9), c = cell % 9, b = boxOf(r, c);
if (board[r][c] !== ".") return fill(cell + 1);
for (const d of "123456789") {
if (rows[r].has(d) || cols[c].has(d) || boxes[b].has(d)) continue; // already in its row, column or box
rows[r].add(d); cols[c].add(d); boxes[b].add(d);
board[r][c] = d;
if (fill(cell + 1)) return true; // solved: stop, and keep the board
board[r][c] = ".";
rows[r].delete(d); cols[c].delete(d); boxes[b].delete(d);
}
return false; // nothing fits: the caller tries its next digit
}
fill(0);
}
Each filled LeetCode's example, first row 53..7.... becoming 534678912.
Which cell to fill next matters a lot. Reading order takes the next empty cell, whatever it allows. Taking the empty cell with the fewest digits that fit instead means fewer guesses, and a wrong guess shows up sooner:
def solve_fewest_first(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empty = set()
for r in range(9):
for c in range(9):
if board[r][c] == ".":
empty.add((r, c))
else:
rows[r].add(board[r][c])
cols[c].add(board[r][c])
boxes[r // 3 * 3 + c // 3].add(board[r][c])
def fits(r, c):
b = r // 3 * 3 + c // 3
return [d for d in "123456789" if d not in rows[r] and d not in cols[c] and d not in boxes[b]]
def fill():
if not empty:
return True
r, c = min(empty, key=lambda cell: len(fits(*cell))) # the most constrained empty cell
b = r // 3 * 3 + c // 3
empty.remove((r, c))
for d in fits(r, c):
rows[r].add(d)
cols[c].add(d)
boxes[b].add(d)
board[r][c] = d
if fill():
return True
board[r][c] = "."
rows[r].remove(d)
cols[c].remove(d)
boxes[b].remove(d)
empty.add((r, c))
return False
fill()
| Puzzle | Calls, reading order | Calls, fewest first |
|---|---|---|
| LeetCode's example | 6,428 | 52 |
| Arto Inkala's | 72,097 | 4,326 |
On LeetCode's example it went from 9 to 3 ms. On Inkala's the calls fell 17-fold, but the time rose from 103 ms to 294: every call scans all the empty cells to find the fewest, and in Python the scan cost more than the calls it saved. Fewer calls is the goal; how cheaply you pick the next cell decides whether time follows.
M-Coloring: a colour per vertex
M-Coloring Problem asks if a graph's vertices can take one of m colours each, with no edge joining two of the same colour. Each call colours the next vertex with a colour none of its neighbours has:
def graph_coloring(v, edges, m):
nbrs = [[] for _ in range(v)]
for a, b in edges:
nbrs[a].append(b)
nbrs[b].append(a)
color = [0] * v # 0: no colour yet
def paint(u):
if u == v:
return True # every vertex has a colour
for k in range(1, m + 1):
if all(color[w] != k for w in nbrs[u]):
color[u] = k # no neighbour has colour k
if paint(u + 1):
return True
color[u] = 0
return False
return paint(0)
For the example's 4 vertices and edges [[0, 1], [1, 3], [2, 3], [3, 0], [0, 2]], 3 colours work and 2 don't: it returned True and False. Vertices 0, 1 and 3 all touch each other, so they need three colours between them.
Spotting it, and when it breaks
The clues. "Find a path on the board that spells", "place n pieces so that none", "fill the grid so every row", "colour so that no two neighbours": choices on a board, each bound by rules. The inputs are tiny: a 6 × 6 grid, n up to 9, one 9 × 9 board, 10 vertices.
The near-misses. The shortest path on a grid: breadth-first search, not backtracking (Shortest Paths with BFS). Counting paths that only go right or down: a table (Grid DP). Many words on the same board: a trie walked alongside the search (Tries for Searching Many Words).
When it breaks. These stay exponential. Every check you add cuts branches, but the worst input still grows the tree fast, which is why the limits are this small. Count first, start from the most constrained choice, and cut a branch the moment it breaks a rule.
Bugs that cost a submission
Not putting the letter back.
keep, board[r][c] = board[r][c], "#"
ok = (found(r + 1, c, k + 1) or found(r - 1, c, k + 1)
or found(r, c + 1, k + 1) or found(r, c - 1, k + 1))
return ok # the cell stays "#"
On the grid ["AAA", "AAB"], exist for "AAB" returned False; with the letter put back it returns True. The first starts fail and leave # behind, and the path that works needs those cells.
One diagonal set.
if c in cols or row - c in diag: # row + c never checked
continue
For n = 4 it returned 7 boards instead of 2: queens on the same up-right diagonal slip through.
Not stopping at the solution.
board[r][c] = d
fill(cell + 1) # its answer ignored
board[r][c] = "."
The board came back with its first row still 53..7....: the search filled every cell, then kept backing out of the solution, emptying each cell on the way.
A maze path that doesn't mark its cells.
for letter, dr, dc in steps: # mat[r][c] = 0 missing
nr, nc = r + dr, c + dc
On the example maze, Python raised RecursionError: with nothing marked, the rat stepped back and forth between two open cells until the stack ran out.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
In this order:
- Word Search: mark the cell, try the neighbours, unmark.
- Rat in a Maze: every path, the steps tried in letter order.
- N-Queens: a row per call, three sets for the attacks.
- M-Coloring Problem: a colour per vertex, checked against its neighbours.
- Sudoku Solver: three sets per cell, and stop at the solution.
Then the section quiz, across all four lessons.