Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramowitz, M., Stegun, I. (eds.): Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables. New York: Dover 1970
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677–691 (1986)
Geldenhuys, J., Valmari, A.: Techniques for smaller intermediary BDDs. In: CONCUR 2001 – 12th International Conference on Concurrency Theory, Aalborg, Denmark, 21–24 August 2001. Lecture Notes in Computer Science, vol. 2154, pp. 233–247. Berlin, Heidelberg, New York: Springer 2001
Geldenhuys, J., Valmari, A.: A nearly memory-optimal data structure for sets and mappings. In: Proceedings of the 10th International SPIN Workshop on Model Checking Software, Portland, OR, 9–10 May 2003. Lecture Notes in Computer Science, vol. 2648, pp. 136–150. Berlin, Heidelberg, New York: Springer 2003
Knuth, D.E.: The Art of Computer Programming, vol 3: Sorting and Searching. Reading, MA: Addison-Wesley 1973
Liaw, H.-T., Lin, C.-S.: On the OBDD-representation of general boolean functions. IEEE Trans. Comput. 41(6), 661–664 (1992)
Myrvold, W., Ruskey, F.: Ranking and unranking permutations in linear time. Inform. Process. Lett. 79(6), 281–284 (2001)
Valmari, A.: Mitä pieni Rubikin kuutio opetti minulle tie-torakenteista, informaatioteoriasta ja satunnaisuudesta. Tietojenkäsittelytiede 20, 53–78 (2003)
Wegener, I.: The size of reduced OBDD’s and optimal read-once branching programs for almost all boolean functions. IEEE Trans. Comput. 43(11), 1262–1269 (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Valmari, A. What the small Rubik’s cube taught me about data structures, information theory, and randomisation. Int J Softw Tools Technol Transfer 8, 180–194 (2006). https://doi.org/10.1007/s10009-005-0191-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10009-005-0191-z