← Play Sliding Puzzle

Sliding Puzzle Solving Methods & Algorithms: From Beginner to A* Search

The definitive guide to sliding puzzle algorithms — from the band method beginners learn first, through parity mathematics and Manhattan distance, all the way to the A* search that powers computer solvers. Every technique explained, with drills you can practice in our free sliding puzzle.

Introduction: Why "Sliding Tiles Randomly" Never Works

If you have ever spent ten minutes on a 15-puzzle only to find that placing tile 8 broke tile 7, you already know the problem. The sliding puzzle has 16 positions and 16! / 2 possible states — roughly 10 trillion configurations. You cannot solve it by reaction. You need a method that guarantees progress, regardless of how scrambled the starting position is.

This guide organizes every serious solving method into four tiers: beginner algorithms anyone can learn in five minutes, intermediate strategies used by speed-solvers, the mathematical foundations that explain why some positions are unsolvable, and the computer-science algorithms (A*, IDA*, pattern databases) that find optimal solutions. Each tier builds on the previous one. If you are brand new to the puzzle, start with our how to play sliding puzzle guide first; if you want a quick step-by-step recipe without the theory, the beat the 15-puzzle guide covers the band method in five minutes.

Tier 1: Beginner Algorithms

These three methods solve any standard 15-puzzle without any mathematical background. Pick one, practice it on a 3x3 board, then scale up.

1. The Band Method (Row-by-Row)

The band method is the most widely taught algorithm because it reduces a 2D problem to a series of 1D problems. You solve one complete row (a "band") at a time, shrinking the puzzle as you go.

The algorithm:

  1. Top row first. Place tile 1 in the top-left corner, then tiles 2 and 3 beside it. The trick: place tile 3 below its target, then rotate it up using the empty space to the right of tile 2.
  2. Left column next. Place tiles 4 (and 5 on a 4x4) down the left edge using the same rotate-into-place technique.
  3. Reduce and repeat. With the top row and left column solved, the remaining 3x3 (or 2x3) area is treated as a smaller puzzle. Repeat until only a 2x2 or 2x3 block remains.
  4. Final block. The last few tiles are solved as a unit using a cycling pattern — never place them one at a time.

Why it works: Each solved band is never broken again. The puzzle shrinks predictably, so you always know exactly what to do next. Average solve length is 80-120 moves for a 4x4.

2. The Corner-First Method

Instead of rows, you solve all four corners first (tiles 1, 3, 13, 15 on a standard 4x4). Corners are the hardest tiles to place later because they have two fixed neighbors. Once the frame is locked, the interior edges and center fill in with far less backtracking.

Best for: players who find the last-row breakage problem frustrating. Corner-first eliminates that problem entirely by solving the most constrained positions first.

3. The Edge-Pair Method

Pair each edge tile with its adjacent corner, then slot the pair in together. This is the sliding-puzzle equivalent of the "F2L" (First Two Layers) technique from speed-cubing. It requires more look-ahead than the band method, but produces shorter solutions.

Tier 2: Speed-Solving Techniques

Once you can solve a 4x4 consistently, these three techniques cut your time dramatically.

Look-Ahead

Beginners solve one tile, stop, find the next tile, solve it, stop again. Speed-solvers never pause. While executing the moves for tile 3, their eyes are already tracking tile 4 and planning its placement sequence. This is the single biggest time-saver — most of the gains from practice come from shrinking the pause between tiles, not from faster finger movement.

Move Efficiency

Track your move count. A typical beginner 4x4 solve takes 150-200 moves. An efficient band-method solve takes 80-100 moves. The difference is wasted backtracking — every time you move a solved tile out of the way and put it back, you are spending 4-6 moves that could have been avoided by a better placement sequence. Practice each band until the optimal sequence becomes muscle memory.

The 2x3 Cycling Algorithm

The last block (usually a 2x3 region in the bottom-right) is where most time is lost. The correct technique cycles all six tiles through a fixed loop: move the blank around the perimeter of the block in one direction, and the tiles will rotate through the loop without disturbing the rest of the board. Memorize the 8-move cycle, and the final stage becomes nearly automatic.

Tier 3: The Mathematics of Sliding Puzzles

Understanding the math explains why certain puzzles behave the way they do, and prevents the wasted effort of trying to solve impossible positions.

Permutation Parity

Every sliding puzzle position belongs to one of two classes: solvable or unsolvable. The dividing line is a property called parity, computed by counting inversions. An inversion is any pair of tiles where the higher-numbered tile appears before the lower-numbered tile in reading order.

Solvability test (even-width boards like 4x4):

For odd-width boards (3x3, 5x5), the rule is simpler: the position is solvable if and only if the inversion count is even.

This is why the classic "14-15 puzzle" (with tiles 14 and 15 swapped) is unsolvable — it has exactly one inversion, which fails the parity test on a 4x4 board regardless of blank position.

God's Number

In 2008, Richard Korf proved that every solvable 15-puzzle can be solved in at most 80 moves (half-turn metric). This is the puzzle's "God's Number" — the longest shortest-solution among all solvable positions. For comparison, the 8-puzzle (3x3) has God's Number 31, and the 2x2 pocket cube has God's Number 11. Most random 15-puzzle shuffles require 50-70 moves for an optimal solution.

Tier 4: Computer Science Algorithms

These are the algorithms that actually compute optimal solutions. You do not need to implement them by hand, but understanding them reveals what a "good" solve looks like.

A* Search

A* (pronounced "A-star") is the workhorse algorithm for shortest-path problems. It explores board states in order of f(n) = g(n) + h(n), where:

