ZERO / HERO
Exploring a maze with breadcrumbs

Backtracking

The analogy

You try a path, and if it leads nowhere you walk back to the last junction and pick the next option — undoing your breadcrumbs as you go. The skill is not the walking, it is noticing early that a corridor cannot possibly work, so you never walk down it at all.

Visualizer

The decision tree, pruned

step 1 / 9
·12312132131123132

The decision tree for permutations of [1,2,3]. Each level chooses one more element.choose / explore / un-choose

def permutations(a):
    out, cur, used = [], [], [False] * len(a)
    def bt():
        if len(cur) == len(a):
            out.append(cur[:])       # copy!
            return
        for i, v in enumerate(a):
            if used[i]:
                continue
            used[i] = True; cur.append(v)      # choose
            bt()                                # explore
            cur.pop();    used[i] = False       # un-choose
    bt()
    return out

def n_queens(n):
    cols, d1, d2, out = set(), set(), set(), []
    def bt(r, board):
        if r == n:
            out.append(board[:]); return
        for c in range(n):
            if c in cols or r-c in d1 or r+c in d2:
                continue                        # PRUNE early
            cols.add(c); d1.add(r-c); d2.add(r+c)
            bt(r + 1, board + [c])
            cols.remove(c); d1.remove(r-c); d2.remove(r+c)
    bt(0, [])
    return out
Check yourself

Where does backtracking actually get its speed?