What the small Rubik’s cube taught me about data structures, information theory, and randomisation

This article discusses observations made when the state space of the 2 × 2 × 2 Rubik’s cube was constructed with various programs based on various data structures, gives theoretical explanations for the observations, and uses them to develop more memory-efficient data structures. The cube has 3,674,160 reachable states. The fastest program runs in 20 s 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 through which each state was first found. Its memory consumption is remarkably small, considering that 3,674,160 × 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 s. We also discuss the performance of BDDs and perfect state packing in this application.