How Computers Solve Puzzles: Search, Estimates and Logic

Computers solve puzzles by turning each one into a network of positions and then searching that network for a route from the start to the goal. Some searches check positions in a fixed order, some follow an estimate of how close each position is to the goal, and some hand the whole puzzle to a logic engine that tests every possibility against the rules.

This article walks through those methods on one small sliding tile position, compares what each one costs, and ends with a famous puzzle about two hidden numbers that a logic program settles in one go.

What does a computer see when it looks at a puzzle?

A computer does not see tiles, pegs or clues. It sees states. A state is a complete snapshot of the puzzle at one moment: where every piece sits and what is still empty. A move is anything the rules allow that turns one state into another.

Join every state to the states one move away and you get what programmers call a state space. Solving the puzzle becomes a travel problem: find a path through that network from the starting state to a goal state.

The sliding tile puzzle is the standard test case. Numbered tiles sit in a square tray with one empty cell, the only move is to slide a neighbouring tile into the gap, and the aim is to put every tile back in order ^[2]. The version with three rows and three columns, holding eight tiles, is small enough to map completely and large enough to be interesting.

We counted by computer, starting from the solved tray and spreading outward one move at a time, to see how quickly the network grows. Two positions lie one move away, four lie two moves away, eight lie three moves away and sixteen lie four moves away. A paper published on 10 July 2015 notes that every position of this eight-tile tray can be solved within 31 moves ^[2].

Which position will we solve?

Here is the example used in the rest of this article. The gap is in the centre.

The goal is the usual order: one, two, three across the top, then four, five, six, then seven and eight, with the empty cell last, in the lower right.

We checked by computer that the shortest solution takes exactly eight moves. Every method below either finds that eight-move route or settles for a longer one, and that difference is the whole story.

How does breadth-first search find the shortest route?

Breadth-first search is the simplest careful method. It looks at the start, then at every position one move away, then at every position two moves away, and so on, like ripples spreading on a pond.

Because it works outward in rings, the first time it reaches the goal it has reached it by a shortest route. Nothing closer can have been missed, since every closer position was checked first.

The price is effort. In our own run on this example, breadth-first search has to look at every position fewer than eight moves from the start before it can reach the goal, and there are two hundred and one of them. With the moves tried in a fixed order, it examined two hundred and seven positions in total, counting the solved tray itself.

A paper published on 21 August 2022 names breadth-first and depth-first search as the two classic types of search, both usable when the program has no information about how far away the goal is ^[1]. Depth-first search dives down one line of moves as far as it can before backing up, which saves memory but gives no promise that its first answer is the shortest.

What is a heuristic, and why does it help?

A heuristic is a quick estimate of how far a position is from the goal. It does not need to be exact. It only needs to be cheap to compute and to point roughly in the right direction.

The 2022 paper used one of the simplest estimates for sliding tiles: count the cells whose contents differ from the goal ^[1]. The version used in this article counts only the tiles and ignores the gap. Every tile that is out of place will need at least one move, so the count gives a quick sense of how much work remains.

In our example, seven of the eight tiles are out of place, so the estimate is seven, while the true distance is eight. The estimate is a little low, and that is exactly what a good estimate for this job should be.

The same paper describes the key property: a heuristic is called admissible when it never overestimates the real cost ^[1]. We checked by computer, across the entire eight-tile network, that the misplaced-tile count never exceeds the true number of moves for any reachable position.

How does A* search use the estimate?

A* search keeps a list of positions waiting to be explored and always picks the most promising one next. The 2022 paper sets out its scoring rule as f(n) = g(n) + h(n): moves already made plus the estimated moves still needed ^[1].

That sum is the clever part. A position that looks close to the goal but took many moves to reach does not jump the queue, because the moves already spent count against it. The search stays focused without forgetting the cost of the road behind it.

Under the hood the 2022 paper describes two stores: an open set of positions still to be explored, often held in a priority queue so the cheapest is always at the front, and a closed set of positions already explored ^[1].

In our own run, A* with the misplaced-tile estimate returned the eight-move solution after examining only sixteen positions, against the two hundred and seven that breadth-first search needed. Because the estimate never overestimates, A* does not stop early with a longer route.

Why is greedy search fast but sometimes wrong?

Greedy best-first search drops the moves-already-made part and ranks positions by the estimate alone; the 2022 paper writes its score as f(n) = h(n) ^[1]. It always rushes toward whichever position looks closest to the goal.

On the 15-tile position tested in that paper, greedy search needed 22 iterations while A* needed 35, according to the paper's comparison table ^[1]. On that position both methods reached the solved tray, and the A* run shows a 13-move route ^[1]. The paper explains the speed by greedy search ignoring the cost already spent ^[1].

Our eight-tile example shows the flip side. In our own runs, greedy search with the misplaced-tile estimate, breaking ties in the order positions were discovered, returned a route of eighteen moves, more than twice the shortest. Across three hundred runs with ties broken at random, it never did better than eighteen.

The reason is simple. Greedy search always jumps to the position with the lowest count, even when that position sits at the start of a long detour. With nothing to remind it how far it has already travelled, it has no reason to turn back.

How do the search methods compare?

Can a computer solve a puzzle without searching at all?

Yes. For a sliding tray of any size there is a fixed recipe that places tiles one at a time. The 2015 paper describes it: bring each tile of the first row into place using short sequences of moves, then do the same for the first column, then repeat on the smaller tray that remains ^[2].

The recipe never wanders, but it pays in extra moves. The 2015 paper showed that this method makes about 8/3 n³ moves on average, plus smaller terms, for a tray with n rows and n columns, and it tested the figure on 10,000 random positions for each size from 4 to 200 ^[2].

At the very end the recipe falls back on checking every possibility for the last small tray ^[2]. That paper lists the smallest tray, with three tiles, as solvable in six moves, the eight-tile tray in 31 moves and the fifteen-tile tray in 80 moves ^[2].

How does a logic program solve a puzzle?

Some puzzles are not about moving pieces at all. They are about what people know. Here a different kind of tool shines: a logic program, where you write down the rules as facts and conditions and let a solver find every state of affairs that fits.

A paper published on 18 July 2023 used this approach on the well-known sum and product puzzle, in which two people each hold one fact about a pair of hidden whole numbers, the sum or the product, and three brief remarks about who knows what are the only clues ^[3].

The paper turned the number limits and each remark into rules of a logic program and passed them to an answer set solver ^[3]. Only one model came back, and it fixes the hidden pair as 4 and 13 ^[3].

We repeated the idea in its plainest form: a computer listed all two thousand three hundred and fifty-two allowed pairs and crossed off every pair that clashes with each remark in turn, until a single pair was left. No estimate and no route are involved, just the rules tested against every candidate.

Which method should a puzzle solver choose?

It depends on what the puzzle asks for.

• Shortest route, small network. Breadth-first search is simple and always right.
• Shortest route, larger network. A* with an estimate that never overestimates finds the same answer while looking at far fewer positions.
• Any route, quickly. Greedy search or a fixed recipe gets there fast, but the route may be long.
• Facts and clues, no moves. A logic program states the rules once and checks every candidate against them.

People use the same ideas without naming them. Trying every option one step out before going further is breadth-first thinking. Ruling out options that cannot fit the clues is the logic program's method.

Can you try these methods yourself?

Pick a puzzle you know and name its states, its moves and its goal. Then ask which method fits: do you need the shortest answer, or will any answer do?

The riddle below asks for the fewest days on a route, which is exactly the question breadth-first search was built for.