Klotski

Klotski is a sliding block puzzle where the player must move a large 2x2 block to a designated exit position by sliding it and other blocks within a confined tray. The tray is typically 4 columns wide and 5 rows tall, containing blocks of various sizes — one 2x2 block, several 2x1 blocks (horizontal or vertical), and 1x1 blocks — with exactly two empty cells that allow movement. The challenge is to navigate the large block through the crowded board to reach the exit, usually at the bottom center.

Rules

1. The board is a 4x5 tray containing blocks of different sizes and two empty cells.
2. Blocks can be slid horizontally or vertically into adjacent empty space, but cannot be lifted, rotated, or placed on top of other blocks.
3. The goal is to move the large 2x2 block to a target position (typically the bottom center of the tray, which has an opening).
4. All other blocks are obstacles that must be rearranged to create a path for the large block.

Block Types (Classic Configuration)

• 1 large block (2x2) — the one you need to free
• 1 tall block (1x2 vertical)
• 4 medium blocks (2x1 horizontal or 1x2 vertical, depending on configuration)
• 4 small blocks (1x1)
• 2 empty cells

Strategies

• Visualize the Exit Path: The 2x2 block needs a clear 2-wide channel from its current position to the exit. Your job is to create that channel.
• Move Small Blocks First: Small 1x1 blocks are the most flexible. Use them to create temporary space for moving larger blocks.
• Avoid Circular Moves: It is easy to accidentally undo progress. Be intentional about each move and try to track the overall direction of the large block.
• Work from the Exit Up: Clear space near the exit first, then work upward to create a path for the large block to descend.
• Use Parking Spaces: Move obstacle blocks to areas where they will not need to be moved again. The corners are often good parking spots.
• Minimum Moves Challenge: The classic configuration ("Pennant Puzzle" or "Daughter in the Box") requires a minimum of 81 moves. Trying to approach this minimum adds an extra layer of challenge.

Klotski's origins are somewhat unclear, with multiple claims to its invention. The puzzle appears to have emerged in the early 20th century in multiple countries independently. Variations of sliding block puzzles were patented in the United States and Europe between 1900 and 1930. The name "Klotski" comes from the Polish word "klocki," meaning "blocks."

The most famous configuration of the puzzle is known in China as "Hua Rong Dao" (华容道), named after a legendary pass from the Chinese classic novel "Romance of the Three Kingdoms." In the story, the warlord Cao Cao must escape through the Huarong Pass after his defeat at the Battle of Red Cliffs (208 AD). In the puzzle, the large block represents Cao Cao, and the other blocks represent generals blocking his path. This narrative framing made the puzzle enormously popular in China, where it has been a cultural staple for over a century.

In the West, the puzzle appeared under various names: "Pennant Puzzle" (marketed by the Embossing Company in the 1930s), "Dad's Puzzle," and simply "Sliding Block Puzzle." Martin Gardner featured sliding block puzzles in his Scientific American column, introducing them to a wide mathematical audience. Computer scientists have used Klotski and its variants as benchmark problems for search algorithms and AI planning.

The mathematical analysis of Klotski is substantial. The puzzle has been shown to be PSPACE-complete in its general form, meaning it is among the hardest problems solvable with polynomial space. The classic configuration has been exhaustively analyzed by computer, confirming the optimal solution of 81 moves (or 116 if counting each single-cell slide as a move). There are many variant configurations of different difficulties, and designing new interesting configurations remains an active area of puzzle design.