← Back to the puzzle · How the computer does it →

Solving it by hand

The searches on the other page suit a computer. People solve sliding puzzles quite differently. They do not search. They finish the puzzle in layers, a row or a column at a time, and never undo what is already done. The two standard methods are layer by layer (LBL) and fringe. This page teaches both, shows them working on a board you can shuffle, and measures how much longer their routes are.

1. The big idea: shrink the puzzle

Suppose you have finished the top row of a 5 × 5 board, and you promise never to touch those five tiles again. The rest of the board is a 4 × 5 puzzle, with the gap somewhere inside it. Finish its left column and lock that too, and what remains is 4 × 4. It is exactly the same kind of puzzle, only smaller. So you do the same again, and again, until a 2 × 2 block is left. That is recursion, and each step is smaller than the last.

It has to go from the outside in. It is tempting to solve a small puzzle in the middle first and then grow outwards, but that fails for a good reason. Once the middle is locked, the gap can only move in the ring of cells around it, and that ring is one tile wide. Tiles in a ring one tile wide can only go round in circles. They can never overtake one another, so their order is fixed, and it will almost never be the right one. The method works from the outside precisely because it always leaves a region at least two cells wide to work in.

The final 2 × 2 is the exception, and a telling one. Its three tiles can only circle round the gap, so their cyclic order never changes. Whether they come out right was settled by the starting position. If they do not, the board you began with could not be solved at all (see the test for this). That is why swapping two tiles to “fix” a stubborn corner never works: it is exactly the kind of change that makes a board impossible.

2. Placing one tile

Only the gap ever moves. A tile moves when the gap is next to it and it slides in. So to bring a tile to a place, you walk the gap to the far side of it and push.

If the gap is already in front of the tile, in the direction you want to go, one move does it. If the gap is behind, it has to travel all the way round the tile first, which takes several moves, typically about five when there is room. So each square of distance a tile must travel costs several moves, and a tile that must cross the board costs dozens. That is why routes by this method are long, and why they grow quickly with the size of the board.

The one rule is to keep the gap out of the finished area. Route the gap round the locked tiles, never through them.

3. The corner trick

Placing the tiles of a line one at a time works until the last two. Take a top row, 1 2 3 4, with 1 and 2 already in place. Put 3 in its home and then try to put 4 in its home beside it. For 4 to slide up into the corner, the gap must be in the corner and 4 directly beneath it. But the gap can only reach the corner by passing through 4’s cell or 3’s cell, so one of them gets knocked out. There is no way round it, so the last two tiles go in together:

  1. Park the second-to-last tile (3) in the corner, where the last tile (4) belongs.
  2. Park the last tile (4) directly beneath it, one step in from the edge.
  3. Bring the gap round to the home of 3, the cell next to the corner.
  4. Slide 3 across into its home, and then slide 4 up into the corner. Both are home, and the gap is back inside the unfinished area.

Here is a real example from a 4 × 4 board, with 3 and 4 outlined:

The awkward case catches nearly every beginner. Suppose 4 is already in the corner, so it is tempting to leave it, but 3 is somewhere else. Leaving 4 there means 3 can only be slotted in by disturbing it. The answer is to knock 4 out on purpose and bring the pair in together. Here the first stage below takes many moves to do that:

A person memorises a fixed sequence of moves for this case. The program behind this page finds the sequence by searching, as it does for every tile. The stages are the same.

4. Two methods: layer by layer and fringe

The corner trick needs room to work, which is why you stop reducing at a 2 × 2 block rather than a 1 × 1. The 15 puzzle page on the Speedsolving.com wiki names two ways of getting down there:

Each number below is the line in which that cell is finished, on a 6 × 6 board.

Layer by layer (LBL)
Fringe

Both finish with the same 2 × 2 and use the same corner trick. They differ only in the order in which lines are locked, which the maps show, and in the length of the routes, which section 6 measures. On a 3 × 3 the two methods are identical. The trainer in the next section runs either one.

5. Try it: a step-by-step trainer

Shuffle a board and let a method solve it, choosing layer by layer or fringe. Next move makes one move, Next stage does a whole stage, and Play keeps going. Locked tiles are shaded green, and the tile or tiles being worked on are outlined. You can also take over at any point by sliding tiles yourself, and the trainer will plan afresh from where you leave the board.

    6. How long are the routes?

    Here the two methods race against the computer on the same random boards. Quick is the weighted A* from the other page; on a 3 × 3 the true shortest route is also shown. The averages are the point, since any one board can go either way.

    Method Average moves Fewest Most Against Quick

    The human methods come out at roughly twice the shortest on a 4 × 4, and longer than Quick at every size. Fringe comes out a few per cent shorter than LBL on square boards from 4 × 4 upwards, which fits the wiki’s verdict that the two are about as fast as each other. The cost grows quickly with the size of the board: on the boards this program was tried on, the average route from 3 × 3 up to 8 × 8 grew a little faster than the cube of the board’s side. A rise of about that order is no accident. A board has about n² tiles, each must travel a distance of the order of n, and every square of that distance costs a handful of moves.

    Finding the shortest route on a large board is a different matter. It is NP-hard, so no known method is guaranteed to find it fast.[1] That is why both people and computers settle for a good route, not the best one, on large boards. Computers search without layers at all: A* and IDA* find the shortest route on a small board, and weighted A* finds a good one on a larger board, as the other page explains.

    7. Records, communities and further reading

    Sliding puzzles have an active community of speedsolvers, with a wiki, forums, a simulator and records.

    Further reading

    8. Common pitfalls

    Reference

    1. Daniel Ratner and Manfred Warmuth, ‘The (n²−1)-Puzzle and Related Relocation Problems’, Journal of Symbolic Computation, 10.2 (1990), 111–137.

    The code is human.js, and the tests that check it solves every solvable board up to 3 × 3, and thousands of larger ones, are in test.js.

    ← Back to the puzzle · How the computer does it →