A*, Iterative Deepening and IDA* Search

A* and its relatives are an extension topic beyond most interviews; they pay off in robotics, mapping and game-AI rounds, and in "fewest moves" puzzles (sliding tiles) where plain BFS explores far too many states.

All of them add one ingredient to ordinary shortest-path search: a heuristic h(x), an estimate of the remaining cost from state x to the goal. The search uses it to look at promising states first and to skip states that cannot lie on a cheaper path.

Intuition

A*. Dijkstra's algorithm always expands the state with the smallest known cost g(x) from the start. A* expands the state with the smallest f(x) = g(x) + h(x), the estimated cost of a full path through x. With h = 0, A* is exactly Dijkstra.

• Admissible heuristics never overestimate: h(x) <= true remaining cost. Then A* returns an optimal path.
• Consistent heuristics satisfy a triangle inequality: h(x) <= cost(x, y) + h(y) for every move from x to y. Then f never decreases along a path, each state is finalized the first time it is popped (like Dijkstra), and a stale-entry check is enough. Consistent implies admissible.
• The closer h is to the true cost, the fewer states A* expands. A perfect h walks straight to the goal; h = 0 explores like Dijkstra.

Typical heuristics: on a 4-directional grid where every move costs at least 1, the Manhattan distance |dr| + |dc|; with diagonal moves, the Chebyshev or octile distance; in continuous space, the straight-line distance; in sliding puzzles, the number of misplaced tiles or the sum of each tile's Manhattan distance to its target (larger, hence better, and still admissible because each move shifts one tile by one cell).

Iterative deepening DFS (IDDFS). Run a depth-limited DFS with limit 0, 1, 2, ... until the goal is found. It finds the shallowest goal like BFS but uses only O(depth) memory. Re-exploring the upper levels each round costs little, because in a tree with branching factor b at least 2, the last level dominates the total.

IDA*. Iterative deepening where the limit is on f = g + h instead of on depth. Each round is a DFS that prunes any state whose f exceeds the bound; the next bound is the smallest f that was pruned. It keeps A*'s optimality with the memory of a DFS, which is why it is the classic way to solve the 15-puzzle optimally.

Unsolvable inputs. Search cannot prove impossibility cheaply in a huge space, so check it first when you can. Sliding puzzles have an exact test based on the parity of inversions (pairs of tiles in the wrong relative order, blank excluded). A horizontal move never changes the inversion count; a vertical move moves one tile past cols - 1 others. With an odd number of columns that is an even change, so the inversion parity is invariant and must be even. With an even number of columns the parity flips together with the blank's row, so inversions + (blank row counted from the bottom, starting at 1) must be odd.

When to use it in interviews / OAs

• Shortest paths on large grids or maps toward a single known target, with a natural geometric lower bound (A*).
• Sliding puzzles and similar "fewest moves to a fixed goal configuration" problems, where the state space explodes (A* or IDA*, after a solvability check).
• Searches where the answer depth is small but the branching factor is high and memory is tight (IDDFS, IDA*).
• Discussions of how game or robot path planning works, and why Dijkstra alone is slower toward a single target.

Template

A* on a weighted grid

import heapq


def a_star_grid(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int]) -> int:
    """Cheapest cost from start to goal. Entering cell (r, c) costs grid[r][c] >= 1; 0 is a wall."""
    rows, cols = len(grid), len(grid[0])

    def h(r: int, c: int) -> int:  # Manhattan distance: consistent because every step costs >= 1
        return abs(r - goal[0]) + abs(c - goal[1])

    best = {start: 0}  # cheapest known g for each cell
    heap = [(h(*start), 0, start)]  # (f, g, cell)
    while heap:
        _, g, (r, c) = heapq.heappop(heap)
        if (r, c) == goal:
            return g
        if g > best[(r, c)]:
            continue  # stale entry: a cheaper path to this cell was found later
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > 0:
                ng = g + grid[nr][nc]
                if ng < best.get((nr, nc), float("inf")):
                    best[(nr, nc)] = ng
                    heapq.heappush(heap, (ng + h(nr, nc), ng, (nr, nc)))
    return -1

Sliding puzzle: moves, heuristic, solvability

A board is a tuple read row by row, with 0 as the blank; the goal is 1, 2, ..., rows*cols - 1, 0.

def slide_moves(state: tuple[int, ...], rows: int, cols: int):
    """All boards reachable by sliding one tile into the blank."""
    z = state.index(0)
    zr, zc = divmod(z, cols)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = zr + dr, zc + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            s = list(state)
            j = nr * cols + nc
            s[z], s[j] = s[j], s[z]
            yield tuple(s)


