Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 46 ยท Projects

Project: Sliding-Puzzle Solver

Build a generic 8- and 15-puzzle solver in Python: solvability check, BFS, A* with two heuristics and IDA*, then benchmark them in a results table.

In this project you put the whole search toolkit to work. You will write one small, reusable model of the sliding puzzle (the 3x3 "8-puzzle" and the 4x4 "15-puzzle"), plug in three different solvers, and measure how they compare. By the end you will have a solver that handles 15-puzzle boards in a fraction of a second and a benchmark table that shows, with real numbers, why heuristics matter.

You need the ideas from problem formulation, breadth-first search, A*, admissible heuristics and IDA*. Everything runs in your browser, so keep the instances modest: the 15-puzzle has about 10^13 reachable positions, and hard boards need more time and memory than a web page offers.

The design

A good solver separates three concerns, so each can be tested and swapped on its own:

  1. The problem model: what a state is, which moves exist, the goal, and the facts about the puzzle (solvability, heuristics).
  2. The solvers: generic algorithms that know nothing about tiles. They call successors(state) and compare against goal.
  3. The benchmark: a harness that runs each solver on the same boards and reports solution length, nodes expanded and time.
graph LR
    M["SlidingPuzzle<br/>successors, goal,<br/>heuristics"] --> B["BFS"]
    M --> A["A*"]
    M --> I["IDA*"]
    B --> H["Benchmark<br/>harness"]
    A --> H
    I --> H
    H --> T["Results table"]

One model, three interchangeable solvers, one harness that treats them all alike.

A state is a tuple of n*n numbers read row by row, with 0 for the blank. A tuple is immutable and hashable, so it can go straight into the sets and dictionaries that the search algorithms use. A move slides a neighboring tile into the blank, which is the same as moving the blank up, down, left or right. Each move costs 1.

Step 1: Is the board solvable?

Before searching, check that a solution exists. Exactly half of all arrangements of a sliding puzzle are unreachable from the goal: they can never be solved by legal moves, and a search on one of them would run until memory is exhausted. The parity test is cheap.

Count the inversions of the board: pairs of tiles (ignoring the blank) where a larger number comes before a smaller one when you read row by row. Every move of the blank sideways does not change the sequence of tiles at all, and a vertical move jumps one tile over n - 1 others, which changes the inversion count by an even number when n is odd. This gives the rules:

  • Odd width (3x3): solvable exactly when the number of inversions is even.
  • Even width (4x4): solvable exactly when inversions + row of the blank counted from the bottom (starting at 1) is odd.

Does the formula really work? The program checks it against the ground truth: it floods outward from the goal and counts every state it can reach.

Python Solvability: the parity rule versus a full flood fill

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The flood fill reaches 181,440 states, exactly half of the 362,880 possible arrangements, and the formula agrees on every one of the 20,160 boards we sample. The famous "14-15 puzzle" (the 4x4 board with only tiles 14 and 15 swapped) is correctly reported as unsolvable, which shows why that old challenge could never be won.

Always validate input at the edge of your program. A solver that happily loops forever on an unsolvable board is a bug in the user's eyes, even though the algorithm is correct.

Step 2: Heuristics

Two admissible heuristics are available, and the second dominates the first (see admissible heuristics):

  • Misplaced tiles: how many tiles are not on their goal square. Each misplaced tile needs at least one move.
  • Manhattan distance: the sum over tiles of the horizontal plus vertical distance to the goal square. Each move shifts one tile by one square, so at least that many moves are needed.

Both ignore the blank and the other tiles in the way, which is exactly the relaxation that makes them admissible. Manhattan distance is always at least as large as misplaced tiles, so A* guided by it expands fewer nodes.

Step 3: Three solvers

All three share the same interface: solver(problem, start) returns the solution path (a list of states) and the number of nodes expanded.

  • BFS explores by depth. It is optimal for unit costs, needs no heuristic, and stores every state it has seen, so memory is its limit.
  • A* expands the state with the lowest f = g + h. With an admissible heuristic it returns an optimal path. It stores the best known cost per state and skips stale queue entries. Its memory use is also large, but far smaller than BFS's because the heuristic prunes most of the space.
  • IDA* runs repeated depth-first searches with a bound on f. If a pass fails, the new bound is the smallest f that exceeded the old one. It needs memory proportional only to the solution depth, at the price of re-expanding nodes.

