Why Some Puzzles Are Computationally Hard, Even for Computers

Some puzzles are computationally hard because the number of possible positions grows so fast with the size of the puzzle that no computer can check them all, and nobody knows a shortcut that always finds the best answer quickly. For the sliding tile puzzle, finding the shortest solution on a tray of any size is NP-hard, and for route problems such as the travelling salesman problem, the question is NP-complete ^[1], ^[2].

That does not mean every instance is slow to solve. It means that as the puzzle grows, the worst cases grow faster than any known clever trick can keep up with. This article explains where that runaway growth comes from and why the hardest part is often finding the best answer rather than any answer.

What does it mean for a puzzle to be computationally hard?

Specialists in computing judge a puzzle by how the work needed to solve it grows as the puzzle gets bigger, not by how one particular instance feels.

Some growth is gentle. If the work rises with the square or the cube of the size, doubling the size multiplies the work by four or eight. A computer can live with that for a very long time.

Other growth is steep. If the work doubles every time one more piece is added, ten extra pieces multiply the work by about a thousand, and twenty extra pieces by about a million. No hardware upgrade keeps pace with that for long.

A problem is called NP-hard when a fast method for it would also give fast methods for a huge class of other problems that have resisted every attempt so far. Whether a fast method exists at all is still an open question, and no one has found one.

How fast does the number of positions grow?

The sliding tile puzzle makes the growth easy to see. Numbered tiles sit in a tray with one empty cell, and you slide tiles into the gap until they are back in order ^[1].

We counted the reachable positions of the three smaller trays by computer, spreading outward from the solved tray one move at a time. The largest tray in the table is far too big to list that way.

Each step up in size multiplies the number of positions by a huge factor, while the longest shortest solution only grows from 31 moves on the eight-tile tray to 80 on the fifteen-tile tray ^[1].

In each of the three trays we counted, exactly half of all tile arrangements turned out to be reachable. A hidden property of each arrangement, a kind of even or uneven count, never changes when a tile slides, which is why the other half stays out of reach of the solved tray.

The eight-tile tray hides another surprise. In our own count, only two of its positions need the maximum number of moves, while a typical position needs about twenty-two.

Why is finding the best solution harder than finding any solution?

This is the heart of the matter. For the sliding tile puzzle, getting the tiles home at all is easy for a computer, while getting them home in the fewest moves is not.

A paper published on 10 July 2015 summarises both sides ^[1]. Working out the fewest possible moves for the general tray with n rows and n columns has been proved NP-hard ^[1].

Yet the same paper points to a method that solves any solvable tray with a number of moves that grows only like the cube of n ^[1]. It also reports that the work which showed the hardness demonstrated that a polynomial-time approximation algorithm exists ^[1].

So any solution comes cheaply. The best solution is the flip side: being sure that no shorter route exists can mean ruling out a vast number of alternatives. The 2015 paper gives 2n³/3 as the best known lower bound on the expected number of moves, and it expects that both a better method and a better bound exist ^[1].

People feel the same split. Solving a scrambled tray by hand is a pleasant challenge, but being certain that your solution is the shortest possible is a different and much harder kind of question.

Why are route problems like the travelling salesman problem so hard?

Many puzzles ask for a route. Visit every square of a board once, draw a single loop through every dot, or plan the shortest round trip through a set of stops. These all lead to the same group of problems.

The travelling salesman problem asks for the shortest round trip that visits every stop exactly once. A paper published on 21 June 2011 places it among the most basic NP-complete questions about networks ^[2].

Counting the possible trips shows why trying them all fails. Fix the starting stop, list the orders of the others, and treat a trip and its reverse as the same. We counted these by computer: five stops give twelve round trips, and ten stops give one hundred and eighty-one thousand, four hundred and forty, the same number as the reachable positions of the eight-tile tray. Twenty stops give about sixty quadrillion.

Cleverer methods do much better than listing every trip, but they still grow very fast. As the 2011 paper recounts, the best general method for decades needed time that roughly doubled with each added stop, and the same bound applied to merely deciding whether any loop through every point exists ^[2].

As of 21 June 2011, the paper noted, nobody knew whether the general problem could be solved in time growing like 1.999 to the power of the number of stops ^[2].

Why is it hard even to count all the loops?

A closed loop through every point of a network, visiting each point once and coming back to the start, is what loop-drawing puzzles and closed tours on a board ask for.

We checked small networks by computer. Four points, each joined to the other three, allow three different loops. The eight corners of a cube, joined along its edges, allow six.

Ten points arranged as an outer ring of five and an inner ring of five, with each inner point joined to one outer point and to the two inner points two steps away from it, allow none at all. Yet every point there has three lines, just as on the cube.

For networks where every point has exactly three lines, the 2011 paper lists all such loops in time growing like 1.276 to the power of the number of points ^[2]. That speed also limits how many loops these networks can hold ^[2].

The limit cannot drop much further: some of these networks hold about 1.259 to the power of the number of points such loops, so the count really does grow exponentially with size ^[2].

That has a plain consequence. Any method that lists every loop must take at least as long as there are loops to list, so no trick can make the full list quick.

Do clever estimates make hard puzzles easy?

Estimates help a great deal in practice, but they do not remove the worst cases.

A paper published on 21 August 2022 tried two estimate-driven searches on a fifteen-tile tray, one that adds the moves already spent to the estimate and one that trusts the estimate alone ^[3]. Its estimate was a tally of the cells not yet matching the solved tray ^[3].

That paper asks for an estimate that never claims more moves than are really needed ^[3]. Such an estimate keeps the search honest, but it says nothing about how long the search will take on the worst positions.

The trouble is that an estimate is only as good as its closeness to the truth. In our own check of the eight-tile tray, counting out-of-place tiles never gives more than eight, yet some positions need thirty-one moves.

Averaged over every reachable position in that check, the true distance is about twenty-two moves while the estimate is about seven, and the search has to make up that gap by exploring.

On bigger trays the gap widens and the number of positions to explore grows very fast along with it. A better estimate shrinks the search, often dramatically, but for an NP-hard problem no known estimate keeps it small on every instance.

How do the different kinds of hardness compare?

What does this mean for people who solve puzzles?

Hardness in the computer sense is about size. A small instance of a hard problem can be a delightful puzzle, because a person can hold all of it in mind and find the key idea.

Puzzle makers rely on this. They keep the board small enough to be fair and add clues that cut away most of the possibilities, so the solver never has to face the full flood of options. A good clue does for a person what a good estimate does for a computer: it points away from dead ends.

The lesson for solvers is to look for structure before trying options. Counting, symmetry and the even or uneven property behind the sliding tray let you rule out huge groups of positions in one thought, which no amount of blind searching can match.

Can you feel the hardness for yourself?

Next time you face a puzzle, ask two questions. How many options would I have to try if I knew nothing? And which clue lets me skip most of them?

The lock below hides one code among many. Try it by reasoning rather than by trying codes one after another, and notice how each clue shrinks the search.