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.