AlgoScope

Backtracking

Build a solution one choice at a time. Before each choice, check it against what is already placed. If nothing works, undo the last choice and try its next option. That undo is the whole trick: it turns a blind enumeration into a search that abandons a dead branch the moment it is dead. Sudoku is the same loop with a richer constraint: at each empty cell try the digits in order, keep the first that is absent from its row, column and box, and when nothing fits, clear the cell and hand the previous one its next digit.

The player

Sudoku with 12 empty cells.012301231432

A 4 x 4 sudoku: every row, every column and every 2 x 2 box must hold the digits 1 to 4 once each. 12 cells are empty. Fill them in reading order: at each empty cell try the digits in turn, keep the first that does not clash, and go on to the next cell. When no digit fits, the mistake is earlier: clear the cell, go back, and give the previous cell its next digit.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.

  1. Which digit goes into cell (0, 1) first?

    • 2
    • 1
    • 3
    • 4

    Answer: 2. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  2. Which digit goes into cell (0, 2) first?

    • 3
    • 1
    • 2
    • 4

    Answer: 3. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  3. Which digit goes into cell (0, 3) first?

    • None fits, backtrack
    • 1
    • 2
    • 3

    Answer: None fits, backtrack. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  4. Which digit goes into cell (0, 2) first?

    • 2
    • 1
    • 3
    • 4

    Answer: 2. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  5. Which digit goes into cell (0, 3) first?

    • 3
    • 1
    • 2
    • 4

    Answer: 3. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  6. Which digit goes into cell (1, 0) first?

    • 2
    • 1
    • 3
    • 4

    Answer: 2. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  7. Which digit goes into cell (1, 1) first?

    • None fits, backtrack
    • 1
    • 2
    • 3

    Answer: None fits, backtrack. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  8. Which digit goes into cell (1, 1) first?

    • 2
    • 1
    • 3
    • 4

    Answer: 2. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  9. Which digit goes into cell (1, 3) first?

    • 1
    • 2
    • 3
    • 4

    Answer: 1. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  10. Which digit goes into cell (2, 0) first?

    • 2
    • 1
    • 3
    • 4

    Answer: 2. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  11. Which digit goes into cell (2, 2) first?

    • 1
    • 2
    • 3
    • 4

    Answer: 1. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  12. Which digit goes into cell (2, 3) first?

    • 4
    • 1
    • 2
    • 3

    Answer: 4. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  13. Which digit goes into cell (3, 0) first?

    • 4
    • 1
    • 2
    • 3

    Answer: 4. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  14. Which digit goes into cell (3, 1) first?

    • 1
    • 2
    • 3
    • 4

    Answer: 1. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

  15. Which digit goes into cell (3, 2) first?

    • 3
    • 1
    • 2
    • 4

    Answer: 3. Try 1 to 4 in order and keep the first that is absent from the row, the column and the box. If none is, the fault lies in an earlier cell.

