8 Puzzle Solver

Things to Play With

• Slide tiles yourself. Click any tile next to the blank to move it. The panel tracks your move count and the current Manhattan distance to the goal.
• Pick an algorithm. Switch between A*, Greedy Best-First, and Breadth-First search, then hit Solve to watch it finish the board.
• Swap heuristics. Toggle between Manhattan and Hamming distance. A smarter estimate expands far fewer nodes. (Breadth-First ignores the heuristic.)
• Scrub the solution. Step forward and back, drag the slider, or press play to auto-animate the tiles along the found path.
• Compare runs. Every Solve appends a row to the comparison table. Pit algorithms and heuristics against each other on the same board before you shuffle.

About

I first wrote an 8-puzzle solver years ago in my university Artificial Intelligence class. That version was a terminal program in Python. I built it to learn search algorithms and heuristic functions, then measure how they perform. Feel free to get the code on GitHub.

The demo above is a from-scratch TypeScript rebuild of that project. Solve a few puzzles. Compare how the algorithms behave. If you want the details, keep reading.

Search algorithms

This project uses three search algorithms:

• Breadth First Search
• Greedy Best First Search
• A* Search

Breadth First Search explores the search space one depth at a time. It visits every node at the current depth before it moves deeper. Here, each node is one puzzle state. This algorithm always finds the shortest path to the goal. It is also the slowest of the three.

def breadth_first_search(startPuzzle, solutionPuzzle = "12345678-"):
    queue = Q.Queue()
    queue.put([startPuzzle])
    visitedPuzzles = set([startPuzzle])
    while not queue.empty():
        path = queue.get()
        currentPuzzle = path[-1]
        if currentPuzzle == solutionPuzzle:
            return path
        for child in getPuzzleChildren(currentPuzzle):
            if child not in visitedPuzzles:
                visitedPuzzles.add(child)
                queue.put(path + [child])
    return None

Greedy Best First Search ranks nodes with a heuristic. The heuristic guesses which child is most likely to lead to the goal. This algorithm is faster than Breadth First Search. It does not always find the shortest path.

def best_first_search(heuristicFunction, startPuzzle, solutionPuzzle = "12345678-"):
    queue = Q.PriorityQueue()
    queue.put((heuristicFunction(startPuzzle), [startPuzzle]))
    visitedPuzzles = set([startPuzzle])
    while not queue.empty():
        _, path = queue.get()
        currentPuzzle = path[-1]
        if currentPuzzle == solutionPuzzle:
            return path
        for child in getPuzzleChildren(currentPuzzle):
            if child not in visitedPuzzles:
                visitedPuzzles.add(child)
                queue.put((heuristicFunction(child), path + [child]))
    return None

A* Search combines Breadth First Search and Greedy Best First Search. As it explores, it tracks the path cost to each node. That cost is the parent path cost plus the cost of the move into the child. With that cost and a heuristic, A* finds the shortest path and still focuses the search. It is often slower than Greedy Best First Search. It always finds the shortest path to the goal.

def a_star_search(heuristicFunction, startPuzzle, solutionPuzzle = "12345678-"):
    queue = Q.PriorityQueue()
    start_g = 0
    start_f = heuristicFunction(startPuzzle) + start_g
    visitedPuzzles = set(startPuzzle)
    queue.put((start_f, (start_g, [startPuzzle])))
    while not queue.empty():
        node = queue.get()
        _, current_node = node
        current_g, current_puzzle_path = current_node
        current_puzzle = current_puzzle_path[-1]
        if current_puzzle == solutionPuzzle:
            return current_puzzle_path
        for child in getPuzzleChildren(current_puzzle):
            if child not in visitedPuzzles:
                visitedPuzzles.add(child)
                child_g = current_g + 1
                child_f = heuristicFunction(child) + child_g
                queue.put((child_f, (child_g, current_puzzle_path + [child])))
    return None

Heuristic functions

This project uses two heuristic functions:

• Manhattan Distance
• Hamming Distance

Manhattan Distance estimates the cheapest path from the current state to the goal. It sums how far each tile sits from its goal position. For each tile, that distance is the horizontal gap plus the vertical gap.

def manhattanDistance(puzzle):
    distance = 0
    for i, val in enumerate(list(puzzle)):
        if val == "-":
            continue
        targetIndex = int(val) - 1
        targetCoordinates = (targetIndex // 3, targetIndex % 3)
        distance += abs(targetCoordinates[0] - (i // 3)) + abs(targetCoordinates[1] - (i % 3))
    return distance

Hamming Distance takes a simpler cut. It counts tiles that are not in their goal position. It ignores how far each wrong tile sits from home.

def hammingDistance(puzzle):
    target = "12345678-"
    return sum([1 for i, val in enumerate(list(puzzle)) if val != target[i]])

A note on admissibility.

Both heuristics are admissible. Admissible means the heuristic never overestimates the cheapest path to the goal. That matters. If a heuristic overestimates, the search may miss the shortest path.

Performance Testing

I used my old Python program here on GitHub for performance tests. I ran them on over 500 randomly generated puzzles. For every solver and heuristic pair, I ran each puzzle three times, averaged the results, then recorded them. The results are below.

Data

Analysis