Lab 01 — IDA* & Pattern Databases (15-Puzzle)

Goal

Implement IDA* to solve the 15-puzzle optimally with a Manhattan-distance heuristic, then upgrade the heuristic: linear conflict, then a disjoint 6-6-3 pattern database.

Background

A* stores every generated node. The 15-puzzle has 16!/2 ≈ 1.05×10^13 reachable states; the hardest instances need 80 optimal moves, and A*’s open list grows as O(b^d) with effective branching factor ≈ 2.13 — RAM dies long before depth 50.

Korf (1985), IDA:* depth-first search with an f = g + h cutoff, restarted with the minimum f-value that exceeded the previous cutoff. O(d) memory. First algorithm to solve random 15-puzzle instances optimally (average optimal length ≈ 53).

Korf & Felner (2002), disjoint pattern databases: precompute exact solve costs for disjoint subsets of tiles by backward BFS from the goal; sum the lookups. Their 7-8 split cut Manhattan’s ~4×10^8 average nodes to ~4×10^4.

Admissibility (h never overestimates) gives optimality; consistency (h(u) ≤ 1 + h(v) for a move u→v) makes f non-decreasing along paths. Manhattan distance is both.

Solvability: on a 4×4 board, a state is solvable iff (tile inversions) + (blank row counted from the bottom, 1-based) is odd. Half of all arrangements are unreachable.

Interview Context

• Robotics / motion planning / game-AI roles: heuristic search is core material
• Heuristic-search research (ICAPS, SoCS): the canonical benchmark
• ICPC / Codeforces: IDA* appears occasionally in puzzle problems
• Standard FAANG: LeetCode 773 (Sliding Puzzle) is 2×3 and plain BFS suffices; IDA* and PDBs essentially never required

When to Skip This Topic

Skip if any of these are true:

• You aren’t targeting robotics, planning, game-AI, or research roles
• Plain BFS/DFS and A* on explicit graphs (phase-04) aren’t automatic yet
• Your loop is standard FAANG — LC 773 at 2×3 scale is BFS, done

If you can’t state why A* with an admissible heuristic is optimal, fix that first. This is depth beyond any standard interview loop.

Problem Statement

Optimal 15-Puzzle.

Given a 4×4 board containing tiles 1–15 and one blank (0), return a shortest move sequence reaching the goal (tiles in row-major order, blank last), or report the state unsolvable. A move slides a tile adjacent to the blank into the blank; name moves by the direction the blank travels (U/D/L/R).

Constraints

• Board is 4×4; input is a permutation of 0–15
• Optimal lengths range 0–80; random instances average ≈ 53
• Pure-Python IDA* + Manhattan: instances up to ~40 optimal moves in seconds; beyond that needs linear conflict, a PDB, or C
• Memory: O(d) for the search; the 6-6-3 PDB adds ~11.5 MB

Clarifying Questions

1. Must the solution be optimal, or merely valid? (Optimal — otherwise greedy best-first solves instantly and the lab is pointless.)
2. Is the input guaranteed solvable? (No — detect the unsolvable half via the parity test before searching.)
3. Are moves named by tile motion or blank motion? (Either; state your convention. Blank motion here.)
4. One shortest solution or all of them? (Any one.)

Examples

3×3 warm-up (goal = 1..8 row-major, blank last), showing f = g + h cutoffs:

2 3 1
4 5 6      h = Manhattan = 4  (tile 2: 1, tile 3: 1, tile 1: 2)
7 8 _

IDA* iterations (next cutoff = smallest pruned f):
bound  4 → no goal, min pruned f = 6
bound  6 → 8
bound  8 → 10
bound 10 → 12
bound 12 → 14
bound 14 → 16
bound 16 → 16-move solution (optimal); h underestimated by 12

Unsolvable, detected by parity — no search:

1 3 2
4 5 6      3×3 (odd width): solvable iff inversions even; here 1 → unsolvable
7 8 _

4×4: Sam Loyd's "14-15 puzzle" (goal with 14, 15 swapped):
inversions = 1, blank row from bottom = 1, sum = 2 (even) → unsolvable

Brute Force

