Breadth-first search

The three-by-three sliding puzzle: eight tiles in a box, one cell empty, and a tile can slide into the empty cell. How many moves does it take to solve the position in the picture? Trying sequences of moves is useless: there are infinitely many. But you can send a wave out from the solved board: first all positions one move from it, then two, then three, until the wave covers them all. Below, a breadth-first search does this right in your browser. Move the tiles and watch the answer change.

The wave went through all 181,440 positions that can be reached at all, and for each it knows the exact number of moves to the solution. The hardest need 31 moves, and there are exactly two such positions; the “Hardest” button shows both. Almost two thirds of the positions lie in layers of 20 to 25 moves, and on average a position is 22 moves from solved. Turn on the hints: a green tile brings you closer to the solution, a red one takes you away. There are no neutral tiles: every move changes the distance by exactly one. Why will become clear from the proof.

The idea

Walk the graph in rings: first all vertices one step from the start, then two, then three. A queue is all it takes: a vertex is put at the tail when first seen and processed from the head. Since the rings go in order, a vertex is first seen along the shortest path, the one with the fewest edges.

The graph here is not written down anywhere. The vertices are positions, the edges moves, and a position's neighbours are computed on the fly: swap the empty cell with a neighbouring tile. Such a graph is called a state space, and breadth-first search works in it just as in a graph of roads or links.

The scene's second trick is that the traversal starts not from your position but from the solved one. Any move can be undone, so the path from a position to the solution and the path from the solution to the position are the same path read in opposite directions. One traversal from the goal answers the question for all starts at once. A traversal from your position would answer only about it.

How it works: Carroll's doublets

In March 1879 Lewis Carroll published a new game in the magazine Vanity Fair, “doublets”: turn one word into another by changing one letter per move, so that every intermediate word is a real one. His own example is HEAD → HEAL → TEAL → TELL → TALL → TAIL. Words are vertices, a move is an edge, and the shortest chain is a job for breadth-first search. Here it is on a small dictionary of 21 words, step by step. Below is the queue: the head on the left, the tail on the right.

Follow the queue. It never holds words from more than two neighbouring layers: layer k is finishing at the head, and words of layer k + 1 arrive at the tail. So words are taken strictly layer by layer, and by the time layer k + 1 comes up, all closer words have been processed.

Note the steps “already found, skip”. A word is marked at the moment it is seen, not when it is taken from the queue. If it were marked on extraction, a word would get into the queue several times, once from each neighbour in the previous layer. The answer would stay right, but in the sliding puzzle the queue would take 241,921 entries instead of 181,440, and its largest length would grow from 24,059 to 32,751.

When the queue is empty, each word remembers where it was reached from. These links form a tree rooted at the starting word, and the chain to TAIL is read along them backwards. The result is Carroll's own chain. There are other chains in the dictionary, for example through HEAT, BEAT and BELT, but they are all longer, and from HELD there is no way to TAIL at all. If there were several shortest chains, the traversal would take the one the wave reached first.

Why the paths are shortest

Call the layer L_k the set of vertices at distance exactly k from the start s: L₀ = {s}, and L_k+1 is the neighbours of vertices in L_k that are not in earlier layers. Breadth-first search builds these sets one after another.

A useful consequence comes out of the proof. In an undirected graph an edge connects vertices of the same layer or of neighbouring layers: if an edge went from L_k to L_k+2, the far vertex would be at distance k + 1. An edge within one layer closes a cycle of odd length, so a graph can be coloured in two colours with no single-coloured edges if and only if breadth-first search found no edge within a layer. This is how bipartiteness is checked.

The sliding puzzle graph is bipartite: colour the cells of the box like a chessboard, and the empty cell changes colour with every move. There are no edges within a layer, so every move takes a position to a neighbouring layer, one closer or one farther. Hence the hints without neutral tiles.

Code

Python uses deque: popleft costs O(1). In Go the queue is an ordinary slice: queue = queue[1:] only moves the start of the slice and copies nothing. The dictionary dist does double duty: it stores the answer and remembers who has been seen.

And this is the scene from the start of the article: all positions of the sliding puzzle in one traversal from the solved board. A position is a string of nine characters, and moves are computed on the fly. The program prints the size of each layer and both hardest positions:

The layers almost double at each step, 1, 2, 4, 8, 16, then the growth slows, and after the 24th move the layers thin out: almost no new positions are left, and the wave runs into the edges of the space. The sum of all layers is exactly 9!/2: half of the tile arrangements cannot be reached from the solved position. That sliding puzzles of every size are built this way was proved back in 1879 by William Johnson and William Story.

What it costs

