# B Korf’s Optimal Solution to Rubik’s Cube Puzzle and Pattern Databases Appendix

```Appendix
B
Korf’s Optimal Solution to Rubik’s Cube
Puzzle and Pattern Databases
In this appendix we look at admissible heuristic functions for the Rubik’s cube puzzle
and the 15 and 24 tile puzzle based on pattern databases. A pattern database is a heuristic
function stored as a lookup table which stores the lengths of optimal solutions for instances
of subproblems. The results are from papers by Korf.
B.1
Rubik Cube
If we consider Rubik’s cube, it can be categorised using a state of 20 elements. This
consists of representations of the orientations of the sub–cubes which move. There are 8
corners and 12 edges. Each corner has 3 orientations and each edge 2 orientations. Thus
a state is a 20 element vector.
Typical a human solving the puzzle takes about 50 – 100 moves. This is done by using
learnt algorithms for manipulating pieces leaving others static (e. g. turning an edge cube
over while leaving others fixed).
There are 8! permutations of the 8 corners and 12! permutations of the 12 edges. Each
corner can have 3 orientations and each edge 2, so altogether the total number of states
is 8! × 38 × 12! × 212 . But these permutations are split into 12 mutual classes, so that
one can only transform between states in the same class. So from one state there are
8! × 38 × 12! × 212 /12 states reachable. This is 4.3 × 1019 .
Compared with the 15 puzzle – 1013 states. (16!/2).
Take as basic moves 90◦ clockwise, 90◦ counter–clockwise and 180◦ in each of the six
planes of the Rubik cube. We consider the centre of the cube as fixed in space and so
don’t rotate the three central planes – this determines the colours of the faces for the goal
state. The search tree then has 18 (6) way branching initially. Then 15 way branching
since rotating the same face consecutively results in a state which appears elsewhere in the
tree. However, twisting opposite faces commutes so we can reduce the branching further.
It can be shown that the average branching factor is 13.3.
xi
Depth
Nodes
1
18
2
243
3
3,240
4
43,254
5
577,368
6
7,706,988
7
102,876,480
8
1,373,243,544
9
18,330,699,168
10
244,686,773,808
11
3,266,193,870,720
12
43,598,688,377,184
13
581,975,750,199,168
14
7,768,485,393,179,328
15
103,697,388,221,736,960
16
1,384,201,395,738,071,424
17 18,476,969,736,848,122,368
18 246,639,261,965,462,754,048
Table B.1: Nodes in Search Tree
From table B.1 we see that there must be some problems requiring at least 18 moves
(could be much bigger), since number of reachable states using 17 moves is still less than
the total number of states possible.
Korf used variant of manhattan distance – distance is min number of moves to correct
position and orientation. To be admissible we divide by 8 as 1 basic move moves 4 other
corners and 4 edges. He actually used IDA* – the variant of A* called iterative deepening
A*. It is also possible to take a simpler heuristic – just use consider the edge cubes only
and divided by 4.
In general, the basic Manhattan distance gives too low a value and so in general there is
too much computation using this directly even if the values are precomputed. Computing
IDA* tree to a depth 14 would take 3 days , to 18 250 years. (on a Sparc Ultra).
A modified admissible heuristic was evaluated as follows:
h(n) = max{hcorners (n), he1 (n), he2 (n)}
where hcorners computes the minimum number of moves to ensure the all 8 corners are in
the correct position Figure B.1. This is precomputed using a breadth-first search from the
goal state. The last cube is determined by the others, and so there are 8!37 possibilities.
Each value can be stored using 4 bits since the maximum value is 11. 42M is needed for
this table.
xii
Figure B.1: Corner Database
(a) Edge Set1
(b) Edge Set2
Figure B.2: Two Edge Sets
The 12 edges are split into two groups of 6 Figure B.2. he1 then evaluates the minimum
numbers of moves to position the first set of edges cubes and he2 for the second set. The
number of possible combinations is 12!/6! · 26 . The maximum number of moves to orient 6
edges is 10 and so 4-bits can be used per position. Hence 20M is required for each table.
So altogether 82M is required for all tables.
The stored table is also called a pattern database. It took about 1 hour to compute
the table. This table needs to be stored in RAM for the IDA* algorithm, but this is now
possible with a reasonable workstation.
Korf performed experiments on states produce by making 100 random basic moves.
The table B.2 shows the statistics for 10 such cases. All had solutions within 18 moves
and 1 only 16 moves. It is thought that 20 moves is sufficient for all start states, but this
has not been proved.
So by careful choice of a heuristic it is possible to tackle these large combinatorial
problems where brute search would clearly be useless.
xiii
No. Depth Nodes Generated
1
16
3,720,885,493
2
17
11,485,155,726
3
17
64,837,508,623
4
17
126,005,368,381
5
18
262,228,269,081
6
18
344,770,394,346
7
18
502,417,601,953
8
18
562,494,969,937
9
18
626,785,460,346
10
18
1,021,814,815,051
Table B.2: Table of Results
B.2
15 and 24 Tile Puzzle
Pattern databases for the 15 puzzle were first introduced by Culberson and Schaeffer.
One example of splitting the 15 puzzle into subproblems is indicated in Figure B.3.
Figure B.3: 15 Puzzle Pattern Database
The 8 blue (light grey) tiles are in one set and the 7 red (dark grey) in the other.
The two databases are computed (offline) using a backward breadth first search from the
goal state. The non-pattern tiles are not distinguished but their moves are counted. The
heuristic for the 15 puzzle is then taken as the maximum of these two heuristics. So in the
above example, 31 moves can solve the red tiles and 22 the blue. So the heuristic value
for the configuration on the left is taken as 31. This is then clearly an admissible heuristic
since both sets of tiles have to be put into their final positions. Other divisions of the tiles
is possible as alternative for the pattern databases (they could even overlap). Figure B.4
shows another possible split.
xiv
Figure B.4: Alternative 15 Puzzle Pattern Database
Korf changed the way he counted the moves so that the moves of non-pattern tiles are
ignored. As long as the subsets don’t overlap, then instead of maximising the two heuristic
values they can be added as any one tile will only belong to one set.
Taking the configuration in Figure B.5, 20 moves are needed to position the red tiles
and 25 moves for the blue. Hence the heuristic value for the configuration will be taken
as 20+25 = 45 which will be a lower bound on the minimal number of moves to solve the
puzzle and so is admissible. The 7-tile database has about 58 million entries and the 8-tiles
Figure B.5: Configuration with Goal
xv
Korf used an additive pattern database for the 24 puzzle based on the subsets indicated
in Figure B.6. All subsets have six tiles and the pattern databases contain about 128 million
entries. IDA* can solve optimally random 24-puzzle configurations using this heuristic
(sum of the four heuristics on the subsets) in about 100 moves. The running time in his
experiments were 18 seconds to 10 days with an average of about 1.5 days.
Figure B.6: 24 Puzzle Subsets
xvi
```