Skip to content

Backtracking

In one sentence

Build a solution one choice at a time. After each choice, recurse; when you come back, undo the choice and try the next one. Stop early on any branch that already breaks the rules.

1. What problem does it solve?

Example — 1097B · Petr and a Combination Lock (rating 1200)

A lock's pointer starts at \(0\) on a \(360\)-degree scale. Petr must turn the wheel exactly \(n\) times; the \(i\)-th turn is \(a_i\) degrees, clockwise or counterclockwise. Is there a choice of directions that brings the pointer back to \(0\)?

Limits: \(n \le 15\), \(a_i \le 180\).

Input   Output
3
10
20
30      YES

3
10
10
10      NO

3
120
120
120     YES

First test: \(+10 + 20 - 30 = 0\).

Each turn has two choices, so there are \(2^n\) ways, at most \(2^{15} = 32768\). That is small enough to try them all. Backtracking is the clean way to enumerate them: decide turn \(1\), then turn \(2\), and so on.

2. How backtracking works

2.1 The search tree

Each level of recursion decides one turn. For the first test, with the running angle shown at each node:

graph TD
  S["0"] --> A["+10 → 10"]
  S --> B["−10 → 350"]
  A --> AA["+20 → 30"]
  A --> AB["−20 → 350"]
  B --> BA["+20 → 10"]
  B --> BB["−20 → 330"]
  AA --> AAA["+30 → 60"]
  AA --> AAB["−30 → 0 ✓"]
  AB --> ABA["+30 → 20"]
  AB --> ABB["−30 → 320"]
  BA --> BAA["+30 → 40 "]
  BA --> BAB["−30 → 340"]
  BB --> BBA["+30 → 0 ✓"]
  BB --> BBB["−30 → 300"]

The \(2^3 = 8\) leaves are all possible direction choices. Two of them end at \(0\). Angles are taken modulo \(360\), so \(-10\) is written as \(350\).

2.2 The pattern

dfs(state):
    if the solution is complete: record it, return
    for each choice:
        if choice is allowed:
            make the choice      (update state)
            dfs(next state)
            undo the choice      (restore state exactly)

Undo is what makes this work. After exploring everything below "turn 1 clockwise", the state must be exactly as it was before, so "turn 1 counterclockwise" starts clean.

In the lock problem the state is just one number, so we pass it as an argument: dfs(i + 1, (cur + a[i]) % 360). Returning from the call automatically restores cur, and that is the undo. When the state is a board or a list of used markers, you must undo by hand, as in the queens below.

Pruning means stopping a branch early when it cannot lead to a solution. For the lock, every leaf is a valid choice, so there is nothing to prune; for the queens, most branches are cut immediately.

Cost is roughly the number of nodes in the search tree. For the lock: \(2^{n+1} - 1 \approx 65000\) calls.

2.3 The lesson example: \(n\) queens

Place \(n\) queens on an \(n \times n\) board so that no two share a row, column or diagonal. Every column must hold exactly one queen, so decide column by column which row it goes in.

Search tree on a \(4 \times 4\) board, where Q@r means "queen in row \(r\)":

graph TD
  S[start] --> A0["col 0: Q@0"]
  S --> A1["col 0: Q@1"]
  S --> A2["col 0: Q@2"]
  S --> A3["col 0: Q@3"]
  A0 --> B02["col 1: Q@2"]
  A0 --> B03["col 1: Q@3"]
  B02 --> X1["col 2: no safe row ✗"]
  B03 --> C01["col 2: Q@1"]
  C01 --> X2["col 3: no safe row ✗"]
  A1 --> B13["col 1: Q@3"]
  B13 --> C10["col 2: Q@0"]
  C10 --> D12["col 3: Q@2 ✓"]

Only safe rows are drawn; every other branch is cut immediately. The two branches not expanded are mirror images of the ones shown: col 0: Q@2 mirrors Q@1 and gives the second solution (rows \(2, 0, 3, 1\)), and Q@3 mirrors Q@0 and gives none.

Checking a square in \(O(1)\): diagonal ids.

  • On a "\"-diagonal (going down-right), row and column both increase by \(1\), so \(\text{row} - \text{col}\) is constant.
  • On a "/"-diagonal (going down-left), row increases while column decreases, so \(\text{row} + \text{col}\) is constant.
row + col                 row - col + n   (n = 4, the + n keeps it >= 0)
0 1 2 3                   4 3 2 1
1 2 3 4                   5 4 3 2
2 3 4 5                   6 5 4 3
3 4 5 6                   7 6 5 4

Two squares share a diagonal exactly when they have the same id, so "is this diagonal free?" is one array lookup.

3. Lesson notes — April 12

Notes

Queens

  • Use DFS with backtracking.
  • Place queens column by column.
  • Before placing a queen, check row, column, and two diagonals.
  • After recursion, undo the choice.
def dfs(col):
    if col == n:
        return

    for row in range(n):
        if check(row, col):
            place(row, col)
            dfs(col + 1)
            undo(row, col)
  • Useful diagonal ids:
dia1 = row + col
dia2 = row - col + n

4. Worked solution — Petr and a Combination Lock

dfs(i, cur): turns \(0..i-1\) are decided and the pointer is at cur. Try both directions for turn \(i\).

import sys

input = sys.stdin.readline


def solve():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))

    def dfs(i, cur):
        if i == n:
            return cur == 0
        if dfs(i + 1, (cur + a[i]) % 360):
            return True
        if dfs(i + 1, (cur - a[i]) % 360):
            return True
        return False

    if dfs(0, 0):
        print("YES")
    else:
        print("NO")


solve()

(cur - a[i]) % 360 is never negative in Python, so the angle always stays in \(0..359\).

5. The queens from the lesson, completed

The lesson's check, place and undo filled in with the diagonal ids. For \(n = 8\) it prints \(92\), the number of 8-queens solutions.

n = 8

row_used = [False] * n
dia1_used = [False] * (2 * n)   # row + col
dia2_used = [False] * (2 * n)   # row - col + n
count = 0


def check(row, col):
    return not row_used[row] and not dia1_used[row + col] and not dia2_used[row - col + n]


def place(row, col):
    row_used[row] = True
    dia1_used[row + col] = True
    dia2_used[row - col + n] = True


def undo(row, col):
    row_used[row] = False
    dia1_used[row + col] = False
    dia2_used[row - col + n] = False


def dfs(col):
    global count
    if col == n:
        count += 1
        return

    for row in range(n):
        if check(row, col):
            place(row, col)
            dfs(col + 1)
            undo(row, col)


dfs(0)
print(count)

6. Common mistakes

Forgetting to undo

Then markers stay True after the branch ends, later branches see a board with extra queens, and the count comes out too small.

Undoing something different from what you placed

place and undo must touch exactly the same entries. Writing both as small functions keeps them in sync.

Negative angle or index

row - col can be negative, and in Python a negative index silently reads from the end of a list: add \(n\). For angles, use % 360.

Counting in a local variable

count += 1 inside dfs needs global count (or nonlocal inside another function). Otherwise Python raises UnboundLocalError.

Using backtracking when \(n\) is large

\(2^n\) is fine for \(n \le 20\). For \(n = 40\) it is \(10^{12}\). Check the constraints first (Complexity).

7. Practice

Problem Where Idea
1097B · Petr and a Combination Lock Codeforces · 1200 two choices per step (this page)
550B · Preparing Olympiad Codeforces · 1400 every subset of problems, check the rules
1611C · Polycarp Recovers the Permutation Codeforces · 1000 think about the choices before searching
OJ P2251 April 12 homework search on a grid
Credits & licenses