Klotski: Difference between revisions
Line 94: | Line 94: | ||
* [http://www.stavanger-guide.com/klotski.htm Nice easy to follow gif animation]. A visual hint of the 'Forget-me-not' (L'Âne Rouge) solution. |
* [http://www.stavanger-guide.com/klotski.htm Nice easy to follow gif animation]. A visual hint of the 'Forget-me-not' (L'Âne Rouge) solution. |
||
* [http://www.jawed.com/programs/puzzle.html Solving Dad's Puzzle] |
* [http://www.jawed.com/programs/puzzle.html Solving Dad's Puzzle] |
||
* [http://www.youtube.com/watch?v=vK1mgbvS_8s Solving Klotski puzzle] |
|||
Revision as of 16:20, 5 April 2009
This article needs additional citations for verification. (March 2008) |
![](http://upload.wikimedia.org/wikipedia/en/2/29/Bricks-Forget-Me-Not-small.png)
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 move 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, and it is manufactured by OK Novelty Co., Chicago. The aim of this puzzle is completely identical to Klotski, just that default blocks and arrangement are different. He also filed U.S. patent 1,017,752 on 1907-12-14, which is about sliding block puzzle similar to Pennant Puzzle, but with a slightly different combination of blocks, and a different goal -- not only moving the largest block to specific location, but all of the other blocks must achieve specific configuration as well. The patent is granted on 1912-02-20.
- John Harold Fleming obtained patent in 1934 in England (patent number 411515. Patent is applied on 1932-12-07 and granted on 1934-06-07. The puzzle concerned has 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 2x2 block. The patent included a 79-step solution.
- It is known in France as L'âne rouge (red donkey) at that time.
- It is said to trace back to Thai game called "Khun Phaen Escapes to freedom". [citation needed]
- It is said that the game is already known in Japan around 10th year of Shōwa period, i.e. around 1935; but during early days the puzzle name was slightly different from original Japanese version.
- One of the earliest books about standard Klotski is written by Chinese professor 姜长英 on 1949,in his book 《科学消遣》. (translation: Science Pastime) (cited in Baidu reference)
It is still unknown which one is the origin, or (in turn) is 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 are claiming to be the ultimate origin of this game.
Solving
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7f/SquareMaster.jpg/220px-SquareMaster.jpg)
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. However, the 'Square Master' game for iPhone and iPod touch shows that the board can be placed in a layout that would take a minimum of 126 moves. In this rendition of the game, sliding a piece two positions in the same direction counts as two moves.
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 parenthesis): 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
![](http://upload.wikimedia.org/wikipedia/commons/8/84/Hakoiri3.jpg)
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.
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
![](http://upload.wikimedia.org/wikipedia/commons/5/5b/Dad%27s_Puzzle.png)
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:
- The default location of all blocks are different from Klotski. For example, the largest square block is in upper left corner.
- It is in 4x5 area, with one 2x2, two 1x2, four 2x1, two 1x1 pieces.
- 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 is in 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
See also
External links
- Nice easy to follow gif animation. A visual hint of the 'Forget-me-not' (L'Âne Rouge) solution.
- Solving Dad's Puzzle
- Solving Klotski puzzle