Plain BFS with a visited set. Depth 20 ≈ 2.13^20 ≈ 4×10^6 states — fine. Depth 25 ≈ 1.6×10^8 states ≈ 16 GB at ~100 B/state — memory dies around depth 20–25. Average instance needs depth 53.

Brute Force Complexity

• Time: O(b^d), b ≈ 2.13
• Space: O(b^d) — the killer

Optimization Path

1. BFS → A* + Manhattan: far fewer expansions, still O(b^d) memory.
2. A* → IDA*: DFS with f-cutoff, restart at the min pruned f. O(d) memory; re-expansion is a constant factor (geometric growth — see follow-ups).
3. Manhattan → linear conflict: +2 for each pair of tiles in their goal row (or column) in reversed order — they must pass around each other. Still admissible.
4. → disjoint 6-6-3 pattern database: exact costs for tile groups {6, 6, 3}, built by backward BFS over abstracted states. 16P6 = 5,765,760 entries per 6-group, 1 byte each → ~11.5 MB. Node counts drop ~1000× vs Manhattan.

Final Expected Approach

GOAL = tuple(range(1, 16)) + (0,)

def solvable(board):
    tiles = [t for t in board if t]
    inv = sum(1 for i in range(15) for j in range(i + 1, 15)
              if tiles[i] > tiles[j])
    blank_row_from_bottom = 4 - board.index(0) // 4
    return (inv + blank_row_from_bottom) % 2 == 1

