Constraint Problems and Pruning

28 min · Intermediate

Many problems come with rules: queens that must not attack, digits that must not repeat, a word that must not reuse a cell. The search stays the same, but you check the rule before every choice. A branch that breaks a rule is cut at once, and this is what makes backtracking practical.

Check before you choose

Pruning is skipping a branch of the search as soon as it cannot lead to a valid answer. The earlier the check runs, the more work it saves.

A valid bracket string never closes more than it opened. Test this before adding a bracket and bad paths die at once. Cutting a branch early like this is called pruning.

Python

1def brackets(n):2    result = []3    def walk(path, opened, closed):4        if len(path) == 2 * n:5            result.append("".join(path))6        if opened < n:7            path.append("(")8            walk(path, opened + 1, closed)9            path.pop()10        if closed < opened:11            path.append(")")12            walk(path, opened, closed + 1)13            path.pop()14    walk([], 0, 0)15    return result

Example 1 · Valid brackets for n = 3 and their count

Python

1def brackets(n):2    result = []3    def walk(path, opened, closed):4        if len(path) == 2 * n:5            result.append("".join(path))6        if opened < n:7            path.append("(")8            walk(path, opened + 1, closed)9            path.pop()10        if closed < opened:11            path.append(")")12            walk(path, opened, closed + 1)13            path.pop()14    walk([], 0, 0)15    return result16
17
18print(brackets(3))19print([len(brackets(n)) for n in range(1, 6)])

Output

['((()))', '(()())', '(())()', '()(())', '()()()']
[1, 2, 5, 14, 42]

What this code does

Five strings are valid for three pairs, and none of them is ever built in a wrong form.
The counts 1, 2, 5, 14 and 42 grow fast, but far more slowly than 2 to the power 2n.

Example 2 · Brute force or pruned search

Python

1from itertools import product2
3
4def balanced(text):5    depth = 06    for ch in text:7        depth += 1 if ch == "(" else -18        if depth < 0:9            return False10    return depth == 011
12
13def calls(n, opened=0, closed=0):14    if opened + closed == 2 * n:15        return 116    total = 117    if opened < n:18        total += calls(n, opened + 1, closed)19    if closed < opened:20        total += calls(n, opened, closed + 1)21    return total22
23
24strings = ["".join(p) for p in product("()", repeat=8)]25print("brute force builds", len(strings), "strings,", sum(balanced(s) for s in strings), "are valid")26print("pruned search makes", calls(4), "calls")

Output

brute force builds 256 strings, 14 are valid
pruned search makes 64 calls

What this code does

Brute force builds all 2 to the power 8 strings and checks each one at the end.
The pruned search never extends a path that cannot be valid, so it makes far fewer calls.
The gap widens quickly as n grows.

Two tests guard the choices: no more than n opening brackets, and a closing bracket only while one is still open. No wrong string is ever built.

N-Queens: one queen per row

Constraint is a rule every answer must obey, such as no two queens in one column or diagonal. The search checks it before each choice, so broken paths stop at once.

Place n queens on an n by n board so that none attacks another. Put one queen in each row. A set keeps the lines already used, and a square is safe if none of its three lines is taken.

Python

1def queens(n):2    taken = set()3    def place(row):4        if row == n:5            return 16        count = 07        for col in range(n):8            marks = {("c", col), ("a", row - col), ("b", row + col)}9            if marks & taken:10                continue11            taken.update(marks)                  # choose12            count += place(row + 1)13            taken.difference_update(marks)       # undo14        return count15    return place(0)

Example 3 · Four queens: all solutions

Python

1def solutions(n):2    taken, path, found = set(), [], []3
4    def place(row):5        if row == n:6            found.append(path[:])7            return8        for col in range(n):9            marks = {("c", col), ("a", row - col), ("b", row + col)}10            if marks & taken:11                continue12            taken.update(marks)13            path.append(col)14            place(row + 1)15            path.pop()16            taken.difference_update(marks)17
18    place(0)19    return found20
21
22for cols in solutions(4):23    print(cols)24first = solutions(4)[0]25for col in first:26    print("." * col + "Q" + "." * (3 - col))

Output

[1, 3, 0, 2]
[2, 0, 3, 1]
.Q..
...Q
Q...
..Q.

What this code does

Each solution lists the column of the queen in rows 0 to 3.
Only two solutions exist, and they are mirror images of each other.
The board is printed by repeating dots on either side of the Q.

Example 4 · Solutions as the board grows

Python

