What the Small Rubik's Cube Taught Me on Data Structures, Information
Theory and Randomisation
Antti
Valmari, Tampere University of Technology, Finland
This story tells about observations made when the state space of the
2x2x2 Rubik's cube was constructed with various programs based on
various data structures, gives theoretical explanations to the
observations, and uses them to develop more memory-efficient data
structures. The cube has 3674160 reachable states. The fastest program
runs in 20 seconds, and uses 11.1 million bytes of memory for the state
set structure. It uses a 31-bit representation of the state and also
stores the rotation via which each state was first found. Its memory
consumption is remarkably small, considering that 3674160 times 31 bits
is about 14.2 million bytes. Getting below this number was made
possible by sharing common parts of states. Obviously, it is not
possible to reduce memory consumption without limit. We derive an
information-theoretic hard average lower bound of 6.07 million bytes
that applies in this setting. We introduce a general-purpose variant of
the data structure and end up with 8.9 million bytes and 48 seconds. We
also discuss the performance of BDDs and perfect state packing in this
application.