Rubik's Cube

Hold a Rubik's cube and give it a few twists. In seconds you can reach a position no human has ever seen before — the 3×3 cube has 43,252,003,274,489,856,000 distinct states, about 43 quintillion. Scramble it properly and the odds of two people landing on the same mess are essentially zero.

And yet here is the shock: every single one of those 43 quintillion positions can be solved in 20 moves or fewer. That number — 20 — is called God's Number, and it was proven in 2010 by a team using clever group theory and weeks of donated Google computing time.

So which is it — trivially easy or impossibly hard? The cube sits exactly on the seam between the two, and that seam is where complexity theory lives.

Here is a simplified cube — a single ring of stickers you can rotate left or right, plus a couple of swaps. Scramble it, then try to bring it back to order. Each button is one move.

<p class="hint">{{hint}}</p>
<div id="ring" class="ring"></div>
<div class="status" id="status">{{press_scramble}}</div>
<div class="btns">
  <button id="mL" type="button">L ↺</button>
  <button id="mR" type="button">R ↻</button>
  <button id="mS" type="button">S ⇅</button>
  <button id="scramble" type="button" class="alt">{{btn_scramble}}</button>
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ring { display: grid; grid-template-columns: repeat(8, 40px); gap: 5px; margin: .6rem 0; }
.st { width: 40px; height: 40px; border-radius: 8px; border: 1px solid rgba(0,0,0,.18);
      display: flex; align-items: center; justify-content: center;
      font: 700 13px ui-monospace, monospace; color: rgba(0,0,0,.45); }
.c0 { background: #e63946; } .c1 { background: #f4a261; } .c2 { background: #e9c46a; }
.c3 { background: #2a9d8f; } .c4 { background: #277da1; } .c5 { background: #5e548e; }
.c6 { background: #b5179e; } .c7 { background: #adb5bd; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.alt { background: #2a9d8f; border-color: #21847a; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a solution is instant: replay the moves and see if every sticker is home. Finding the shortest solution is the hard part — press Find shortest solution and the computer searches outward from the scramble, trying every move sequence until it stumbles onto the goal. Each extra move multiplies the number of sequences it must explore. On a real 3×3 that explosion is the difference between "always ≤20 moves exist" and "good luck finding them by brute force."

How hard is the cube, really? The answer splits in two.

• The fixed 3×3 has a constant diameter. In 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge proved that God's Number is exactly 20 in the half-turn metric: every one of the 43 quintillion states is solvable in at most 20 face turns, and some need all 20. Because the cube's size is fixed, a computer can in principle look up the answer — the hardness is constant, not growing.
• Checking a proposed solution is trivial: apply the moves and verify the cube is solved.
• Brute-force searching for the shortest solution still explodes: roughly 18 choices per move means the search tree grows like 18ᵈ at depth d.
• The generalized cube is NP-complete. In 2017, Erik Demaine, Sarah Eisenstat and Mikhail Rudoy proved that deciding whether a scrambled n×n×n cube can be solved in at most k moves is NP-complete — as hard as any problem in NP. Let the cube grow, and finding optimal solutions joins the hardest problems we know.

That is the punchline: the toy on your desk is easy only because it never grows. Allow the puzzle to scale, and its shortest-solution question sits right alongside SAT and the whole NP-complete family.

"Reach a goal state through a sequence of reversible moves" is one of the deepest shapes in computer science, and the cube is its most photogenic example:

• Heuristic search: the cube was the proving ground for IDA* with pattern databases — precomputed tables that estimate how far a state is from solved, the same idea behind modern AI planners.
• Group theory: the cube is a finite group, and the tricks used to bound God's Number echo in cryptography and error-correcting codes.
• Robotics and planning: a robot arm rearranging objects faces the same "configuration space" search as a cube solver.
• Teaching complexity: because everyone has held one, the cube is a vivid way to explain why "small to check, huge to search" is the heart of P vs NP.

Understand the cube and you've met combinatorial search and group structure — the machinery under countless planning, coding and optimization problems.

The Rubik's cube is a perfect little paradox. Its 43 quintillion states feel boundless, yet every one is at most 20 moves from solved — a diameter so small it almost seems unfair. The catch is that this neatness depends on the cube staying 3×3. Let it grow to n×n×n and finding the shortest solution becomes NP-complete.

So the next time you twist a cube back into order, remember the strange fact in your hands: checking that it's solved takes a glance, a solution always exists within 20 moves, and yet the general version of this toy is as hard as anything in computer science. That is P vs NP, spinning in your palm.