1def queens(n):2    taken = set()3    def place(row):4        if row == n:5            return 16        count = 07        for col in range(n):8            marks = {("c", col), ("a", row - col), ("b", row + col)}9            if marks & taken:10                continue11            taken.update(marks)                  # choose12            count += place(row + 1)13            taken.difference_update(marks)       # undo14        return count15    return place(0)16
17
18for n in range(1, 9):19    print(n, queens(n))

Output

What this code does

Some sizes have no solution at all: 2 and 3 print 0.
Eight queens have 92 solutions, found in well under a second.
The numbers do not grow in a smooth line, which is why you cannot guess them.

Example 5 · Pruning against brute force on six queens

Python

1from itertools import permutations2
3calls = [0]4taken = set()5
6
7def place(row, n):8    calls[0] += 19    if row == n:10        return 111    count = 012    for col in range(n):13        marks = {("c", col), ("a", row - col), ("b", row + col)}14        if marks & taken:15            continue16        taken.update(marks)17        count += place(row + 1, n)18        taken.difference_update(marks)19    return count20
21
22def diagonals_ok(p):23    return len({r - c for r, c in enumerate(p)}) == 6 and len({r + c for r, c in enumerate(p)}) == 624
25
26print("boards checked by brute force:", sum(1 for _ in permutations(range(6))))27print("solutions:", sum(1 for p in permutations(range(6)) if diagonals_ok(p)))28place(0, 6)29print("calls made by the pruned search:", calls[0])

Output

boards checked by brute force: 720
solutions: 4
calls made by the pruned search: 153

What this code does

Brute force already uses one queen per row and per column, then checks the diagonals of all 720 boards.
The pruned search stops a branch the moment a queen is attacked, so it makes fewer calls and finds the same 4 solutions.
Without the one-queen-per-row idea, brute force would have to try 6 to the power 6 boards.

A queen uses its column and two diagonals. Squares on one diagonal share row - col, and squares on the other share row + col. A set lookup makes each test take constant time.

Sudoku-style: fill the first empty cell

Dead end is a state where no choice left obeys the rules. The search returns to the previous level, undoes the choice made there and tries the next option.

A 4 by 4 puzzle uses the digits 1 to 4 once in every row, column and 2 by 2 box. Find the first empty cell, try each digit that fits and recurse. If none works, report failure.

Python

1def solve(grid):2    for r in range(4):3        for c in range(4):4            if grid[r][c] == 0:5                for d in range(1, 5):6                    if fits(grid, r, c, d):7                        grid[r][c] = d        # choose8                        if solve(grid):9                            return True10                        grid[r][c] = 0        # undo11                return False                  # no digit fits12    return True                               # no empty cell left

Example 6 · A 4 by 4 puzzle

Python

1def fits(grid, r, c, d):2    if d in grid[r] or d in [row[c] for row in grid]:3        return False4    br, bc = r // 2 * 2, c // 2 * 25    return all(grid[i][j] != d for i in range(br, br + 2) for j in range(bc, bc + 2))6
7
8def solve(grid):9    for r in range(4):10        for c in range(4):11            if grid[r][c] == 0:12                for d in range(1, 5):13                    if fits(grid, r, c, d):14                        grid[r][c] = d        # choose15                        if solve(grid):16                            return True17                        grid[r][c] = 0        # undo18                return False                  # no digit fits19    return True                               # no empty cell left20
21
22grid = [[2, 0, 0, 3], [0, 4, 1, 0], [1, 0, 0, 4], [0, 3, 2, 0]]23if solve(grid):24    for row in grid:25        print("".join(str(d) for d in row))26else:27    print("no solution")

Output

What this code does

The search fills the first empty cell with a digit that fits and moves on; a dead end undoes the digit.
The grid is changed in place, so after a successful solve it holds the answer.
If a puzzle has no solution, solve returns False and the program prints a message instead.

fits checks the row, the column and the box. Setting the cell back to 0 is the undo, and return False tells the caller to change its own guess.

Word search on a grid

Does a word appear in a letter grid by moving up, down, left or right, using each cell once? Overwrite the cell with # while you are inside it, and put the letter back on the way out.

Python

1def exists(grid, word):2    rows, cols = len(grid), len(grid[0])3    def walk(r, c, k):4        if grid[r][c] != word[k]:5            return False6        if k == len(word) - 1:7            return True8        saved, grid[r][c] = grid[r][c], "#"          # choose9        found = any(10            0 <= r + dr < rows and 0 <= c + dc < cols and walk(r + dr, c + dc, k + 1)11            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))12        grid[r][c] = saved                           # undo13        return found14    return any(walk(r, c, 0) for r in range(rows) for c in range(cols))

Example 7 · Words in a letter grid

Python

