Klotski

screenshot of FORGET-ME-NOT level in Windows Entertainment Pack version

Klotski (from Polish klocki -- wooden blocks) is a sliding block puzzle. Sometimes it only refers to the block arrangement in the right-hand-side diagram, where the largest block (in red) must be moved to the bottom middle location (marked in blue). In a more global sense, Klotski refers to a whole group of similar sliding-block puzzles where the aim is to move a specific block to some predefined location. For more information, please refer to the Block arrangement variation section below.

Rules

Like other sliding-block puzzles, several different-sized block pieces are placed inside a box, which is generally in 4x5 size. Among the blocks, there is a special one (usually the largest) which must be moved to a special area designated by the game board. The player is not allowed to remove blocks; he may only slide blocks horizontally and vertically. Common goals are to solve the puzzle with a minimum number of moves or in a minimum amount of time.

History

• Lewis W. Hardy obtained copyright for a game named Pennant Puzzle in 1909, manufactured by OK Novelty Co., Chicago. The aim of this puzzle is completely identical to Klotski, just default blocks and arrangement are different. He also filed U.S. Patent 1,017,752 on 1907-12-14, which is about a sliding-block puzzle similar to Pennant Puzzle, but with a slightly different combination of blocks and a different goal—not only the largest block must be moved to a specific location, but all of the other blocks must achieve a specific configuration as well. The patent was granted on 1912-02-20.

• John Harold Fleming obtained a patent in 1934 in England (patent number 411515. He applied for it on 1932-12-07 and it was granted on 1934-06-07. The puzzle concerned has the same blocks and almost identical placement as forget-me-not, only that the unique horizontal 2x1 block is placed at the bottom instead of beneath the 2x2 block. The patent included a 79-step solution.

• It was known in France as L'âne rouge (red donkey) at that time.^{[citation needed]}

• It is said to trace back to a Thai game called "Khun Phaen Escapes to freedom".^{[citation needed]}

• It is said that the game was already known in Japan around the 10th year of the Shōwa period, i.e. around 1935.^{[citation needed]}

• One of the earliest books about standard Klotski was written by the Chinese professor 姜长英 on 1949，in his book 《科学消遣》. (translation: Science Pastime)^{[citation needed]}

It is still unknown which one is the original, or (in turn) if it has evolved from some other sliding-block puzzle, say, the 15 puzzle, which enjoyed immense popularity in western countries during late 19th century. There are many confusing and conflicting claims, and several countries claim to be the ultimate origin of this game.

Solving

The minimum number of moves for the original puzzle is 81, which is verified by computer to be the absolute minimum for the default starting layout, if you consider sliding a piece two positions in the same direction to be a single move.

The first published 81-step solution is by Martin Gardner, in Feb 1964 issue of Scientific American. In the article he discussed the following puzzles (with Edward Hordern classification code in parentheses): Pennant Puzzle (C19), L'Âne Rouge (C27d), Line Up the Quinties (C4), Ma's Puzzle (D1) and a form of Stotts' Baby Tiger Puzzle (F10).

For earliest published solutions (not optimal solution), currently known is from Chinese educator Xǔ Chún Fǎng (許蒓舫), in his book 《數學漫談》. (translation: Mathematics Tidbits; Hwa Yi Publication, March 1952) His solution involves 100 steps.

Variation

There are several variations of this game, some with names specific to the culture of certain countries, some with different arrangement of blocks.

It is still unknown whether these variations affected each other and how.

Block name variation

The following variations basically have the same layout and block arrangement, varying only in name (human, animal, or others), usually with some sort of story behind the names. It is completely unknown whether they share the same origin, though this is highly possible as they are identical to each other.

Hua Rong Dao

• Hua Rong Dao (alternatively named Hua Rong Path, Chinese name: 華容道) is the Chinese variation, featuring an old legendary during Battle of Red Cliffs in the 13th year of Jian An in the East Han Dynasty 208AD-- a well-known battle in Chinese history. The legendary: Cao Cao was defeated in this battle, and escaped to Hua Rong Dao, in which he encountered Guan Yu. Because Guan Yu remembered Cao Cao treated him well during old days despite he was a general of enemy of Cao Cao, Guan Yu spared Cao Cao's life. The largest block is named Cao Cao.

Daughter in the box

Daughter In The Box（箱入り娘） board

The daughter in the box (Japanese name: hakoiri musume) wood puzzle depicts an "innocent young girl, who knows nothing of the world" trapped in a building. The largest piece is named "daughter", and other blocks are given names of other family members (like father, mother and so on).

Yet another variation in Japan uses name of pieces from Shogi.

L'âne rouge

In France it is well known as L'âne rouge. It features a red donkey (largest piece) trying to escape a maze of fences and pens to get to its carrots.^{[citation needed]}

Khun Chang Khun Phaen

This is the variation for Thailand. Description taken from University of Cambridge ^[1]:

Khun Phaen is a famous character in Thai Legend. This game was originally known as `Khun Chang Khun Phaen' and refers to Khun Phaen being imprisoned. He breaks out of jail by escaping the cordon of nine sentries who are guarding him.

There is a slight difference between Khun Chang Khun Phaen and the standard layout—the middle 2 1x1 blocks are moved to bottom. Other than that, all other blocks are the same. The origin of this variation is unknown in Thailand.

Block arrangement variation

In this context, the "basic" arrangement is assumed to be the one on top of this page, which is used globally as the "basic" game of Klotski. It is coded C27d in Hordern classification of sliding puzzle games.

Pennant Puzzle

Pennant Puzzle / Dad's puzzle

Coded as C19 in Hordern classification, it is first copyrighted in 1909 by Lewis. W. Hardy in United States. Standard Trailer Co. has it copyrighted under the name Dad's Puzzler on 1926 (also in US). Its arrangement is different:

1. The default location of all blocks are different from Klotski. For example, the largest square block is in upper left corner.
2. It is in 4x5 area, with one 2x2, two 1x2, four 2x1, two 1x1 pieces.
3. The exit of block is not at the bottom middle, but bottom left.

Other than these, the game rule is completely the same as Klotski. The minimum number of moves to solve the puzzle is 59.

Ma's Puzzle

Ma's Puzzle is copyrighted by Standard Trailer Co. at 1927. It is the first sliding puzzle to use non-rectangular shape. Its goal is to join its 2 L-shaped pieces together, either anywhere or top right corner of the board.

Computerized version

The first known graphical version of Klotski was created for Windows by ZH Computing in 1991. It was later in the same year included in the third Microsoft Windows Entertainment Pack.

Many versions of Klotski exist now, either freely available or commercially available. For example, one is included in the GNOME desktop environment. Some even include the idea of having blocks with special effects.

Notes and references

1. ^ nrich.maths.org :: Mathematics Enrichment :: Khun Phaen Escapes to Freedom

See also

• N-puzzle
• Rush Hour (board game)
• Mechanical puzzles
• Combination puzzles

External links

• easy-to-follow gif animation. Animation of the 'Forget-me-not' (L'Âne Rouge) solution.
• Solving Dad's Puzzle
• Solving Klotski puzzle
• Klotski by ZH Computing