How it runs, step by step

  1. A 4 x 4 sudoku: every row, every column and every 2 x 2 box must hold the digits 1 to 4 once each. 12 cells are empty. Fill them in reading order: at each empty cell try the digits in turn, keep the first that does not clash, and go on to the next cell. When no digit fits, the mistake is earlier: clear the cell, go back, and give the previous cell its next digit.

    Sudoku with 12 empty cells.

  2. Cell (0, 1). 1 is already in row 0. 2 fits. 3 is already in column 1. 4 fits. Place 2, the smallest that fits, and move on.

    Place 2 at 0, 1.

  3. Cell (0, 2). 1 is already in row 0. 2 is already in row 0. 3 fits. 4 is already in column 2. Place 3, the smallest that fits, and move on.

    Place 3 at 0, 2.

  4. Cell (0, 3). 1 is already in row 0. 2 is already in row 0. 3 is already in row 0. 4 is already in its box. Nothing fits, so an earlier choice was wrong: clear this and back up.

    Nothing fits at 0, 3.

  5. Every digit that fits cell (0, 2) has been tried and each ran into a dead end further on. Clear it and return to the previous cell.

    Clear 0, 2 and back up.

  6. Back at cell (0, 1): 2 led to a dead end, so try the next digit that fits here, 4.

    Try 4 at 0, 1.

  7. Cell (0, 2). 1 is already in row 0. 2 fits. 3 fits. 4 is already in row 0. Place 2, the smallest that fits, and move on.

    Place 2 at 0, 2.

  8. Cell (0, 3). 1 is already in row 0. 2 is already in row 0. 3 fits. 4 is already in row 0. Place 3, the smallest that fits, and move on.

    Place 3 at 0, 3.

  9. Cell (1, 0). 1 is already in column 0. 2 fits. 3 fits. 4 is already in row 1. Place 2, the smallest that fits, and move on.

    Place 2 at 1, 0.

  10. Cell (1, 1). 1 is already in its box. 2 is already in row 1. 3 is already in column 1. 4 is already in row 1. Nothing fits, so an earlier choice was wrong: clear this and back up.

    Nothing fits at 1, 1.

  11. Back at cell (1, 0): 2 led to a dead end, so try the next digit that fits here, 3.

    Try 3 at 1, 0.

  12. Cell (1, 1). 1 is already in its box. 2 fits. 3 is already in row 1. 4 is already in row 1. Place 2, the smallest that fits, and move on.

    Place 2 at 1, 1.

  13. Cell (1, 3). 1 fits. 2 is already in row 1. 3 is already in row 1. 4 is already in row 1. Place 1, the smallest that fits, and move on.

    Place 1 at 1, 3.

  14. Cell (2, 0). 1 is already in column 0. 2 fits. 3 is already in row 2. 4 fits. Place 2, the smallest that fits, and move on.

    Place 2 at 2, 0.

  15. Cell (2, 2). 1 fits. 2 is already in row 2. 3 is already in row 2. 4 is already in column 2. Place 1, the smallest that fits, and move on.

    Place 1 at 2, 2.

  16. Cell (2, 3). 1 is already in row 2. 2 is already in row 2. 3 is already in row 2. 4 fits. Place 4, the smallest that fits, and move on.

    Place 4 at 2, 3.

  17. Cell (3, 0). 1 is already in column 0. 2 is already in row 3. 3 is already in column 0. 4 fits. Place 4, the smallest that fits, and move on.

    Place 4 at 3, 0.

  18. Cell (3, 1). 1 fits. 2 is already in row 3. 3 is already in column 1. 4 is already in row 3. Place 1, the smallest that fits, and move on.

    Place 1 at 3, 1.

  19. Cell (3, 2). 1 is already in row 3. 2 is already in row 3. 3 fits. 4 is already in row 3. Place 3, the smallest that fits, and move on.

    Place 3 at 3, 2.

  20. Solved: every row, column and box holds 1 to 4 once. 15 digits were placed and 3 undone along the way. Backtracking is exhaustive search made bearable by checking each partial answer as soon as it is written. A 4 x 4 grid barely needs it, but the same code with n = 9 solves any newspaper puzzle in a blink.

    Solved after 15 placements.

The code

Backtracking, in Python

def solve_queens(n, row=0, cols=None):
    if cols is None: cols = [0] * n                # a fresh board for the outermost call
    if row == n: return True                       # every row has a queen
    for c in range(n):
        if safe(cols, row, c):                     # no queen in this column or diagonal
            cols[row] = c                          # choose
            if solve_queens(n, row + 1, cols): return True   # recurse
            # undo is implicit: the next c overwrites
    return False                                   # no square works: caller backtracks

def solve_maze(g, r, c, path):
    if not 0 <= r < len(g) or not 0 <= c < len(g[0]) or g[r][c] != 1:
        return False                               # wall or outside
    path.append((r, c))
    g[r][c] = 2                                    # visited, so no cycles
    if r == len(g) - 1 and c == len(g[0]) - 1: return True
    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if solve_maze(g, r + dr, c + dc, path): return True
    path.pop()                                     # dead end: retreat
    return False

