Searching States Depth-First for the Fewest Moves

Depth-first search returns the first route it finds, and the first route is often long; a visited set then stops a shorter route from ever reaching the goal.

Depth-first search finds a route through a graph of states, but not the fewest moves, and letting it run on after the first route does not repair it when states are marked visited. The mistake is tempting because depth-first search is shorter to write and reaches the goal. A counter starts at 1, and each move either adds 1 or doubles it; values above 20 are not allowed, and the goal is 10. No route of 3 moves exists, because 3 moves reach only 4, 5, 6 and 8.

The first listing searches depth-first, trying add 1 before doubling, and keeps searching after the first route to look for a shorter one. The second searches breadth-first.

Depth-first against breadth-first on the counter puzzle

dfs_counter.pypy

LIMIT, GOAL = 20, 10


def next_values(value: int) -> list[int]:
    return [v for v in (value + 1, value * 2) if v <= LIMIT]


visited = {1}
route = [1]
first_found: list[int] | None = None
best: list[int] | None = None


def search(value: int) -> None:
    global first_found, best
    if value == GOAL:
        first_found = first_found or route.copy()
        if best is None or len(route) < len(best):
            best = route.copy()
        return
    for following in next_values(value):
        if following not in visited:
            visited.add(following)
            route.append(following)
            search(following)
            route.pop()


search(1)
print("first route found:", " ".join(map(str, first_found)), f"({len(first_found) - 1} moves)")
print("best after searching on:", " ".join(map(str, best)), f"({len(best) - 1} moves)")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

first route found: 1 2 3 4 5 6 7 8 9 10 (9 moves)
best after searching on: 1 2 3 4 5 6 7 8 9 10 (9 moves)

bfs_counter.pypy

from collections import deque

LIMIT, GOAL = 20, 10


def next_values(value: int) -> list[int]:
    return [v for v in (value + 1, value * 2) if v <= LIMIT]


parent: dict[int, int | None] = {1: None}
queue = deque([1])
while queue:
    value = queue.popleft()
    if value == GOAL:
        break
    for following in next_values(value):
        if following not in parent:
            parent[following] = value
            queue.append(following)

route = [GOAL]
while (previous := parent[route[-1]]) is not None:
    route.append(previous)
route.reverse()
print("route found:", " ".join(map(str, route)), f"({len(route) - 1} moves)")
three_moves = {1}
for _ in range(3):
    three_moves = {v for value in three_moves for v in next_values(value)}
print("values reached in exactly 3 moves:", " ".join(map(str, sorted(three_moves))))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

route found: 1 2 4 5 10 (4 moves)
values reached in exactly 3 moves: 4 5 6 8

Depth-first search follows add 1 all the way to 10 and reports 9 moves. Searching on does not help: on the way it marked every value from 2 to 20 as visited, so when it later tries doubling 5 to reach 10, or 2 to reach 4, those values are already marked and the shorter route is never followed. Breadth-first search reaches values in order of their distance, so the first time it reaches 10, it is by the 4 moves 1, 2, 4, 5, 10. The rule: when every move costs the same, the fewest moves come from breadth-first search. A depth-first search without a visited set would find them, by trying every route, which costs what every route costs.

← → move through sections and cards