The story of Hakoiri Musume

Hakoiri Musume — “the daughter in the box” — is a sliding-block puzzle on a 4×5 board. You slide the pieces around to bring the biggest one, the Daughter, out through the exit at the bottom. You can't lift anything; the only room you have is two empty squares.

What counts as one move?

The classic layout can be solved in 81 moves — if sliding the same piece several times in a row, even around a corner, counts as one move. Count every single-square slide instead and the minimum is 116.

We checked both numbers with this site's own program. It looks at every position one move away, then two moves away, and so on (a breadth-first search). Treating same-shaped pieces as identical, 25,955 different arrangements can be reached from the classic start, and the one farthest from the goal needs 93 moves. That is our “Hardest” layout.

One mechanism, many stories

Puzzles of this family have travelled under different names and stories:

Where	Name and story
United States	Lewis W. Hardy filed a patent in 1907, granted in 1912. In 1909 it was registered for copyright as the Pennant Puzzle, themed on baseball pennants, and it later spread under names such as Dad's Puzzle.
Britain	A patent published in 1934 shows almost exactly the Hakoiri Musume layout.
France	A puzzle of the same family is known as L'Âne Rouge, “the red donkey”.
China	Huarong Dao. The big piece is the warlord Cao Cao, escaping through Huarong Pass after the Battle of Red Cliffs, as told in Romance of the Three Kingdoms. The story is old, but the earliest reliable record of the puzzle is from 1938, and the name first appears in a book in 1949.
Japan	Hakoiri Musume. A “daughter kept in a box” is a sheltered girl, guarded by the family pieces around her. It is said to have been played by the 1930s; who named it is unknown.

The name Klotski, common in English, is said to come from a 1991 computer game.

Who invented it?

Nobody knows. The American patent is an early record, but some sources say its layout was different, so it can't simply be called the original. Claims that Huarong Dao goes back to the Three Kingdoms era have no record to back them up.

1964: a magazine column takes it worldwide

Martin Gardner devoted his February 1964 “Mathematical Games” column in Scientific American to sliding-block puzzles. The 81-move solution was published around that time and became widely known.

How to think about it

• Line up the two gaps. Big pieces can only move when both empty squares sit side by side. Plan for that first.
• Small pieces move the gaps. You shuffle the small pieces mainly to carry the empty squares where you need them.
• The wide piece is the gatekeeper. The Daughter needs a two-square-wide path down. Work backwards from clearing it.

Stuck? The Hint button on the puzzle page shows a next move, and you can watch a shortest solution.