def search(g, w, r, c, k, used):
    if k == len(w): return True                    # every letter matched
    if not 0 <= r < len(g) or not 0 <= c < len(g[0]) or used[r][c] or g[r][c] != w[k]:
        return False
    used[r][c] = True                              # choose: this cell spells w[k]
    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if search(g, w, r + dr, c + dc, k + 1, used): return True
    used[r][c] = False                             # undo: the cell may serve another path
    return False

def solve_sudoku(g, n):
    cell = first_empty(g)
    if cell is None: return True                   # no empty cell left: solved
    r, c = cell
    for d in range(1, n + 1):
        if allowed(g, r, c, d):                    # not already in the row, column or box
            g[r][c] = d                            # choose
            if solve_sudoku(g, n): return True     # recurse
            g[r][c] = 0                            # undo
    return False                                   # every digit failed: caller backtracks

Backtracking, in JavaScript

function solveQueens(n, row = 0, cols = new Array(n).fill(0)) {
  if (row === n) return true;                          // every row has a queen
  for (let c = 0; c < n; c++) {
    if (safe(cols, row, c)) {                          // no queen in this column or diagonal
      cols[row] = c;                                   // choose
      if (solveQueens(n, row + 1, cols)) return true;  // recurse
    }                                                  // undo is implicit: the next c overwrites
  }
  return false;                                        // no square works: caller backtracks
}

function solveMaze(g, r, c, path) {
  if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] !== 1) return false;   // wall or outside
  path.push([r, c]);
  g[r][c] = 2;                                         // visited, so no cycles
  if (r === g.length - 1 && c === g[0].length - 1) return true;
  for (const [dr, dc] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
    if (solveMaze(g, r + dr, c + dc, path)) return true;
  }
  path.pop();                                          // dead end: retreat
  return false;
}

function search(g, w, r, c, k, used) {
  if (k === w.length) return true;                     // every letter matched
  if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || used[r][c] || g[r][c] !== w[k]) return false;
  used[r][c] = true;                                   // choose: this cell spells w[k]
  for (const [dr, dc] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
    if (search(g, w, r + dr, c + dc, k + 1, used)) return true;
  }
  used[r][c] = false;                                  // undo: the cell may serve another path
  return false;
}

function solveSudoku(g, n) {
  const cell = firstEmpty(g);
  if (cell === null) return true;                      // no empty cell left: solved
  const [r, c] = cell;
  for (let d = 1; d <= n; d++) {
    if (allowed(g, r, c, d)) {                         // not already in the row, column or box
      g[r][c] = d;                                     // choose
      if (solveSudoku(g, n)) return true;              // recurse
      g[r][c] = 0;                                     // undo
    }
  }
  return false;                                        // every digit failed: caller backtracks
}

Backtracking, in Kotlin

fun solveQueens(n: Int, row: Int = 0, cols: IntArray = IntArray(n)): Boolean {
    if (row == n) return true                          // every row has a queen
    for (c in 0 until n) {
        if (safe(cols, row, c)) {                      // no queen in this column or diagonal
            cols[row] = c                              // choose
            if (solveQueens(n, row + 1, cols)) return true   // recurse
        }                                              // undo is implicit: the next c overwrites
    }
    return false                                       // no square works: caller backtracks
}

fun solveMaze(g: Array<IntArray>, r: Int, c: Int, path: MutableList<Pair<Int, Int>>): Boolean {
    if (r !in g.indices || c !in g[0].indices || g[r][c] != 1) return false   // wall or outside
    path += r to c
    g[r][c] = 2                                        // visited, so no cycles
    if (r == g.lastIndex && c == g[0].lastIndex) return true
    for ((dr, dc) in listOf(1 to 0, 0 to 1, -1 to 0, 0 to -1)) {
        if (solveMaze(g, r + dr, c + dc, path)) return true
    }
    path.removeLast()                                  // dead end: retreat
    return false
}

fun search(g: Array<CharArray>, w: String, r: Int, c: Int, k: Int, used: Array<BooleanArray>): Boolean {
    if (k == w.length) return true                     // every letter matched
    if (r !in g.indices || c !in g[0].indices || used[r][c] || g[r][c] != w[k]) return false
    used[r][c] = true                                  // choose: this cell spells w[k]
    for ((dr, dc) in listOf(1 to 0, 0 to 1, -1 to 0, 0 to -1)) {
        if (search(g, w, r + dr, c + dc, k + 1, used)) return true
    }
    used[r][c] = false                                 // undo: the cell may serve another path
    return false
}

