# Solving the Rubik's Cube Optimally is NP-complete

arXiv: https://arxiv.org/abs/1706.06708 · HTML: https://mlsanity.com/paper/1706.06708/

## Key facts

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

## Built on by (most cited first, 10 of 10)

- [Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generation](https://mlsanity.com/paper/2311.04254/) (2023)
- [Puzzle Solving without Search or Human Knowledge: An Unnatural Language Approach](https://mlsanity.com/paper/2109.02797/) (2021)
- [CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs](https://mlsanity.com/paper/2502.18663/) (2025)
- [Contrastive Representations for Temporal Reasoning](https://mlsanity.com/paper/2508.13113/) (2025)
- [Self-Supervision is All You Need for Solving Rubik's Cube](https://mlsanity.com/paper/2106.03157/) (2021)
- [What Matters in Hierarchical Search for Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2406.03361/) (2024)
- [CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)](https://mlsanity.com/paper/2509.19162/) (2025)
- [Reconfiguring Shortest Paths in Graphs](https://mlsanity.com/paper/2112.07499/) (2021)
- [The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems](https://mlsanity.com/paper/2209.03393/) (2022)
- [Universality in Collective Intelligence on the Rubik's Cube](https://mlsanity.com/paper/2511.18609/) (2025)

## 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.