{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:56Z","timestamp":1725603656971},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_58","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"689-700","source":"Crossref","is-referenced-by-count":10,"title":["Algorithms for Solving Rubik\u2019s Cubes"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"Martin L.","family":"Demaine","sequence":"additional","affiliation":[]},{"given":"Sarah","family":"Eisenstat","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Winslow","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"58_CR1","unstructured":"World\u00a0Cube Association. Official results (2010), http:\/\/www.worldcubeassociation.org\/results\/"},{"issue":"1","key":"58_CR2","first-page":"40","volume":"128","author":"S.A. Cook","year":"1984","unstructured":"Cook, S.A.: Can computers routinely discover mathematical proofs? Proceedings of the American Philosophical Society\u00a0128(1), 40\u201343 (1984)","journal-title":"Proceedings of the American Philosophical Society"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Driscoll, J.R., Furst, M.L.: On the diameter of permutation groups. In: Proceedings of the 15th Annual ACM Symposium on Theory of computing, pp. 152\u2013160 (1983)","DOI":"10.1145\/800061.808744"},{"key":"58_CR4","unstructured":"Drucker, A., Erickson, J.: Is optimally solving the n \u00d7n \u00d7n Rubik\u2019s Cube NP-hard? Theoretical Computer Science \u2014 Stack Exchange post (August-September 2010), http:\/\/cstheory.stackexchange.com\/questions\/783\/isoptimally-solving-the-nnn-rubiks-cube-np-hard"},{"issue":"3","key":"58_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0196-6774(81)90029-8","volume":"2","author":"S. Even","year":"1981","unstructured":"Even, S., Goldreich, O.: The minimum-length generator sequence problem is NP-hard. Journal of Algorithms\u00a02(3), 311\u2013313 (1981)","journal-title":"Journal of Algorithms"},{"key":"58_CR6","unstructured":"Fox, F.: Spherical 3x3x3. U.K. Patent 1,344,259 (January 1974)"},{"key":"58_CR7","doi-asserted-by":"crossref","unstructured":"Furst, M., Hopcroft, J., Luks, E.: Polynomial-time algorithms for permutation groups. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pp. 36\u201341 (1980)","DOI":"10.1109\/SFCS.1980.34"},{"key":"58_CR8","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st edn. Series of Books in the Mathematical Sciences. W. H. Freeman & Co Ltd., New York (1979)","edition":"1"},{"key":"58_CR9","unstructured":"Gustafson, W.O.: Manipulatable toy. U.S. Patent 3,081,089 (March 1963)"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"Ishige, T.: Japan Patent 55-8192 (1976)","DOI":"10.5179\/benthos1970.1976.55"},{"issue":"2-3","key":"58_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M.R. Jerrum","year":"1985","unstructured":"Jerrum, M.R.: The complexity of finding minimum-length generator sequences. Theoretical Computer Science\u00a036(2-3), 265\u2013289 (1985)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"58_CR12","first-page":"13","volume":"31","author":"G. Kendall","year":"2008","unstructured":"Kendall, G., Parkes, A., Spoerer, K.: A survey of NP-complete puzzles. International Computer Games Association Journal\u00a031(1), 13\u201334 (2008)","journal-title":"International Computer Games Association Journal"},{"key":"58_CR13","unstructured":"Krell, U.: Three dimensional puzzle. U.S. Patent 4,600,199 (July 1986)"},{"key":"58_CR14","unstructured":"Le., L.: The world\u2019s first 12x12x12 cube. twistypuzzles.com forum post (November 2009), http:\/\/www.twistypuzzles.com\/forum\/viewtopic.php?f=15&t=15424"},{"key":"58_CR15","unstructured":"Seven\u00a0Towns Ltd. 30 years on\u2026and the Rubik\u2019s Cube is as popular as ever. Press brief (May 2010), http:\/\/www.rubiks.com\/i\/company\/medialibrary\/pdf\/Rubiks%20Cube%20to%20celebrate%2030th%20Anniversary%20in%20May%202010.pdf"},{"issue":"5","key":"58_CR16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(84)90062-0","volume":"19","author":"P. McKenzie","year":"1984","unstructured":"McKenzie, P.: Permutations of bounded degree generate groups of polynomial diameter. Information Processing Letters\u00a019(5), 253\u2013254 (1984)","journal-title":"Information Processing Letters"},{"key":"58_CR17","unstructured":"Nichols, L.D.: Pattern forming puzzle and method with pieces rotatable in groups. U.S. Patent 3,655,201 (April 1972)"},{"key":"58_CR18","unstructured":"Museum of\u00a0Modern\u00a0Art. Rubik\u2019s cube, http:\/\/www.moma.org\/collection\/browse_results.php?object_id=2908"},{"issue":"1","key":"58_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J. Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM Journal on Computing\u00a08(1), 111\u2013114 (1979)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"58_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(95)00134-X","volume":"56","author":"I. Parberry","year":"1995","unstructured":"Parberry, I.: A real-time algorithm for the (n 2\u2009\u2212\u20091)-puzzle. Information Processing Letters\u00a056(1), 23\u201328 (1995)","journal-title":"Information Processing Letters"},{"key":"58_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Ratner","year":"1990","unstructured":"Ratner, D., Warmuth, M.: The (n 2\u2009\u2212\u20091)-puzzle and related relocation problems. Journal of Symbolic Computation\u00a010, 111\u2013137 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"58_CR22","unstructured":"Rokicki, T., Kociemba, H., Davidson, M., Dethridge, J.: God\u2019s number is 20 (2010), http:\/\/cube20.org"},{"key":"58_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"58_CR24","unstructured":"Sch\u00fctze, I.: V-cubes Solutions, http:\/\/solutions.v-cubes.com\/solutions2\/"},{"key":"58_CR25","unstructured":"Sebesteny, P.: Puzzle-cube. U.S. Patent 4,421,311 (December 1983)"},{"key":"58_CR26","unstructured":"Slocum, J.: The Cube: The Ultimate Guide to the World\u2019s Bestselling Puzzle \u2014 Secrets, Stories, Solutions. Black Dog & Leventhal Publishers (March 2009)"},{"key":"58_CR27","unstructured":"V-CUBE. V-cube: the 21st century cube, http:\/\/www.v-cubes.com\/"},{"key":"58_CR28","unstructured":"van Deventer, O.: Overlap cube 2x2x23. shapeways design, http:\/\/www.shapeways.com\/model\/96696\/overlap_cube_2x2x23.html"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T03:16:36Z","timestamp":1638414996000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}