View source for Klotski

{{short description|Sliding block puzzle}}
{{more citations needed|date=January 2015}}
[[File:Quo Vadis-HABA.jpg|thumb|In a ''Klotski'' puzzle, the largest block must be moved to the bottom middle location so that it can be slid over the border, without any of the other blocks being removed in this way.]]
'''Klotski''' (from {{langx|pl|klocki|lit=wooden blocks}}) is a [[sliding block puzzle]] thought to have originated in the early 20th century. The name may refer to a specific layout of ten blocks, or in a more global sense to refer to a whole group of similar sliding-block puzzles where the aim is to move a specific block to some predefined location.
==Rules==
Like other sliding-block puzzles, several different-sized block pieces are placed inside a box, which is normally 4×5 in 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, and 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.
==Naming==
[[Image:Bricks-Forget-Me-Not-small.png|right|204px|thumb|A screenshot of the "forget me not" level in the Windows Entertainment Pack version of the game]]The earliest known reference of the name ''Klotski'' originates from the computer version for [[Windows 3.x]] by ZH Computer in 1991, which was also included in Microsoft [[Windows Entertainment Pack]]. The sliding puzzle had already been trademarked and sold under different names for decades, including ''Psychoteaze''<ref>{{cite book|url=https://books.google.com/books?id=mSwhAQAAIAAJ&q=psychoteaze&pg=PA899 |title=Catalog of Copyright Entries. Third Series: 1969: January-June - Library of Congress. Copyright Office - Google 圖書 |year=1972 |access-date=2013-04-18}}</ref> ''Square Root'',<ref name="3 0 + Y e a r s A g o">{{cite web |url=http://home.comcast.net/~l-whiting/attbi/30YearsAgo.html |archive-url=https://archive.today/20121228071229/http://home.comcast.net/~l-whiting/attbi/30YearsAgo.html |url-status=dead |archive-date=2012-12-28 |title=30+ Years Ago |publisher=Home.comcast.net |date=1928-03-27 |access-date=2013-04-18 }}</ref> ''Intreeg'',<ref>{{cite web |url=http://home.comcast.net/~stegmann/sliding.htm |archive-url=https://archive.today/20121220033743/http://home.comcast.net/~stegmann/sliding.htm |url-status=dead |archive-date=2012-12-20 |title=Rob's Puzzle Page - Sliding Block Puzzles |publisher=Home.comcast.net |date=1915-03-16 |access-date=2013-04-18 }}</ref> and Ego Buster. There was no known widely used name for the category of sliding puzzles described before ''Klotski'' appeared.
==History==
It is still unknown which version of the puzzle is the original. There are many confusing and conflicting claims, and several countries claim to be the ultimate origin of this game. One game—lacking the 5 × 4 design of Pennant, Klotski, and Chinese models but a likely inspiration—is the 19th century [[15-puzzle]], where fifteen wooden squares had to be rearranged. It is suggested that unless a 19th-century Asian evidence is found, the most reasonably likely path of transmission is from the late 19th century square designs to the early 20th century rectangular, such as Pennant, thence to Klotski and Huarong Road.{{Citation needed|date=July 2022}}
=== United States ===
The 15-puzzle enjoyed immense popularity in western countries during the late 19th century. Around this time, patents appeared for puzzles using differently shaped blocks. Henry Walton filed {{US patent|516035}} in 1893 for a sliding puzzle of identically shaped rectangles. Frank E. Moss filed {{US patent|668386}} in 1900 for a sliding puzzle of six squares and four rectangles, which is one of the first known occurrences of sliding puzzle with non-equal blocks.  However, the early cognate of Klotski closest in design dates to 1909 in Chicago.{{Citation needed|date=July 2022}}
[[File:Dad's Puzzle.png|thumb|upright|The layout of the ''Pennant Puzzle'']]
Lewis W. Hardy obtained copyright for a game named ''Pennant Puzzle'' in 1909, manufactured by OK Novelty Co., Chicago.<ref>Enlisted in Section 5.A.1 of {{cite book| last=Singmaster |first=David |date=2004 |title=Sources in Recreational Mathematics - An Annotated Bibliography|edition=8th Preliminary| publisher=South Bank University }} ([http://www.puzzlemuseum.com/singma/singma-index.htm Available online] at the Puzzle Museum)</ref> The aim of this puzzle is identical to Klotski, and only its default blocks and arrangement are different. Hardy also filed {{US patent|1017752}} in 1907, 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 must the largest block be moved to a specific location, but all of the other blocks must achieve a specific configuration as well. The patent was granted in 1912.
=== England ===
John Harold Fleming obtained patent for a puzzle in 1934 in [[England]], with almost identical configuration as described in this page.<ref>{{cite patent|country=GB|number=411515|title=An improved puzzle, and means therefor|status=patent|pridate=1932-12-07|gdate=1934-06-07|assign1=John Harold Fleming}}</ref> The puzzle concerned has the same blocks and almost identical placement as forget-me-not, only that the unique horizontal 2×1 block is placed at the bottom instead of beneath the 2×2 block. The patent included a 79-step solution.
=== China ===
[[File:NTPC-SHJH HuaRongDao 2013-06.jpg|thumb|{{Transliteration|zh|Huarong Dao}}]]
The Klotski puzzle—with its two-by-two and one-by-two cells and with the same 4 × 5 dimensions—also closely resembles the Chinese game known as {{Transliteration|zh|Huarong Dao}} ({{Lang-zh|c=华容道|t=華容道}}), also known as  {{Transliteration|zh|Huarong}} ''Pass'' or {{Transliteration|zh|Huarong}} ''Road''. Popular versions of {{Transliteration|zh|Huarong Dao}} used cells with names or images of [[Han dynasty]] heroes and villains, based on a famous battle from the [[Yuan dynasty]] novel [[Romance of the Three Kingdoms]].<ref name="zh-src">{{cite web |last1=Zhang |first1=Wei |last2=Rasmussen |first2=Peter |title=Huarong Pass Sliding Block Puzzle |url=https://chinesepuzzles.org/huarong-pass-sliding-block-puzzle/ |website=Chinese Puzzles |access-date=12 July 2021}}</ref> The Chinese design, commonly using Chinese names for the heroes, villains, and soldiers, has clear inspiration from the Chinese version of chess, which problematizes the origins of the genre of sliding puzzles.
The first account of occurrence of Klotski in [[China]] is in [[Shaanxi Province]], where Lin Dekuan from the [[Northwestern Polytechnical University]] noted that children in a village, a countryside in [[Chenggu County|Chenggu county]], were playing a version of Klotski made with pieces of paper in 1938.<ref>{{cite book| isbn=9787030139856 | author=Wú Hè Líng | title=七巧板、九连环和华容道 | year=2004}} (translation: Tangram, Baguenaudier and Klotski)</ref>
In 1943, the {{Transliteration|zh|Huarong Dao}} was publicized by Liang Qing, a teacher in the New Fourth Route Army who learnt it from people living in northern [[Jiangsu|Jiangsu province]], among soldiers to enhance their cultural life.
One of the earliest books about standard Klotski was written by the Chinese professor Jiang Changying ({{Lang-zh|c=姜长英|labels=no}}) from the Northwestern Polytechnical University in 1949 in his book《{{Lang-zh|c=科学消遣|labels=no}} – ''{{Translation|Science Enterntainment}}''》; Jiang Changying believed that the {{Transliteration|zh|Huarong Dao}} was invented in the late 1930s and became popular during the late 1930s and early 1940s.<ref name="zh-src"/> This book has been republished by Jiang Changying in 1997 as《{{Lang-zh|c=科学思维锻炼与消遣|labels=no}} – ''{{Translation|Scientific mindset training and pastime}}''》({{ISBN|7-5612-0971-1}}).<ref>{{Cite book |last=Jiang |first=Changying |url=https://www.worldcat.org/oclc/769132474 |title=Ke xue si wei duan lian yu xiao qian |last2=姜长英 |date=1997 |publisher=Xi bei gong ye da xue chu ban she |isbn=7-5612-0971-1 |edition=Di 1 ban |location=Xi an |oclc=769132474}}</ref> Jiang Changying also believed that the {{Transliteration|zh|Huarong Dao}} was mostly likely introduced in Shanghai from the early 1940s from Northern Jiangsu province.
In 1956, the {{Transliteration|zh|Huarong Dao}} appeared in math magazine where it was called "''Guan Yu Releases Cao Cao''"; some years later, it gained the revolutionary name of "Chase Away the Paper Tiger" when it was published in the ''Liaoning Pictorial'' of 1959.
The plastic versions of the {{Transliteration|zh|Huarong Dao}} manufactured in the 1960s by the Shanghai No. 14 Toy Factory and Shanghai Changchun Plastic Factory made plastic version were named "Parking the Boats".
In the 1980s, an association was created by {{Transliteration|zh|Huarong Dao}} enthusiasts; {{Transliteration|zh|Huarong Dao}} enthusiasts also organized competitions in Beijing, Shanghai, and Northeast China.
==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 single piece to any reachable position to be a single move.
The first published 81-step solution is by [[Martin Gardner]], in the February 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''; [[:zh:開明書店|Kāi Mínɡ Shū Diàn]], March 1952) His solution involves 100 steps.
The current Guinness World Record for the [https://www.guinnessworldrecords.com/world-records/428817-fastest-time-to-solve-a-klotski-puzzle ''Fastest time to Solve a 4x5 Klotski puzzle''] is 3.99 seconds, achieved by Lim Kai Yi, a speedsolver from Malaysia on {{fdate|2024-06-13|mdy}}.
==Variations==
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. 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.
=== {{Transliteration|zh|Huarong Dao}} ===
[[Image:HuaRongDao.jpg|thumb|The Chinese wooden game ''{{Transliteration|zh|Huarong Dao}}'', thought to date from the 1930s, follows the same pattern as ''Klotski''.|257x257px]]
{{Transliteration|zh|Huarong Dao}} ({{Lang-zh|c=华容道|t=華容道}}, alternatively named {{Transliteration|zh|Huarong}} ''Pass'' or ''{{Transliteration|zh|Huarong}} Trail'') is the Chinese variation,  which shows unique Chinese characteristics, by basing itself on one of [[Classic Chinese Novels|Four Great Classical Novels]] novel, ''[[Romance of the Three Kingdoms]],'' about the warlord [[Cao Cao]] retreating through the {{Transliteration|zh|Huarong}} Trail (present-day [[Jianli County]], [[Jingzhou]], [[Hubei]]) after his defeat at the [[Battle of Red Cliffs]] in the winter of 208/209 CE during the late [[Han dynasty|Eastern Han dynasty]]. He encountered an enemy general, [[Guan Yu]], who was guarding the path and waiting for him. Guan Yu spared Cao Cao and allowed the latter to pass through {{Transliteration|zh|Huarong}} Trail on account of the generous treatment he received from Cao in the past. The largest block in the game is named "Cao Cao".
{{Clear}}
=== Daughter in the box ===
{{Multiple image
| image1            = Hakoiri3.jpg
| image2            = Hakoiri Shogi.jpg
| total_width       = 300
| caption1          = A Daughter in the Box （箱入り娘） board
| caption2          = Japanese variants with shogi pieces
| header            = Japanese version
| align             = left
}}
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).
Another Japanese variation uses the names of [[shogi]] pieces.
{{Clear}}
=== L'âne rouge ===
In France, it is well known as ''L'âne rouge''. It features a red donkey (the largest piece) trying to escape a maze of fences and pens to get to its carrots.<ref name="3 0 + Y e a r s A g o"/> However, there is no known and documented record of its first existence in France.
=== Khun Chang Khun Phaen ===
This is a variation from Thailand. [[Khun Phaen]] is a famous character in Thai legend, and the game is named after the epic poem ''[[Khun Chang Khun Phaen]]'', in which the character is imprisoned. The game depicts Khun Phaen breaking out of the prison by overcoming its nine sentries.<ref>{{cite web|url=http://nrich.maths.org/public/viewer.php?obj_id=1261&part=index&refpage=monthindex.php |title=Mathematics Enrichment :: Khun Phaen Escapes to Freedom |publisher=nrich.maths.org |date= |access-date=2013-04-18}}</ref>
There is a slight difference between ''Khun Chang Khun Phaen'' and the standard layout—the two middle 1×1 blocks are moved to bottom. Other than that, all other blocks are the same. The origin of this variation is unknown.
===Other block arrangements===
In this context, the "basic" arrangement is assumed to be a 4×5 area laid out as follows:-
* In the left-hand column, two 1×2 blocks with a 1×1 block beneath.
* In the right-hand column, two 1×2 blocks with a 1×1 block beneath.
* In the middle two columns, a 2×2 block at the top, with a horizontal 2×1 block beneath it, two 1×1 blocks beneath that, leaving a 2×1 empty space at the bottom.
This is used globally as the "basic" game of Klotski. It is coded C27d in [[Edward Hordern|Hordern]] classification of sliding puzzle games.<ref name=leh>{{cite book |last1=Hordern |first1=Edward |title=Sliding Piece Puzzles |date=1986 |publisher=OUP |isbn=0-19-853204-0}}</ref>{{rp|81}}
====Pennant Puzzle====
Coded as C19 in Hordern classification,{{r|leh|p=78}} 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'' in 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 4×5 area, with one 2×2, two 1×2, four 2×1, two 1×1 pieces.
# The exit of block is not at the bottom middle, but bottom left.
Other than these, the game rules are 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 was 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===
An early graphical computer version was created by Jim Bates in 1988.<ref>{{cite web |url=https://archive.org/details/msdos_festival_PRISONER |title=MS-DOS Shareware: PRISONER }}</ref> In 1991, Klotski was included in the third Microsoft [[Windows Entertainment Pack]]. Many versions of Klotski followed, either freely or commercially available. For example, one is included in the [[GNOME]] desktop environment. Some include blocks which have special effects.
=== In video games ===
The puzzle is also found in the 1995 [[Super Nintendo Entertainment System]] game ''[[Lufia II: Rise of the Sinistrals]]''. In a cave on Dragon Mountain, the player is told "The world's most difficult trick is beyond this point." A few floors down, the player is faced with the sliding block puzzle. The central block contains four chests with powerful items: Mega shield, Holy Robe, Legend helm, and Lizard blow.
==See also==
* [[N-puzzle]]
* [[Rush Hour (puzzle)]]
* [[Mechanical puzzles]]
* [[Combination puzzles]]
* [[Sliding puzzle]]
==Notes and references==
{{Reflist}}
==External links==
* [https://www.youtube.com/watch?v=wE5KFf5QotI easy-to-follow video]. 'Forget-me-not' (L'Âne Rouge) solution.
* [http://www.jawed.com/programs/puzzle.html Solving Dad's Puzzle]
[[Category:Mechanical puzzles]]
[[Category:Combination puzzles]]
[[Category:Puzzle video games]]
[[Category:Microsoft Entertainment Pack]]
[[Category:Wooden toys]]
[[ru:Klotski]]