fun solveSudoku(g: Array<IntArray>, n: Int): Boolean {
    val (r, c) = firstEmpty(g) ?: return true          // no empty cell left: solved
    for (d in 1..n) {
        if (allowed(g, r, c, d)) {                     // not already in the row, column or box
            g[r][c] = d                                // choose
            if (solveSudoku(g, n)) return true         // recurse
            g[r][c] = 0                                // undo
        }
    }
    return false                                       // every digit failed: caller backtracks
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Choose, recurse, undo. The undo is what lets the same code try every branch.
  • Check constraints as early as possible: every square ruled out before recursing prunes a whole subtree.
  • Reach for it on all-solutions and constraint questions: queens, sudoku, mazes, subsets, permutations.

Where this is used

Regular expression enginesText processing

PCRE, Java's java.util.regex and Python's re match by backtracking: at each alternation or quantifier the engine takes one option, recurses on the rest of the pattern, and rewinds the input position when that rest fails. The rewind is what makes backreferences possible at all, since the engine can reconsider how the text was split. It is also why a pattern like (a+)+b can take exponential time on a long run of a's: it is walking a tree of ways to divide the same characters.

pip and Cargo resolving versionsDeveloper tools

Choosing package versions is a constraint problem: pick a version, check it against every requirement already fixed, and on a conflict drop back and take the next candidate. pip's resolver has worked this way since 20.3, which is what the message about looking at multiple versions of a package means - it is backtracking through a release history. Cargo's resolver is the same shape: its documentation describes picking the next version and backtracking when a conflict leaves no solution.

SAT and SMT solversVerification

DPLL, the basis of the CDCL solvers in use today, assigns a variable, propagates the clauses that assignment forces, and undoes the assignment when some clause becomes unsatisfiable. MiniSat and the SAT core inside Z3 add clause learning on top, so a dead branch also records the reason it died and rules out other branches carrying the same conflict. Model checkers and symbolic execution engines run on this loop.

PrologProgramming languages

In Prolog backtracking is not a technique, it is the execution model: the engine tries the first matching clause, binds variables, and on failure unwinds those bindings from a stack called the trail before trying the next clause. Typing a semicolon after an answer forces it to backtrack and produce the next one. The undo step in this lesson is that trail, written by hand.

Why it works this way

Where is the undo in the queens code?

It is there, just invisible: cols[row] = c is overwritten by the next value of c, and no earlier row ever reads that slot while a later row only reads it after it has been written fresh, so no explicit reset is needed. You can skip the undo only when the stale value is unreachable. Sudoku and word search share one grid across the whole search, so g[r][c] = 0 and used[r][c] = false are mandatory - drop either line and a failed branch leaves its guesses behind for every branch that comes after it.

Why the maze keeps its visited marks but word search clears them

Both mark a cell on the way in, and only one clears it on the way out. In the maze a cell that failed can never help again: the first visit tried every continuation from it, and the neighbours it skipped were already visited, so they were either dead too or on the path behind it. Leaving g[r][c] = 2 is a memo rather than a bug. In word search the cell's usefulness depends on the path, since the same square can match a different letter index on another route, so used[r][c] has to go back to false. The test is whether failure at that cell was path-independent.

Which choice you try first changes the running time by orders of magnitude

firstEmpty scans the sudoku grid in reading order, which is the simplest rule and one of the worst. Picking the empty cell with the fewest legal digits instead - the minimum-remaining-values heuristic - fails near the top of the tree, where a failure prunes the most. Same algorithm and same constraints, but hard puzzles drop from millions of assignments to thousands.

Collecting every solution, not just the first

All four functions here return Boolean and stop at the first success. For all solutions you do the opposite: never return early, and at the base case record a copy of the partial solution. Forgetting the copy is the classic bug - you append the live array, it keeps mutating underneath you, and you end up with a list of identical rows, usually the empty starting state.

Read more

Next up