Title: Exploring Klotski: An Investigation of the Minimum Number of Moves in a Special Case of Slide Puzzles
Authors: Axelcris G. Suladay, Mergel Ann G. Millendez, Trisha B. Vista Francisco Ramos National High School
Volume: 9
Issue: 2
Pages: 194-194
Publication Date: 2025/02/28
Abstract:
Klotski is a special type of sliding puzzle that first emerged in the early 20th century. It refers to a variety of sliding block or tile games with the goal of moving a specific block to a predetermined spot. By changing the game's rule that requires a player to move a certain tile or block from one corner of the puzzle to its opposite corner, providing that it contains spaces more than or equal to one, this inquiry sought to ascertain the minimum number of moves. It was also recognized that the Klotski puzzle's dimension was directly influenced by the number of spaces. The results of the investigation proposed the use of these formulae in determining the minimum number of moves (M) given the number of columns/rows of a square-shaped Klotski: a. M = 8s?11 if the number of spaces (S) is equal to 1, b. M = 8s?3S?8 if the number of spaces (S) is greater than or equal to 1 but less than or equal to 4, c. M = 8s?S?16 if the number of spaces (S) is greater than or equal to 4 but less than or equal to infinity and the number of rows/columns (s) is greater than or equal to the number of spaces (S). Alternatively, 3 formulae were proposed to determine the minimum number of moves (?M) of a rectangular-shaped Klotski: a. M = 6l + 2w ? 13 if the number of spaces is equal to 1, b. M = 4 1 + 4lw ? 14 if the product of the dimension is the quantity of n plus 1 multiplied by the quantity of n plus 2, and c. M = 6l?2w?S?16 if the product of the dimension is the quantity of n plus f multiplied by the quantity of n plus k, where f is greater than or equal to 1, k is greater than 2, k is greater than f , f is less than the number of spaces (S), and lastly if the number of spaces is greater than or equal to 2 but less than or equal to infinity. In the ca?se where only the product (P) and difference (d) of the dimensions are given, the formula MPd = 4 d2 + 4P + 2d ? 13 may be u?sed to determine the minimum number of moves if the number of spaces is equal to 1, while MPd = 4 1 + 4P ? 14 is used only if the ?pr oduct of the dimension is the quantity of n plus 1 multiplied by the quantity of n plus 2, and MPd = 4 d2 + 4P + 2d ? S ? 16 will be utilized if the product of the dimension is the quantity of n plus f multiplied by the quantity of n plus k, where f is greater than or equal to 1, k is greater than 2, k is greater than f , f is less than the number of spaces (S), and the number of spaces is greater than or equal to 2 but less than or equal to infinity. It is recommended that additional investigations must be done for other cases of the puzzle, such as with triangles and other shaped Klotski puzzles, with consideration of the movement of more than 1 block and to determine the other possible real-life application of the concepts and result in this study.