def manhattan(board):
    d = 0
    for i, t in enumerate(board):
        if t:
            g = t - 1
            d += abs(i // 4 - g // 4) + abs(i % 4 - g % 4)
    return d

def neighbors(board):
    z = board.index(0)
    r, c = divmod(z, 4)
    for dr, dc, m in ((-1, 0, 'U'), (1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R')):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 4 and 0 <= nc < 4:
            nz = nr * 4 + nc
            nb = list(board)
            nb[z], nb[nz] = nb[nz], nb[z]
            yield tuple(nb), m

def ida_star(start):
    path = [start]
    moves = []

    def search(g, bound):
        board = path[-1]
        f = g + manhattan(board)
        if f > bound:
            return f
        if board == GOAL:
            return True
        best = float('inf')
        for nb, m in neighbors(board):
            if len(path) > 1 and nb == path[-2]:
                continue
            path.append(nb)
            moves.append(m)
            t = search(g + 1, bound)
            if t is True:
                return True
            best = min(best, t)
            path.pop()
            moves.pop()
        return best

    bound = manhattan(start)
    while True:
        t = search(0, bound)
        if t is True:
            return moves
        if t == float('inf'):
            return None
        bound = t

def solve(board):
    board = tuple(board)
    if not solvable(board):
        return None
    return ida_star(board)

Upgrades: replace manhattan with Manhattan + linear conflict, or with sum(pdb[i][key_i(board)] for i in range(3)) for the 6-6-3 PDB. Recompute h incrementally (only the moved tile’s delta) for ~16× fewer heuristic ops.

Data Structures

• Board as a 16-tuple: hashable, cheap to copy
• Explicit path + moves stacks: parent pruning and path return
• PDB: flat byte array keyed by the pattern tiles’ positions

Correctness Argument

• Manhattan is admissible: each move changes one tile’s position by 1, so every tile needs ≥ its distance; consistent: h changes by ±1 per move while g changes by 1.
• IDA* optimality: each cutoff is the exact minimum f pruned previously, so no path of cost < bound was ever discarded; the first goal found within the current bound is therefore optimal.
• Parity: every move preserves (inversions + blank row from bottom) mod 2; the goal’s sum is odd, so even-sum states are unreachable.

Complexity

• Time: O(b^d) worst case; heuristic quality sets the effective exponent. Iterative deepening multiplies by r/(r−1), where r = per-iteration node growth ratio (≈ 4.5 here → ~1.3× overhead)
• Space: O(d) — the whole point

Implementation Requirements

• Prune the immediate parent; without it branching rises from ≈ 2.13 to ≈ 3
• Next cutoff = min pruned f, never bound + 1 (f steps by 2 here — parity of g + h is invariant — but don’t hardcode)
• Do not count the blank in Manhattan
• Return the move path, not just its length
• Run the parity check before any search

Tests

• Goal state → empty path
• One-move state → that single move
• Sam Loyd 14-15 swap → unsolvable, returns immediately
• Random 20-move walks from goal: solve, assert len ≤ 20, replay moves, assert goal reached
• Optimal lengths match plain BFS for scrambles ≤ 12 moves
• Log per-iteration node counts on a ~40-move instance: Manhattan vs linear conflict — conflict must expand strictly fewer

Follow-up Questions

• Why IDA over A*?* → Memory: A* holds O(b^d) nodes — tens of GB by depth 50; IDA* holds one path, O(d). Re-expansion costs only a constant factor.
• How is a pattern database built? → Backward BFS from the goal over abstracted states in which only the pattern tiles (and blank) are distinguishable; all other tiles are wildcards. Store the exact minimum cost for every placement of the pattern tiles. Lookup = a perfect heuristic for the abstraction.
• Why can disjoint PDBs be summed without breaking admissibility? → Each move moves exactly one tile. Partition tiles into disjoint groups and, when building each PDB, count only moves of that group’s tiles. Any real solution’s moves split across the groups, so the sum of per-group lower bounds ≤ true length. Counting blank moves too would double-count — then only max(), not sum, is safe.
• Detect unsolvable inputs without searching? → The parity invariant above: O(n²) inversion count at n = 16 is instant; compare with the goal’s parity.
• Doesn’t iterative deepening waste work re-expanding shallow levels? → Per-iteration node counts grow geometrically with ratio r (≈ b² ≈ 4.5, since cutoffs step by 2). Total = final × (1 + 1/r + 1/r² + …) = final × r/(r−1) ≈ 1.3× the last iteration alone.
• Rubik’s cube? → Korf 1997: IDA* + corner/edge PDBs solved random cubes optimally. Same recipe, bigger tables — see lab-02.

Product Extension

• Warehouse-robot and Sokoban-style planners (PDB abstractions of the map)
• Memory-constrained embedded planners (IDA* on devices without room for open lists)
• Puzzle-game hint engines: optimal next move
• Model checking: directed search over huge implicit state spaces

Language/Runtime Follow-ups

• Python: tuples + dicts beat OO nodes; recursion is fine at depth ≤ 80 but call overhead dominates — an explicit stack plus incremental h gives ~5×. PyPy: ~30×.
• C++: the reference language; pack the board into a 64-bit int (4 bits/tile), PDB as a flat uint8_t array.
• Java: same long-packing works; avoid autoboxed keys in hot maps.
• JavaScript: rare; typed arrays and integer boards if you must.

Common Bugs

1. No parent pruning: undo-moves create 2-cycles; branching jumps to ≈ 3 and deep iterations cost ~10× more.
2. Blank counted in Manhattan: a state one move from goal gets h = 2 — inadmissible, returned paths can be non-optimal.
3. Wrong parity rule: applying the odd-width rule (inversions even) to 4×4; even widths must include the blank’s row.
4. Cutoff update wrong: bound + 1 doubles iteration count (f steps by 2); anything other than min-pruned-f can skip the optimal depth or loop.
5. Path/moves desync: appending a neighbor but not popping on backtrack — returned move list is garbage.
6. Goal test before cutoff test: accepting a goal with f > bound returns a path longer than branches pruned at smaller f — breaks optimality.

Debugging Strategy

• Property test: scramble k moves from goal (k = 1..20), assert solution length ≤ k and replay reaches goal
• Diff optimal lengths against BFS on shallow instances — mismatch means an inadmissible h or cutoff bug
• Log (bound, nodes) per iteration: bounds must step by 2, nodes grow geometrically
• Unit-test h alone: h(goal) = 0; |Δh| = 1 across every single move
• Verify parity on the goal (odd) and on each one-move neighbor (still odd)

Mastery Criteria

• Implement IDA* + Manhattan + parity check in ≤ 60 min, correct on random scrambles
• Add linear conflict in ≤ 30 min and demonstrate the node-count drop
• State the parity invariant and prove one move preserves it
• Explain PDB construction and why disjoint PDBs sum admissibly, unprompted
• Do the memory arithmetic: why A* dies near depth 25 and IDA* doesn’t