def manhattan_heuristic(rows: int, cols: int):
    target = {v: divmod(v - 1, cols) for v in range(1, rows * cols)}  # where tile v belongs

    def h(state: tuple[int, ...]) -> int:
        total = 0
        for i, v in enumerate(state):
            if v:
                r, c = divmod(i, cols)
                total += abs(r - target[v][0]) + abs(c - target[v][1])
        return total

    return h


def solvable(state: tuple[int, ...], rows: int, cols: int) -> bool:
    tiles = [v for v in state if v]
    inversions = sum(1 for i in range(len(tiles)) for j in range(i + 1, len(tiles)) if tiles[i] > tiles[j])
    if cols % 2 == 1:
        return inversions % 2 == 0
    blank_row_from_bottom = rows - state.index(0) // cols  # the bottom row is 1
    return (inversions + blank_row_from_bottom) % 2 == 1

A* on the puzzle

def sliding_puzzle(board: list[list[int]]) -> int:
    rows, cols = len(board), len(board[0])
    start = tuple(v for row in board for v in row)
    goal = tuple(list(range(1, rows * cols)) + [0])
    if not solvable(start, rows, cols):
        return -1  # avoid exploring half of the state space for nothing
    h = manhattan_heuristic(rows, cols)
    best = {start: 0}
    heap = [(h(start), 0, start)]
    while heap:
        _, g, state = heapq.heappop(heap)
        if state == goal:
            return g
        if g > best[state]:
            continue
        for nxt in slide_moves(state, rows, cols):
            if g + 1 < best.get(nxt, float("inf")):
                best[nxt] = g + 1
                heapq.heappush(heap, (g + 1 + h(nxt), g + 1, nxt))
    return -1

IDA*

def ida_star(start, goal, neighbors, h) -> int:
    """Fewest unit-cost moves from start to goal using O(depth) memory; h must be admissible.
    Only call it when the goal is reachable: otherwise it keeps exploring before giving up."""
    path, on_path = [start], {start}
    FOUND = -1

    def search(g: int, bound: int) -> int:
        node = path[-1]
        f = g + h(node)
        if f > bound:
            return f  # pruned: report how far over the bound it was
        if node == goal:
            return FOUND
        smallest = float("inf")
        for nxt in neighbors(node):
            if nxt not in on_path:  # avoid cycles along the current path
                path.append(nxt)
                on_path.add(nxt)
                t = search(g + 1, bound)
                if t == FOUND:
                    return FOUND
                smallest = min(smallest, t)
                path.pop()
                on_path.remove(nxt)
        return smallest

    bound = h(start)
    while True:
        t = search(0, bound)
        if t == FOUND:
            return len(path) - 1
        if t == float("inf"):
            return -1
        bound = t  # the next round allows the smallest f that was pruned

With h = lambda s: 0 this is plain iterative deepening DFS.

Complexity

• A* with a consistent heuristic expands each state at most once: O(E log V) in the worst case, like Dijkstra, and often far fewer states in practice. Memory is O(V) for the open set and the best-cost map, and that memory is usually what runs out first.
• IDA*: O(depth) memory. Time is roughly the number of nodes with f no larger than the optimal cost, times a modest factor for repeated rounds.
• The solvability test is O(k^2) for k tiles as written (O(k log k) with merge-sort inversion counting).
• 8-puzzle boards have 9!/2 = 181,440 reachable states; 15-puzzle boards have about 10^13, which is why the heuristic and IDA* matter there.

Common pitfalls

• Overestimating heuristics (for example Manhattan distance on a grid that allows diagonal moves, or counting a tile's distance twice) lose optimality.
• Stopping when the goal is pushed instead of when it is popped. Only the pop guarantees the cost is final.
• Skipping the stale-entry check with lazy deletion, which re-expands states many times.
• Inconsistent but admissible heuristics need reopening: allow a state to be pushed again whenever a cheaper g is found (the code above does this through the best map).
• Running IDA or A on an unsolvable puzzle**: half of all boards cannot reach the goal, and the search will explore everything first. Check parity before searching.
• Mutable states. Use tuples or strings so states can be hashed and compared.

Interview variations

• Sliding puzzle (2 x 3): BFS is enough for 720 states, but A* with Manhattan distance is the natural follow-up; the solvability test answers the "-1" case instantly.
• Shortest path in a grid toward one target, with or without obstacles and weights: A* with Manhattan or octile distance.
• Robot or game path planning: discuss A*, weighted A* (multiply h by a factor greater than 1 for speed at the cost of optimality) and when Dijkstra or BFS is enough.
• 8-puzzle or 15-puzzle solvability: the inversion-parity rule alone.
• Word ladder or open the lock with a heuristic (the number of mismatched characters or wheel distances) as an alternative to bidirectional BFS.