Each vertex gets into the queue once: the check “already seen” will not let it in a second time. Each vertex's list of neighbours is looked through once, when it is taken from the queue, so O(E) edges are looked at in all, and in an undirected graph each edge is looked at twice, from both ends. In total O(V + E) time and O(V) memory for the labels and the queue. In the sliding puzzle V = 181,440, there are 241,920 edges and 483,840 neighbour checks.

Linear time rests on one condition: taking from the queue must cost O(1). An ordinary Python list will not do: pop(0) shifts all the remaining elements, and on a wide wave the traversal becomes quadratic. In Go shifting a slice with copy has the same effect. A measurement on random graphs with three edges per vertex:

With the shifting queue the time grows almost as a square: on the right of the chart twice as many vertices take four times as long. With a real queue the slope is about 1.2, not exactly 1: on large graphs every memory access gets more expensive, as the neighbours of a random vertex lie anywhere. At 32 thousand vertices Python with shifting is already two and a half times slower, and the gap grows with the graph.

Memory is worth counting too. The queue holds the whole front of the wave, and on graphs that branch fast it is huge: in the sliding puzzle the queue held up to 24,059 positions at once, one in eight.

Where it breaks

Edge weights

Breadth-first search counts edges. While all steps are worth the same, a move in a puzzle, following a link, a handshake, that is what you need. On a city map steps are unequal: a stretch of avenue between crossroads can be a kilometre, and a stretch of lane thirty metres. Below, breadth-first search and Dijkstra's algorithm look for a path along the same streets of Almaty. Switch the rings: the wave by crossroads stretches along the avenues, where crossroads are few, while the wave by metres spreads out in almost round circles.

From MEGA Alma-Ata to the Central Stadium breadth-first search picks a path of 44 street segments, 7.47 km long, Dijkstra one of 81 segments, but 5.76 km long. Breadth-first search solved a different problem, the one with the fewest crossroads, and solved it correctly. If weights are only 0 and 1, the traversal can still be saved: a vertex found along an edge of weight 0 is put at the front of a deque, not at the tail. This trick, 0-1 BFS, will be needed in the second problem. For arbitrary non-negative weights you need a heap, that is, Dijkstra.

An exploding space

The 3×3 sliding puzzle has 181,440 positions, which is instant. The 4×4 fifteen puzzle has 16!/2 ≈ 1.05 · 10¹³ positions: at one bit per position, more than a terabyte. A full breadth-first traversal of all these positions was first done by Richard Korf and Peter Schultze in 2005. It turned out that the hardest positions need 80 moves, and there are 17 of them. The Rubik's cube has 43,252,003,274,489,856,000 positions, and walking them with a wave is out of the question. That any position can be solved in 20 moves was proved in 2010 by other methods, with about 35 CPU-years of machine time.

When you need a path from one position to another rather than a map of the whole space, the wave is narrowed. Bidirectional search sends two waves towards each other: if each branches b times, two waves of radius d/2 visit about 2b^d/2 vertices instead of b^d. A* pulls the wave towards the goal with a hint about the distance.

Where it is used

Mazes and circuit boards. In 1959 Edward Moore of Bell Labs described a wave for finding the shortest path through a maze. In 1961 C. Y. Lee adapted it for routing wires on printed circuit boards: the cells of the board are vertices, occupied cells are walls. Hence another name, the wave algorithm, or Lee's algorithm. Even earlier, in 1945, the same traversal was described by Konrad Zuse in a thesis on the Plankalkül language, but it was only printed in 1972.

Garbage collection. A copying collector moves live objects into a new area of memory. In 1970 C. J. Cheney noticed that no queue is needed for this: the objects copied but not yet scanned lie one after another in the new area, between the “scanned” pointer and the “free” pointer. This is breadth-first search where the memory itself serves as the queue, and it needs neither a stack nor recursion.

Supercomputers. Since 2010 the Graph 500 ranking has compared machines by the speed of a breadth-first traversal of a huge random graph, in edges per second. For such graphs a two-way traversal was invented: while the front is small, the front's vertices look at their neighbours, and when the front has grown, the other way round, every vertex not yet found looks among its neighbours for at least one in the front and stops at the first. Scott Beamer, Krste Asanović and David Patterson showed in 2012 that on social network graphs this cuts the number of edges examined and speeds up the traversal several times.

Shortest by number of steps. Transfers, handshakes, following links, knight's moves, moves in any puzzle: wherever all steps cost the same. Here breadth-first search is simpler and faster than Dijkstra, and its answer is the same.

Its sibling is depth-first search: the same traversal, but with a stack instead of a queue. It does not find shortest paths; instead it knows things about the structure of a graph that the wave does not see: cycles, order, bridges.

Problems

In the first problem the graph has to be built: a word never has many neighbours, but if every pair of words is compared, the dictionary of “War and Peace” will not fit in the time. In the second the edge weights are 0 and 1, and the queue will have to be replaced by a deque.