1def exists(grid, word):2    rows, cols = len(grid), len(grid[0])3    def walk(r, c, k):4        if grid[r][c] != word[k]:5            return False6        if k == len(word) - 1:7            return True8        saved, grid[r][c] = grid[r][c], "#"          # choose9        found = any(10            0 <= r + dr < rows and 0 <= c + dc < cols and walk(r + dr, c + dc, k + 1)11            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))12        grid[r][c] = saved                           # undo13        return found14    return any(walk(r, c, 0) for r in range(rows) for c in range(cols))15
16
17grid = ["CATS", "OREP", "DENT"]18for word in ["CAT", "CORE", "DENT", "TEEN", "CATA"]:19    print(word, exists([list(row) for row in grid], word))

Output

CAT True
CORE True
DENT True
TEEN False
CATA False

What this code does

Each word is searched on a fresh copy of the grid, with the rows turned into lists so cells can be changed.
CATA is False because the A would have to be used twice.
TEEN is False because no E touches the second E in the right order.

The # keeps a path from using one cell twice. The restore runs whether or not a path was found, so the grid is clean for the next start.

Stop at the first answer, or count them all

Sometimes one answer is enough. Return True when you find one and let or stop the rest. To count answers, add up what each child returns and keep searching. The return value must match the question.

Python

1def can_make(nums, i, left):2    if left == 0:3        return True4    if i == len(nums) or left < 0:5        return False6    return can_make(nums, i + 1, left - nums[i]) or can_make(nums, i + 1, left)

Example 8 · One answer or a count

Python

1def can_make(nums, i, left):2    if left == 0:3        return True4    if i == len(nums) or left < 0:5        return False6    return can_make(nums, i + 1, left - nums[i]) or can_make(nums, i + 1, left)7
8
9
10def count_ways(nums, i, left):11    if left == 0:12        return 113    if i == len(nums) or left < 0:14        return 015    return count_ways(nums, i + 1, left - nums[i]) + count_ways(nums, i + 1, left)16
17
18print(can_make([2, 3, 5, 7], 0, 10))19print(count_ways([2, 3, 5, 7], 0, 10))

Output

True
2

What this code does

can_make stops at the first success because or skips its right side.
count_ways adds both branches, so it keeps searching after every success.
Two subsets reach 10: 3 + 7 and 2 + 3 + 5.

or does not run its right side once the left side is True. The test left < 0 prunes paths that already overshoot, as long as every number is positive.

Next step

Check your understanding

12 quick questions

Constraint Problems and Pruning

28 min · Intermediate

Need help? Ask a tutor

Check before you choose

Pruning is skipping a branch of the search as soon as it cannot lead to a valid answer. The earlier the check runs, the more work it saves.

A valid bracket string never closes more than it opened. Test this before adding a bracket and bad paths die at once. Cutting a branch early like this is called pruning.

Python

1def brackets(n):2    result = []3    def walk(path, opened, closed):4        if len(path) == 2 * n:5            result.append("".join(path))6        if opened < n:7            path.append("(")8            walk(path, opened + 1, closed)9            path.pop()10        if closed < opened:11            path.append(")")12            walk(path, opened, closed + 1)13            path.pop()14    walk([], 0, 0)15    return result

Example 1 · Valid brackets for n = 3 and their count

Python

1def brackets(n):2    result = []3    def walk(path, opened, closed):4        if len(path) == 2 * n:5            result.append("".join(path))6        if opened < n:7            path.append("(")8            walk(path, opened + 1, closed)9            path.pop()10        if closed < opened:11            path.append(")")12            walk(path, opened, closed + 1)13            path.pop()14    walk([], 0, 0)15    return result16
17
18print(brackets(3))19print([len(brackets(n)) for n in range(1, 6)])

Output

['((()))', '(()())', '(())()', '()(())', '()()()']
[1, 2, 5, 14, 42]

What this code does

Five strings are valid for three pairs, and none of them is ever built in a wrong form.
The counts 1, 2, 5, 14 and 42 grow fast, but far more slowly than 2 to the power 2n.

Example 2 · Brute force or pruned search

Python

1from itertools import product2
3
4def balanced(text):5    depth = 06    for ch in text:7        depth += 1 if ch == "(" else -18        if depth < 0:9            return False10    return depth == 011
12
13def calls(n, opened=0, closed=0):14    if opened + closed == 2 * n:15        return 116    total = 117    if opened < n:18        total += calls(n, opened + 1, closed)19    if closed < opened:20        total += calls(n, opened, closed + 1)21    return total22
23
24strings = ["".join(p) for p in product("()", repeat=8)]25print("brute force builds", len(strings), "strings,", sum(balanced(s) for s in strings), "are valid")26print("pruned search makes", calls(4), "calls")

