-------------- Klotski Solver -------------- *--------------------------------------------------------------* A command-line solver for the Klotski game written in Python 3.4 *--------------------------------------------------------------* Copyright 2014, Mingjing Zhang Simon Fraser University +------------+ How it works: +------------+ Run Main.py. It reads the board specified in 'DefaultLayout.txt', then output the steps in an easy-to-read formt +--------------------------------+ How to write your own layout file: +--------------------------------+ The layout file contains the coordinate of each block. It is organized as follows: -- BEGINNING OF FILE -- TypeLetter Coordinate Coordinate ... TypeLetter Coordinate Coordinate ... ... -- END OF FILE -- 'TypeLetter' is a single capital letter that specifies which type of piece the next few coordinates define, until another TypeLetter is encountered. It can be either B(ig), H(orizontal), V(ertical) or S(mall). 'Coordinate' is a two number group in the order of 'X Y' (0 based). It represents the coordinate of the LEFT-TOP block of a piece. For example, the following file: B 1 0 H 1 2 2 3 defines a 2x2 piece whose LEFT-TOP block is at (1,0), and two 1x2 pieces whose LEFT-TOP blocks are at(1,2), and (2, 3) respectively. So the resulting board would look (E = empty block): E 0 0 E E 0 0 E E 1 1 E E E 1 1 E E E E +--+ FAQ: +--+ Why the 'HR' prefix for all class files? HR is the acronym of the Chinese name of Klotski -- Hua-Rong Dao (The Path of Hua-Rong). In the Chinese version, the game reenacts a classical story where the warlord, Cao Cao, escaped to the path of Hua-Rong after defeated in the Battle of Red Cliff. There he was ambushed by the enemy general Guan Yu. Each piece is assigned with a name of a historical figure, with the 2x2 piece being Cao Cao, and the horizontal one Guan Yu. +--------------+ Default Output: +--------------+ Solution found in 5.627 secs. 11975 nodes checked Solution Report: ======================================== Initial Layout: ---------------------------------------- 1 0 0 2 1 0 0 2 3 5 5 4 3 6 7 4 8 9 Solution: ---------------------------------------- Step 1 to 5: #6 DOWN #9 LEFT #4 DOWN #5 RIGHT #3 RIGHT 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 3 5 5 4 --> 3 5 5 4 --> 3 5 5 --> 3 5 5 --> 3 5 5 --> 3 7 4 3 7 4 3 7 4 3 7 4 3 7 4 8 6 9 8 6 9 8 6 9 4 8 6 9 4 8 6 9 4 Step 6 to 10: #8 UP #6 LEFT #3 DOWN #5 LEFT LEFT #7 UP RIGHT 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 3 5 5 --> 3 5 5 --> 5 5 --> 5 5 --> 5 5 7 --> 8 3 7 4 8 3 7 4 8 3 7 4 8 3 7 4 8 3 4 6 9 4 6 9 4 6 3 9 4 6 3 9 4 6 3 9 4 Step 11 to 15: #9 UP UP #3 RIGHT #8 RIGHT DOWN #5 DOWN #9 LEFT LEFT 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 5 5 9 7 --> 5 5 9 7 --> 5 5 9 7 --> 9 7 --> 9 7 --> 8 3 4 8 3 4 3 4 5 5 3 4 5 5 3 4 6 3 4 6 3 4 6 8 3 4 6 8 3 4 6 8 3 4 Step 16 to 20: #7 LEFT LEFT #3 UP #4 UP #8 RIGHT RIGHT #6 RIGHT RIGHT 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 9 7 --> 9 7 3 --> 9 7 3 4 --> 9 7 3 4 --> 9 7 3 4 --> 5 5 3 4 5 5 3 4 5 5 3 4 5 5 3 4 5 5 3 4 6 8 3 4 6 8 4 6 8 6 8 6 8 Step 21 to 25: #5 DOWN #7 DOWN LEFT #3 LEFT #4 LEFT #2 DOWN DOWN 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 2 1 0 0 9 7 3 4 --> 9 3 4 --> 9 3 4 --> 9 3 4 --> 9 3 4 2 --> 3 4 7 3 4 7 3 4 7 3 4 7 3 4 2 5 5 6 8 5 5 6 8 5 5 6 8 5 5 6 8 5 5 6 8 Step 26 to 30: #0 RIGHT #1 RIGHT #9 UP UP #7 UP UP #3 LEFT 1 0 0 1 0 0 9 1 0 0 9 1 0 0 9 1 0 0 1 0 0 1 0 0 1 0 0 7 1 0 0 7 1 0 0 9 3 4 2 --> 9 3 4 2 --> 3 4 2 --> 3 4 2 --> 3 4 2 --> 7 3 4 2 7 3 4 2 7 3 4 2 3 4 2 3 4 2 5 5 6 8 5 5 6 8 5 5 6 8 5 5 6 8 5 5 6 8 Step 31 to 35: #1 DOWN DOWN #0 LEFT #2 UP UP #4 RIGHT #6 UP UP 9 0 0 9 0 0 9 0 0 2 9 0 0 2 9 0 0 2 7 0 0 7 0 0 7 0 0 2 7 0 0 2 7 0 0 2 3 1 4 2 --> 3 1 4 2 --> 3 1 4 --> 3 1 4 --> 3 1 6 4 --> 3 1 4 2 3 1 4 2 3 1 4 3 1 4 3 1 4 5 5 6 8 5 5 6 8 5 5 6 8 5 5 6 8 5 5 8 Step 36 to 40: #8 LEFT UP #5 RIGHT RIGHT #1 DOWN #3 DOWN #6 LEFT LEFT 9 0 0 2 9 0 0 2 9 0 0 2 9 0 0 2 9 0 0 2 7 0 0 2 7 0 0 2 7 0 0 2 7 0 0 2 7 0 0 2 3 1 6 4 --> 3 1 6 4 --> 3 6 4 --> 6 4 --> 6 4 --> 3 1 8 4 3 1 8 4 3 1 8 4 3 1 8 4 3 1 8 4 5 5 5 5 1 5 5 3 1 5 5 3 1 5 5 Step 41 to 45: #0 DOWN #9 RIGHT RIGHT #7 UP RIGHT #6 UP UP #3 UP UP 9 2 9 2 7 9 2 6 7 9 2 6 7 9 2 7 0 0 2 7 0 0 2 0 0 2 0 0 2 3 0 0 2 6 0 0 4 --> 6 0 0 4 --> 6 0 0 4 --> 0 0 4 --> 3 0 0 4 --> 3 1 8 4 3 1 8 4 3 1 8 4 3 1 8 4 1 8 4 3 1 5 5 3 1 5 5 3 1 5 5 3 1 5 5 1 5 5 Step 46 to 50: #1 LEFT #8 LEFT DOWN #0 DOWN #9 DOWN LEFT #2 LEFT 6 7 9 2 6 7 9 2 6 7 9 2 6 7 2 6 7 2 3 0 0 2 3 0 0 2 3 2 3 9 2 3 9 2 3 0 0 4 --> 3 0 0 4 --> 3 0 0 4 --> 3 0 0 4 --> 3 0 0 4 --> 1 8 4 1 4 1 0 0 4 1 0 0 4 1 0 0 4 1 5 5 1 8 5 5 1 8 5 5 1 8 5 5 1 8 5 5 Step 51 to 55: #4 UP UP #0 RIGHT #9 DOWN #7 DOWN #6 RIGHT 6 7 2 4 6 7 2 4 6 7 2 4 6 2 4 6 2 4 3 9 2 4 3 9 2 4 3 2 4 3 7 2 4 3 7 2 4 3 0 0 --> 3 0 0 --> 3 9 0 0 --> 3 9 0 0 --> 3 9 0 0 --> 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 8 5 5 1 8 5 5 1 8 5 5 1 8 5 5 1 8 5 5 Step 56 to 60: #3 UP #1 UP #8 LEFT #9 DOWN DOWN #0 LEFT 3 6 2 4 3 6 2 4 3 6 2 4 3 6 2 4 3 6 2 4 3 7 2 4 3 7 2 4 3 7 2 4 3 7 2 4 3 7 2 4 9 0 0 --> 1 9 0 0 --> 1 9 0 0 --> 1 0 0 --> 1 0 0 --> 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 8 5 5 8 5 5 8 5 5 8 9 5 5 8 9 5 5 Step 61 to 65: #4 DOWN DOWN #2 RIGHT #6 RIGHT #7 RIGHT #3 RIGHT 3 6 2 3 6 2 3 6 2 3 6 2 3 6 2 3 7 2 3 7 2 3 7 2 3 7 2 3 7 2 1 0 0 4 --> 1 0 0 4 --> 1 0 0 4 --> 1 0 0 4 --> 1 0 0 4 --> 1 0 0 4 1 0 0 4 1 0 0 4 1 0 0 4 1 0 0 4 8 9 5 5 8 9 5 5 8 9 5 5 8 9 5 5 8 9 5 5 Step 66 to 70: #1 UP UP #0 LEFT #7 DOWN DOWN #6 DOWN DOWN #2 LEFT 1 3 6 2 1 3 6 2 1 3 6 2 1 3 2 1 3 2 1 3 7 2 1 3 7 2 1 3 2 1 3 2 1 3 2 0 0 4 --> 0 0 4 --> 0 0 4 --> 0 0 6 4 --> 0 0 6 4 --> 0 0 4 0 0 4 0 0 7 4 0 0 7 4 0 0 7 4 8 9 5 5 8 9 5 5 8 9 5 5 8 9 5 5 8 9 5 5 Step 71 to 75: #4 UP UP #7 RIGHT UP #5 UP #9 RIGHT RIGHT #8 RIGHT RIGHT 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 0 0 6 --> 0 0 6 7 --> 0 0 6 7 --> 0 0 6 7 --> 0 0 6 7 --> 0 0 7 0 0 0 0 5 5 0 0 5 5 0 0 5 5 8 9 5 5 8 9 5 5 8 9 8 9 8 9 Step 76 to 80: #0 DOWN #6 LEFT LEFT #7 LEFT LEFT #5 UP #8 UP RIGHT 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 6 7 --> 6 7 --> 6 7 --> 6 7 5 5 --> 6 7 5 5 --> 0 0 5 5 0 0 5 5 0 0 5 5 0 0 0 0 8 0 0 8 9 0 0 8 9 0 0 8 9 0 0 8 9 0 0 9 Step 81 to 81: #0 RIGHT 1 3 2 4 1 3 2 4 6 7 5 5 0 0 8 0 0 9 ---------------------------------------- Total steps: 81 ============ END OF REPORT =============