The first wall: too many paths

The same shape appears in search.

Imagine a problem that gives a computer two possible moves at every step.

After one step, there are 2 paths. After two steps, there are 4. After ten steps, there are 1,024.

Each new step multiplies everything that came before it. This rapid growth is called .

Early programs tried to avoid checking every path by following the ones that looked promising. But as problems grew, the possibilities could multiply faster than any machine could examine them.

A search that worked on a small puzzle could become impossible to finish when the puzzle grew only a little.