Output

brute force builds 256 strings, 14 are valid
pruned search makes 64 calls

What this code does

Brute force builds all 2 to the power 8 strings and checks each one at the end.
The pruned search never extends a path that cannot be valid, so it makes far fewer calls.
The gap widens quickly as n grows.

Two tests guard the choices: no more than n opening brackets, and a closing bracket only while one is still open. No wrong string is ever built.

N-Queens: one queen per row

Constraint is a rule every answer must obey, such as no two queens in one column or diagonal. The search checks it before each choice, so broken paths stop at once.

Place n queens on an n by n board so that none attacks another. Put one queen in each row. A set keeps the lines already used, and a square is safe if none of its three lines is taken.

Python

1def queens(n):2    taken = set()3    def place(row):4        if row == n:5            return 16        count = 07        for col in range(n):8            marks = {("c", col), ("a", row - col), ("b", row + col)}9            if marks & taken:10                continue11            taken.update(marks)                  # choose12            count += place(row + 1)13            taken.difference_update(marks)       # undo14        return count15    return place(0)

Example 3 · Four queens: all solutions

Python

1def solutions(n):2    taken, path, found = set(), [], []3
4    def place(row):5        if row == n:6            found.append(path[:])7            return8        for col in range(n):9            marks = {("c", col), ("a", row - col), ("b", row + col)}10            if marks & taken:11                continue12            taken.update(marks)13            path.append(col)14            place(row + 1)15            path.pop()16            taken.difference_update(marks)17
18    place(0)19    return found20
21
22for cols in solutions(4):23    print(cols)24first = solutions(4)[0]25for col in first:26    print("." * col + "Q" + "." * (3 - col))

Output

[1, 3, 0, 2]
[2, 0, 3, 1]
.Q..
...Q
Q...
..Q.

What this code does

Each solution lists the column of the queen in rows 0 to 3.
Only two solutions exist, and they are mirror images of each other.
The board is printed by repeating dots on either side of the Q.

Example 4 · Solutions as the board grows

Python

1def queens(n):2    taken = set()3    def place(row):4        if row == n:5            return 16        count = 07        for col in range(n):8            marks = {("c", col), ("a", row - col), ("b", row + col)}9            if marks & taken:10                continue11            taken.update(marks)                  # choose12            count += place(row + 1)13            taken.difference_update(marks)       # undo14        return count15    return place(0)16
17
18for n in range(1, 9):19    print(n, queens(n))

Output

What this code does

Some sizes have no solution at all: 2 and 3 print 0.
Eight queens have 92 solutions, found in well under a second.
The numbers do not grow in a smooth line, which is why you cannot guess them.

Example 5 · Pruning against brute force on six queens

Python

1from itertools import permutations2
3calls = [0]4taken = set()5
6
7def place(row, n):8    calls[0] += 19    if row == n:10        return 111    count = 012    for col in range(n):13        marks = {("c", col), ("a", row - col), ("b", row + col)}14        if marks & taken:15            continue16        taken.update(marks)17        count += place(row + 1, n)18        taken.difference_update(marks)19    return count20
21
22def diagonals_ok(p):23    return len({r - c for r, c in enumerate(p)}) == 6 and len({r + c for r, c in enumerate(p)}) == 624
25
26print("boards checked by brute force:", sum(1 for _ in permutations(range(6))))27print("solutions:", sum(1 for p in permutations(range(6)) if diagonals_ok(p)))28place(0, 6)29print("calls made by the pruned search:", calls[0])

Output

boards checked by brute force: 720
solutions: 4
calls made by the pruned search: 153

What this code does

Brute force already uses one queen per row and per column, then checks the diagonals of all 720 boards.
The pruned search stops a branch the moment a queen is attacked, so it makes fewer calls and finds the same 4 solutions.
Without the one-queen-per-row idea, brute force would have to try 6 to the power 6 boards.

A queen uses its column and two diagonals. Squares on one diagonal share row - col, and squares on the other share row + col. A set lookup makes each test take constant time.

Sudoku-style: fill the first empty cell

Dead end is a state where no choice left obeys the rules. The search returns to the previous level, undoes the choice made there and tries the next option.

A 4 by 4 puzzle uses the digits 1 to 4 once in every row, column and 2 by 2 box. Find the first empty cell, try each digit that fits and recurse. If none works, report failure.

Python

