Day 19 · Week 4

A* Search & Eulerian Path

Level 6 · Advanced · 2 hrs: ~45 min theory · ~60 min code · ~15 min notes

🧠 Mental Model

A* is Dijkstra with a hunch: it adds a heuristic h(n) estimating the remaining distance to the goal, so it explores toward the target instead of uniformly outward. Eulerian path is the opposite kind of problem — traverse every edge exactly once — solved by degree conditions + Hierholzer's algorithm.

Two unrelated advanced tools bundled for the day: one about smarter shortest-path search, one about edge-covering tours.

⚙️ A* — Mechanics

A* orders its frontier by f(n) = g(n) + h(n), where g is the known cost from start and h is the estimated cost to goal. When h ≡ 0, A* degenerates to Dijkstra.

Admissibility & optimality If h never overestimates the true remaining cost (admissible), A* returns an optimal path. If additionally h(u) ≤ w(u,v) + h(v) for every edge (consistent/monotone), no node needs reprocessing.

Why admissibility ⇒ optimality (sketch) Suppose A* returns a suboptimal goal path with cost C > C*. At the moment of popping the goal, some node n on an optimal path sits in the frontier with f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* (admissibility gives h ≤ h*). Then f(n) ≤ C* < C, so n would have been expanded before the suboptimal goal — contradiction. ∎

Common admissible heuristics: Manhattan distance (4-dir grids), Euclidean (free movement), Chebyshev (8-dir).

🔁 Eulerian Path — Conditions & Hierholzer

Existence (undirected): an Eulerian circuit exists iff every vertex has even degree (and edges are connected). An Eulerian path exists iff exactly 0 or 2 vertices have odd degree.

Existence (directed): circuit iff in = out for every vertex; path iff at most one vertex has out − in = 1 (start) and one has in − out = 1 (end), all others balanced.

Hierholzer's algorithm builds the tour in O(E): walk edges greedily, and whenever you get stuck, splice in sub-tours. Implemented with a stack, appending to the route in post-order and reversing at the end.

💻 Reference Implementation (Java)

A* on a grid (Manhattan heuristic), then Hierholzer for an Eulerian path.

import java.util.*;

/** A* on a grid. h = Manhattan distance to goal (admissible for 4-dir). */
public int aStar(int[][] grid, int[] start, int[] goal) {
    int R = grid.length, C = grid[0].length;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int[][] g = new int[R][C];
    for (int[] row : g) Arrays.fill(row, Integer.MAX_VALUE);
    g[start[0]][start[1]] = 0;
    // frontier: {f, r, c}, ordered by f = g + h
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
    pq.offer(new int[]{h(start, goal), start[0], start[1]});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int r = cur[1], c = cur[2];
        if (r == goal[0] && c == goal[1]) return g[r][c];
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr<0||nr>=R||nc<0||nc>=C||grid[nr][nc]==1) continue;
            if (g[r][c] + 1 < g[nr][nc]) {
                g[nr][nc] = g[r][c] + 1;
                int f = g[nr][nc] + h(new int[]{nr,nc}, goal);
                pq.offer(new int[]{f, nr, nc});
            }
        }
    }
    return -1;
}
private int h(int[] a, int[] b) {   // Manhattan — admissible
    return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
}

/** Hierholzer's Eulerian path (directed). Assumes existence conditions hold. */
public List<Integer> eulerian(int start, List<Deque<Integer>> adj) {
    Deque<Integer> stack = new ArrayDeque<>();
    LinkedList<Integer> route = new LinkedList<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.peek();
        if (!adj.get(u).isEmpty()) stack.push(adj.get(u).poll()); // follow an edge
        else route.addFirst(stack.pop());   // stuck ⇒ backtrack, prepend
    }
    return route;  // edges each used exactly once
}

🎭 Problem Variances — A* & Eulerian in disguise

Disguise / phrasing	What's really asked	Twist to handle
"Shortest path on a large grid with a goal"	A* (or BFS/Dijkstra)	Add admissible heuristic to prune; interviews often accept plain BFS
"8-puzzle / sliding puzzle min moves"	A* on state space	Heuristic = misplaced tiles / sum of Manhattan
"Reconstruct itinerary / use all tickets"	Eulerian path	Hierholzer; lexical order → sort adjacency
"Valid arrangement of pairs / dominoes"	Eulerian path on a pair graph	Nodes = values, edges = pairs
"Can you draw this in one stroke?"	Eulerian existence	Check odd-degree count (0 or 2)
"Cracking all codes / de Bruijn sequence"	Eulerian circuit on de Bruijn graph	Overlap edges; Hierholzer

Interview reality: A* rarely appears explicitly (BFS/Dijkstra usually suffice) — know the heuristic idea. Eulerian shows up as "reconstruct itinerary" (LC 332), the one you must be able to code.

⚠️ Common Pitfalls

Inadmissible heuristic: overestimating breaks A*'s optimality. Manhattan on a 4-dir grid is safe; Euclidean on a grid with only orthogonal moves under-uses info but stays admissible.

Eulerian vs Hamiltonian: Eulerian = every edge once (easy, degree conditions). Hamiltonian = every vertex once (NP-hard). Don't conflate.

Hierholzer output order: prepend on backtrack (or reverse at the end) — appending gives the reverse tour.

🎯 Problems

LC 332 Reconstruct Itinerary Eulerian path via Hierholzer; sort adjacency for lexical order. Hard

LC 1091 Shortest Path in Binary Matrix BFS suffices; try adding a Chebyshev heuristic to see A* pruning. Med

LC 753 Cracking the Safe Eulerian circuit on a de Bruijn graph — advanced stretch. Hard

📚 References

Hart, Nilsson & Raphael (1968) — "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. SSC 4(2). The A* paper.
Russell & Norvig, AIMA, Ch. 3 — A*, admissibility, and consistency.
Hierholzer (1873) — "Über die Möglichkeit, einen Linienzug ohne Wiederholung zu umfahren." The Eulerian construction.
Euler (1736) — Seven Bridges of Königsberg; origin of graph theory.

← Day 18: Bridges Day 20: Network Flow + Review →