Card 02/ 08
Find the Fewest Moves Across a Warehouse Floor: From Every Route to One Wave at a Time
Trying every route from one corner to the other meets the same cells again and again; spreading out one move at a time reaches each cell once.
A breadth-first search finds the fewest moves between two cells of a grid by reaching each cell once, where trying every route reaches the same cells again and again. A warehouse robot crosses an open floor of square bays from one corner to the opposite one, moving one bay up, down, left or right at a time. The floor is 5 bays by 5, and the question is the fewest moves the trip takes.
The brute force tries every route: a depth-first search that walks from the start in every direction it can, never stepping on a bay already on the current route, and keeps the shortest route that reaches the far corner. It is correct, and its cost is the number of such routes, which grows faster than any power of the floor's size: 12 routes on a 3 by 3 floor, 184 on 4 by 4 and 8,512 on 5 by 5. The repeated work is that each bay is reached by many routes, and each route explores on from it as though for the first time. A route that reaches a bay in 3 moves learns nothing that the first route to reach it in 3 moves had not already learnt.
Every routeGrows faster than any power of R · C
Explore every route that never revisits a bay, and keep the shortest that reaches the corner. Each bay is explored again for every route through it.
Breadth-first searchO(R · C)
Spread out one move at a time from the start, marking each bay when it is first reached. Each bay is reached once, by a shortest route.
The breadth-first version marks a bay as soon as it is reached, so no second route can add it again. The listing runs both on three floor sizes; the route counts agree with the published count of such paths, OEIS A007764.
from collections import deque
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
def every_route(size: int) -> tuple[int, int]:
routes = 0
fewest = size * size
on_route = [[False] * size for _ in range(size)]
def explore(row: int, col: int, moves: int) -> None:
nonlocal routes, fewest
if (row, col) == (size - 1, size - 1):
routes += 1
fewest = min(fewest, moves)
return
on_route[row][col] = True
for d_row, d_col in DIRECTIONS:
r, c = row + d_row, col + d_col
if 0 <= r < size and 0 <= c < size and not on_route[r][c]:
explore(r, c, moves + 1)
on_route[row][col] = False
explore(0, 0, 0)
return routes, fewest
def breadth_first(size: int) -> tuple[int, int]:
distance = [[-1] * size for _ in range(size)]
distance[0][0] = 0
queue = deque([(0, 0)])
visited = 0
while queue:
row, col = queue.popleft()
visited += 1
for d_row, d_col in DIRECTIONS:
r, c = row + d_row, col + d_col
if 0 <= r < size and 0 <= c < size and distance[r][c] == -1:
distance[r][c] = distance[row][col] + 1
queue.append((r, c))
return visited, distance[size - 1][size - 1]
for size in (3, 4, 5):
routes, fewest = every_route(size)
visited, moves = breadth_first(size)
print(f"{size} by {size}: every route tries {routes:>5} routes, fewest {fewest}; breadth-first visits {visited:>2} cells, fewest {moves}")3 by 3: every route tries 12 routes, fewest 4; breadth-first visits 9 cells, fewest 4
4 by 4: every route tries 184 routes, fewest 6; breadth-first visits 16 cells, fewest 6
5 by 5: every route tries 8512 routes, fewest 8; breadth-first visits 25 cells, fewest 8The run's numbers side by side, with the fewest moves each method found.
| Floor | Routes tried | Cells visited | Fewest moves |
|---|---|---|---|
| 3 by 3 | 12 | 9 | 4 |
| 4 by 4 | 184 | 16 | 6 |
| 5 by 5 | 8,512 | 25 | 8 |
Both methods find 8 moves on the 5 by 5 floor. The breadth-first search visits each of the R · C bays once and looks at four neighbours from each, so it is O(R · C) time and space, and the first time it reaches the far corner, it has the answer. Trying every route is only worth it when the question needs the routes themselves, such as counting them.
← → move through sections and cards