1def solve(grid):2    for r in range(4):3        for c in range(4):4            if grid[r][c] == 0:5                for d in range(1, 5):6                    if fits(grid, r, c, d):7                        grid[r][c] = d        # choose8                        if solve(grid):9                            return True10                        grid[r][c] = 0        # undo11                return False                  # no digit fits12    return True                               # no empty cell left

Example 6 · A 4 by 4 puzzle

Python

1def fits(grid, r, c, d):2    if d in grid[r] or d in [row[c] for row in grid]:3        return False4    br, bc = r // 2 * 2, c // 2 * 25    return all(grid[i][j] != d for i in range(br, br + 2) for j in range(bc, bc + 2))6
7
8def solve(grid):9    for r in range(4):10        for c in range(4):11            if grid[r][c] == 0:12                for d in range(1, 5):13                    if fits(grid, r, c, d):14                        grid[r][c] = d        # choose15                        if solve(grid):16                            return True17                        grid[r][c] = 0        # undo18                return False                  # no digit fits19    return True                               # no empty cell left20
21
22grid = [[2, 0, 0, 3], [0, 4, 1, 0], [1, 0, 0, 4], [0, 3, 2, 0]]23if solve(grid):24    for row in grid:25        print("".join(str(d) for d in row))26else:27    print("no solution")

Output

What this code does

The search fills the first empty cell with a digit that fits and moves on; a dead end undoes the digit.
The grid is changed in place, so after a successful solve it holds the answer.
If a puzzle has no solution, solve returns False and the program prints a message instead.

fits checks the row, the column and the box. Setting the cell back to 0 is the undo, and return False tells the caller to change its own guess.

Word search on a grid

Does a word appear in a letter grid by moving up, down, left or right, using each cell once? Overwrite the cell with # while you are inside it, and put the letter back on the way out.

Python

1def exists(grid, word):2    rows, cols = len(grid), len(grid[0])3    def walk(r, c, k):4        if grid[r][c] != word[k]:5            return False6        if k == len(word) - 1:7            return True8        saved, grid[r][c] = grid[r][c], "#"          # choose9        found = any(10            0 <= r + dr < rows and 0 <= c + dc < cols and walk(r + dr, c + dc, k + 1)11            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))12        grid[r][c] = saved                           # undo13        return found14    return any(walk(r, c, 0) for r in range(rows) for c in range(cols))

Example 7 · Words in a letter grid

Python

1def exists(grid, word):2    rows, cols = len(grid), len(grid[0])3    def walk(r, c, k):4        if grid[r][c] != word[k]:5            return False6        if k == len(word) - 1:7            return True8        saved, grid[r][c] = grid[r][c], "#"          # choose9        found = any(10            0 <= r + dr < rows and 0 <= c + dc < cols and walk(r + dr, c + dc, k + 1)11            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))12        grid[r][c] = saved                           # undo13        return found14    return any(walk(r, c, 0) for r in range(rows) for c in range(cols))15
16
17grid = ["CATS", "OREP", "DENT"]18for word in ["CAT", "CORE", "DENT", "TEEN", "CATA"]:19    print(word, exists([list(row) for row in grid], word))

Output

CAT True
CORE True
DENT True
TEEN False
CATA False

What this code does

Each word is searched on a fresh copy of the grid, with the rows turned into lists so cells can be changed.
CATA is False because the A would have to be used twice.
TEEN is False because no E touches the second E in the right order.

The # keeps a path from using one cell twice. The restore runs whether or not a path was found, so the grid is clean for the next start.

Stop at the first answer, or count them all

Python

1def can_make(nums, i, left):2    if left == 0:3        return True4    if i == len(nums) or left < 0:5        return False6    return can_make(nums, i + 1, left - nums[i]) or can_make(nums, i + 1, left)

Example 8 · One answer or a count

Python

1def can_make(nums, i, left):2    if left == 0:3        return True4    if i == len(nums) or left < 0:5        return False6    return can_make(nums, i + 1, left - nums[i]) or can_make(nums, i + 1, left)7
8
9
10def count_ways(nums, i, left):11    if left == 0:12        return 113    if i == len(nums) or left < 0:14        return 015    return count_ways(nums, i + 1, left - nums[i]) + count_ways(nums, i + 1, left)16
17
18print(can_make([2, 3, 5, 7], 0, 10))19print(count_ways([2, 3, 5, 7], 0, 10))

Output

True
2

What this code does

can_make stops at the first success because or skips its right side.
count_ways adds both branches, so it keeps searching after every success.
Two subsets reach 10: 3 + 7 and 2 + 3 + 5.

or does not run its right side once the left side is True. The test left < 0 prunes paths that already overshoot, as long as every number is positive.

Next step

Check your understanding

12 quick questions