Klotski game solutions code#

Klotski game solutions code#

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Run them with python klotski/board_test.py. Therefore the Klotski solver has average complexity O(V+E) and worst case complexity O((V+E) * V). Membership in the set of visited configurations is checked for each transition and the number of elements in the set of visited configurations is bounded by the number of board configurations V. Breadth first search has complexity O(V+E) where V is the number of board configurations and E is the number of transitions between them. The add and in operations on a set have average complexity O(1) and worst case O(N). The visited configurations are stored in a set. So the graph we constructed in the 'Solution Design' section is disconnected. This means that there are 65,880 - 25,955 = 39,925 configurations that are unreachable from the initial configuration. Interestingly, a backtracking search reveals the total number of board configurations as 65,880. That means there are only 25,955 configurations reachable from the initial configuration.

The program examines 25,955 different board configurations. Also the starting configurations differ between the Klotski variant this program solves (Pioneer 1) and the variant described in the Wikipedia article. The Wikipedia article reports a solution of 81 moves, but they count moving a piece by two squares in the same direction as a single move whereas this program counts it as two. The shortest solution this program finds is 85 moves. Finally, before being enqueued each configuration is examined to determine whether it is a solved configuration. The program keeps track of all previously enqueued configurations to ensure that each configuration is examined exactly once. It then pops the next configuration from the front of the queue, finds the next reachable configurations, enqueues them, and repeats. It then determines the board configurations reachable in one move from the first configuration and adds them to a queue for subsequent processing. Instead it begins by constructing a representation of the initial board configuration. It does not explicitly construct the graph. This program uses a breadth first search to traverse the graph. Then a path from the initial board configuration to a solved configuration represents a solution to the puzzle. An edge (u, v) is introduced for each pair of board configurations where the board may be moved from the configuration represented by u to the configuration represented by v with a single move. Imagine each board configuration is assigned to a node in the graph. I model the game with an undirected graph. Solution DesignДЄssuming my estimate of 3 million board configurations is accurate then it is feasible to examine them all. On the other hand there are four identical small squares and four identical tall rectangles, so we can remove two factors of 4!.ДЄt this point I was sufficiently convinced. Some unique board configurations are uncounted because sliding a piece left or right can produce a new board configuration while retaining the same ordering. Since there are 10 pieces, so I estimated the number of board configurations as 10! ~ 3.6 million. The number of possible configurations of pieces on the board provides an upper bound on the number of states that the program must examine. AnalysisД«efore writing a program to solve the puzzle I convinced myself that it was feasible. Twenty years later I had only solved it once. When I was about 10 years old my grandmother gave me the Klotski puzzle game (also called the Square Root puzzle and Pioneer 1) as a gift. 65880 board configurations total (39925 unreachable)