As long as h(n) never overestimates (an "admissible" heuristic), A* guarantees the shortest solution. The quality of h(n) determines how fast A* finds it.

Manhattan Distance Heuristic

The simplest useful heuristic. For each tile, compute the number of horizontal plus vertical moves needed to reach its goal position, then sum across all 15 tiles. This is admissible because each move can reduce one tile's distance by at most 1 — so the sum is a lower bound on the true solution length. A* with Manhattan distance solves random 15-puzzles in seconds.

Example: If tile 7 sits at position (row 2, col 3) and belongs at (row 2, col 1), its Manhattan distance is |2-2| + |3-1| = 2. Sum this for all tiles.

Linear Conflict

Manhattan distance underestimates because it assumes tiles move independently. Linear conflict adds a correction: when two tiles are in their goal row but reversed, at least two extra moves are required to pass them through each other. Adding 2 moves per conflict produces a tighter heuristic and dramatically fewer states explored.

Pattern Databases

The most powerful heuristic for the 15-puzzle pre-computes the exact solution length for every arrangement of a tile subset (for example, tiles 1-2-3-4 plus the blank). This table is then looked up during search as h(n). Korf's 2008 proof of God's Number used a combination of pattern databases — the "linear split" divides the 15 tiles into three groups and sums their pattern database values, with the maximum used as the heuristic.

IDA* (Iterative Deepening A*)

IDA* is the memory-efficient variant of A* that Korf introduced in 1985. Instead of keeping all explored states in memory, it runs depth-first search with a cost limit, then increases the limit and repeats. It finds the optimal solution using memory proportional to the search depth, not the search width. Combined with Manhattan distance + linear conflict + pattern databases, IDA* is the standard solver for 15-puzzle optimality proofs.

Putting It All Together: A Practice Plan

Theory only helps if you practice it. Here is a four-week plan that takes you from "random sliding" to "sub-2-minute 4x4 solves."

  1. Week 1: Learn the band method. Solve twenty 3x3 puzzles using only the algorithm. Target: consistent solves under 60 seconds.
  2. Week 2: Move to 4x4. Focus on the rotate-into-place technique for placing tiles in the top row. Accept slow solves — accuracy before speed. Target: consistent solves under 5 minutes.
  3. Week 3: Learn the 2x3 cycling algorithm for the final block. Track your move count. Target: move count below 120 per 4x4 solve.
  4. Week 4: Introduce look-ahead. Practice solving two tiles' worth of moves in your head before executing. Target: sub-2-minute 4x4 solves.

You can run every one of these practice sessions in our sliding puzzle game — it supports 3x3, 4x4, and 5x5, tracks your solve times, and always generates solvable positions.

Common Mistakes (and the Algorithm That Fixes Them)

Related Guides

Once you master the sliding puzzle algorithm, these related guides extend your puzzle skills in different directions:

Frequently Asked Questions

What is the best method for beginners to solve a sliding puzzle?

The band method (also called the row-by-row method) is the most reliable beginner approach. Solve the top row first, then the left column, and repeat on the smaller remaining square until you reach a 2x3 or 2x2 block. It reduces a 4x4 puzzle to a series of simple 1D placement problems. Practice on a 3x3 sliding puzzle before moving up to 4x4 — the same algorithm scales perfectly.

What is God's Number for the 15-puzzle?

God's Number for the standard 15-puzzle is 80 moves in the half-turn metric (each slide counts as one move). This was proven by Richard Korf in 2008 using IDA* search with pattern databases. In practice, most random shuffles can be solved in 50-70 moves with an efficient method. If you are taking 150+ moves, you are doing a lot of backtracking — the speed drills in this guide will cut your move count quickly.

How do you know if a sliding puzzle is solvable?

Count the number of inversions (pairs of tiles that appear in reverse numerical order when you read the board left-to-right, top-to-bottom, ignoring the blank). On a 4x4 board with even width, add the row of the blank (counting from the bottom). The puzzle is solvable if and only if: (even width) blank on even row from bottom + even inversions, OR blank on odd row from bottom + odd inversions. On odd-width boards like 3x3, it is solvable if inversions are even. Our sliding puzzle game always generates solvable positions.

What is the Manhattan distance heuristic used for?

Manhattan distance is the most common heuristic for A* search on sliding puzzles. For each tile, you calculate how many horizontal and vertical moves it needs to reach its goal position, then sum all tiles. This sum is a lower bound on the actual number of moves needed — it never overestimates, which is why A* with Manhattan distance guarantees the shortest solution. For example, if tile 7 is two cells right and one cell above its target, its Manhattan contribution is 3.

How can I solve a sliding puzzle faster?

Three techniques cut solve times the most: (1) look-ahead — plan the next tile's placement while you are finishing the current one, so you never pause between moves; (2) move efficiency — most beginners waste 30-40% of moves by backtracking, so practice each placement sequence until it is muscle memory; (3) finger dexterity — on touch devices, use swipes rather than taps for 2-3x speed. Start with timed 3x3 solves on our sliding puzzle, then graduate to 4x4 once you can solve a 3x3 in under 60 seconds consistently.

Why is the last row of a sliding puzzle so hard?

The last row is hard because most players try to place each tile independently, which breaks previously-placed tiles. The correct technique is to solve the last row and last column together as a 2xN block using a cycling algorithm — you rotate tiles around a fixed loop until they all land in place simultaneously. This is the same principle used in the final stage of the band method, but applied with more awareness of which tiles must stay locked.