License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.24
URN: urn:nbn:de:0030-drops-85336
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8533/
Go to the corresponding LIPIcs Volume Portal

Demaine, Erik D. ; Eisenstat, Sarah ; Rudoy, Mikhail

Solving the Rubik's Cube Optimally is NP-complete

pdf-format:
LIPIcs-STACS-2018-24.pdf (0.6 MB)

Abstract

In this paper, we prove that optimally solving an n x n x n Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n x n x n Rubik's Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik's Square--an n x n x 1 generalization of the Rubik's Cube--and then proceed with a similar but more complicated proof for the Rubik's Cube case. Our results hold both when the goal is make the sides monochromatic and when the goal is to put each sticker into a specific location.

BibTeX - Entry

@InProceedings{demaine_et_al:LIPIcs:2018:8533,
  author =	{Erik D. Demaine and Sarah Eisenstat and Mikhail Rudoy},
  title =	{{Solving the Rubik's Cube Optimally is NP-complete}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8533},
  URN =		{urn:nbn:de:0030-drops-85336},
  doi =		{10.4230/LIPIcs.STACS.2018.24},
  annote =	{Keywords: combinatorial puzzles, NP-hardness, group theory, Hamiltonicity}
}

Keywords: combinatorial puzzles, NP-hardness, group theory, Hamiltonicity
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI