Sliding Block Puzzle

Understanding the mechanics of sliding block puzzles

The basic version of a Sliding Block Puzzle is deceptively simple. You have a rectangular grid, usually 6 by 5 cells, populated with wooden or plastic pieces of different sizes. A 2 by 2 block sits somewhere in the middle. The rest are 1 by 2 or 2 by 1 horizontal/vertical bars. There's a gap or a pair of adjacent gaps. Your job is to slide pieces around until the big square reaches the exit, typically at the bottom center. That's it. But the state space explodes fast. A standard 6 by 5 board with a few pieces can generate over a million reachable positions from a single starting configuration. The famous "Klondike" layout takes 81 moves to solve. Some constructed puzzles require several hundred moves. That's why people who claim they can just "see the solution" usually can't. They're guessing.

What makes a Sliding Block Puzzle solvable

Not every arrangement of pieces on a board is solvable. This is where parity comes in, but not in the way most introductions describe it. In the standard 6 by 5 Rush Hour-style puzzles with the exit open at the bottom, solvability depends on the permutation parity of the pieces relative to their target positions, combined with where the empty spaces end up after each legal move sequence. I once spent an afternoon trying to solve a commercial puzzle that was marketed as having a unique solution. It had two. I had to mark the pieces with a pencil and track my moves across three separate attempts before I confirmed both paths led to valid but different final positions. The manufacturer's diagram only showed one. This is a real problem with cheap implementations. If you're buying physical puzzles, check online databases like the one maintained by Bell Labs researchers before committing to ones that look suspiciously clean.

Solving approach: breadth-first search

For anyone trying to solve these programmatically or understand how to approach them manually, the standard algorithm is breadth-first search over the state space. Each state is defined by the position and orientation of every piece plus the location of empty cells. From each state, you generate all legal slide moves and explore level by level until you reach the goal state where the 2 by 2 block occupies the exit row. The critical optimization most beginners miss is that you don't need to track the empty cells as separate entities. You can encode the board as a bitmask or a tuple of piece positions and derive emptiness from what's not occupied. This cuts memory usage significantly. A well-implemented BFS solver for standard 6 by 5 puzzles runs in under 30 seconds on modern hardware and uses roughly 200MB of RAM at peak. Here's the basic structure in Python-like pseudocode:

from collections import deque

def solve_puzzle(board_state):
    queue = deque([(board_state, [])])
    visited = {board_state}
    
    while queue:
        state, path = queue.popleft()
        
        if is_goal(state):
            return path
        
        for move in get_legal_moves(state):
            new_state = apply_move(state, move)
            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, path + [move]))
    
    return None  unsolvable

The bottleneck is get_legal_moves. A naive implementation that scans every cell on every turn will be slow. A better approach precomputes which pieces can slide in which directions based on the current empty cell configuration. This reduces move generation from O(cells) to O(pieces) per state. The biggest mistake I see people make is treating all puzzles the same. A puzzle where the exit is blocked by a single 1 by 2 bar requiring a specific sequence of rotations is fundamentally harder than one with a wide open corridor. The difficulty rating on most puzzle sites assumes uniform piece distributions, which is wrong. Another issue is the "deadlock" detection problem. Some positions look valid but have no path forward because the remaining empty cells are split into disconnected regions. Detecting this requires a flood-fill check on the empty space graph, which most casual solvers skip. Adding this check early in your search tree can prune thousands of useless branches and cut solve time from minutes to seconds on hard configurations.

If you're building a solver for custom puzzles, implement a bidirectional BFS. Search from both the start state and the goal state simultaneously, meeting in the middle. This reduces the effective search depth by half and typically gives you a 10x to 50x speedup depending on the puzzle density.

Where to find implementations

There are several solid open-source implementations available. The sliding-block-puzzle package on PyPI provides a complete solver with GUI support and handles standard 6 by 5 boards out of the box. Installation is straightforward: For web-based interactive play, nifty.org's puzzle collection hosts a well-implemented browser version with hundreds of hand-curated puzzles ranging from easy to extremely difficult. The mobile app "Klotski" on both iOS and Android is functional but has a cluttered interface. I recommend the desktop versions if you care about clean UI and accurate move counting. If you want to create a custom variant, the hardest part isn't the rendering. It's the puzzle generation. Randomly placing pieces on a board rarely produces a solvable configuration. The reliable method is to start from a solved state and perform a large number of random legal moves to shuffle the board. This guarantees solvability by construction. The downside is that the resulting puzzles often have multiple solutions and can be trivially solved by following the reverse of the shuffle path if you're not careful about how many moves you make.

A more interesting approach generates puzzles by removing pieces from a fully filled board and solving from there, but this requires a constraint solver to verify uniqueness of solution. Without uniqueness checking, you're just making a puzzle that's easy but possibly ambiguous. The move counting is another area where people make mistakes. In the standard ruleset, a "move" means sliding any piece any distance in one direction until it hits another piece or the board edge. One continuous push counts as one move even if the piece travels three cells. Some variants count each cell as a separate move, which inflates the reported solution length dramatically and makes comparison between puzzle collections meaningless. Always check which convention a source uses before trusting their difficulty rankings.