mlsanityData to 7 Oct 2026

Solving the Rubik's Cube Optimally is NP-complete

arXiv 1706.06708 ↗First posted 21 Jun 2017cs.CC cs.CG math.COcited by 10

Not on the map. Why?

Abstract (arXiv)

In this paper, we prove that optimally solving an n × n × 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 × n × 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 × n × 1 generalization of the Rubik's Cube---and then proceed with a similar but more complicated proof for the Rubik's Cube case.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Jun 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 1; 2023: 1; 2024: 1; 2025: 4.

10 papers.

  1. 2023Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generationcited by 73
  2. 2021Puzzle Solving without Search or Human Knowledge: An Unnatural Language Approachcited by 8
  3. 2025CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphscited by 5
  4. 2025Contrastive Representations for Temporal Reasoningcited by 5
  5. 2021Self-Supervision is All You Need for Solving Rubik's Cubecited by 4
  6. 2024What Matters in Hierarchical Search for Combinatorial Reasoning Problems?cited by 1
  7. 2025CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)cited by 1
  8. 2021Reconfiguring Shortest Paths in Graphscited by 0
  9. 2022The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problemscited by 0
  10. 2025Universality in Collective Intelligence on the Rubik's Cubecited by 0