Counting nodes expanded (rather than only measuring seconds) is the fair way to compare algorithms: it does not depend on how fast your computer is, and it matches the theory. The benchmark below runs six random solvable 8-puzzle boards through every solver, then three scrambled 15-puzzle boards through the two memory-friendly ones, and finally prints one optimal solution.

Python Benchmark BFS, A* and IDA* on 8- and 15-puzzles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading the results

The node counts do not depend on your computer, so they should match the table you see (times will not):

Solver (8-puzzle, 6 boards) Avg moves Avg nodes expanded Max nodes
BFS 21.0 76,786 156,041
A* misplaced tiles 21.0 13,251 37,531
A* Manhattan 21.0 1,396 4,098
IDA* Manhattan 21.0 1,483 5,804

Four lessons stand out.

  1. All four find solutions of identical length. Every solver here is optimal (the heuristics are admissible), so the average of 21.0 moves is the same. Only the effort differs.
  2. The heuristic is worth far more than the algorithm. Moving from BFS to A* with the weak misplaced-tiles heuristic cuts the work by a factor of six. Switching to Manhattan distance cuts it by a factor of 55 compared with BFS. A better heuristic beats a cleverer data structure every time.
  3. IDA matches A on node count.** It re-expands shallow nodes in each iteration, but because the number of nodes grows exponentially with depth, the last iteration dominates the total. In return it stores only the current path, so its memory use is tiny. That is what makes it the standard tool for puzzles too big for A*'s memory.
  4. The 15-puzzle is solved in a few thousand expansions on these boards (4,574 for A* on average), but the boards are only lightly scrambled (20 to 40 random moves). A fully random 15-puzzle board needs about 53 moves on average, and with plain Manhattan distance can take millions of expansions, which is too slow for this page.

Make it stronger

If you have time, try these extensions, roughly in order of difficulty:

  • Linear conflict. If two tiles are in their goal row but in reversed order, one of them must leave the row and come back, costing at least two extra moves. Adding 2 for each such conflict keeps the heuristic admissible and often halves the node count on the 15-puzzle.
  • Bidirectional search. Search from the start and from the goal at the same time; two searches to depth 10 are cheaper than one to depth 20.
  • Pattern databases. Precompute the exact cost of moving a subset of tiles (say, tiles 1 to 7) to their goals, ignoring the others, for every arrangement of that subset; use it as a lookup table. This is the idea behind the best known 15-puzzle solvers, and it is where admissible heuristics get serious.
  • Weighted A*. Multiply h by a factor such as 1.5 and trade a little solution quality for a lot of speed.
  • A user interface. Print the solution as an animation, or let the learner enter a board and report whether it is solvable first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why must a puzzle solver check solvability before searching?

    Only half of the arrangements can be reached from the goal by legal moves. For the other half every search algorithm exhausts all reachable states (or memory) without finding the goal.
  2. 2. Which statement about the heuristics used here is correct?

    Each misplaced tile contributes at least 1 to Manhattan distance, so Manhattan dominates misplaced tiles. Neither overestimates the real number of moves.
  3. 3. What is the main advantage of IDA* over A*?

    IDA* is a series of depth-first searches that keep only the current path in memory. It may re-expand nodes, but it avoids A*'s large open and closed sets.
  4. 4. Why does this project compare solvers by nodes expanded as well as by time?

    Expansion counts are reproducible on any computer and map directly to the theory. Timings also vary with the language, the hardware and the browser.
  5. 5. In the benchmark, why do all four solvers report the same average solution length?

    With unit step costs BFS is optimal, and A* and IDA* with admissible heuristics are optimal too, so all find the minimum number of moves.

Summary

  • Model the puzzle once (state tuple, successors, goal, heuristics) and keep the solvers generic.
  • Check solvability with the inversion-parity rule: exactly half of all arrangements are reachable, and the rule depends on whether the width is odd or even.
  • Manhattan distance dominates misplaced tiles; on the 8-puzzle it reduced expansions from about 77,000 (BFS) to about 1,400.
  • IDA* matches A*'s node counts with memory proportional to the solution depth.
  • Measure nodes expanded, not only seconds, and test on boards of known difficulty.
  • Stretch ideas: linear conflict, pattern databases, bidirectional and weighted search.

Next: Project: Sudoku Solver with CSP.