Introduction

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.

Scramble and Solve

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">A mini "cube": eight colored stickers on a ring. Three moves shuffle them — <b>L</b> rotates the ring left, <b>R</b> rotates it right, <b>S</b> swaps the top two. Scramble it, then bring all colors back to order. Checking a solution is a glance; finding the <i>shortest</i> one is a search.</p>
<div id="ring" class="ring"></div>
<div class="status" id="status">Press Scramble to begin.</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">Scramble</button>
  <button id="find" type="button">Find shortest solution</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A toy "cube": 8 stickers on a ring. Three generators shuffle the state:
//   L = rotate the ring one step left, R = rotate one step right, S = swap pos 0 & 1.
// The SOLVED state is [0,1,2,3,4,5,6,7]. Like a real cube, CHECKING a sequence is a quick replay, but FINDING the SHORTEST solution means searching the reachable states.
// We use breadth-first search (BFS) = the optimal-move oracle, the same idea
// that, scaled up, makes the generalized cube NP-complete (Demaine et al., 2017).
const N = 8;
const SOLVED = [0,1,2,3,4,5,6,7];
let state = SOLVED.slice();

const L = s => s.slice(1).concat(s[0]);            // rotate left
const R = s => [s[N-1]].concat(s.slice(0, N-1));   // rotate right
const S = s => { const t = s.slice(); [t[0], t[1]] = [t[1], t[0]]; return t; };
const MOVES = { L, R, S };

function render() {
  const r = document.getElementById('ring'); r.innerHTML = '';
  state.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'st c' + v; d.textContent = i; // index label shows target position
    r.appendChild(d);
  });
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
const solved = s => s.every((v, i) => v === i);

function apply(name) {
  state = MOVES[name](state); render();
  setStatus(solved(state) ? '✓ Solved! Every sticker is home.' : 'Keep going…', solved(state) ? 'ok' : '');
}

function scramble() {
  const names = ['L','R','S']; let n = 12;
  while (n--) state = MOVES[names[Math.floor(Math.random()*3)]](state);
  if (solved(state)) state = L(state); // never hand back an already-solved scramble
  render(); setStatus('Scrambled. Bring the colors back to order.', '');
}

// BFS from the current state to SOLVED: shortest solution by construction.
function find() {
  const start = state.slice();
  if (solved(start)) { setStatus('Already solved — 0 moves needed.', 'ok'); return; }
  const seen = new Set([start.join(',')]);
  let frontier = [{ s: start, path: [] }], depth = 0, visited = 0;
  while (frontier.length) {
    const next = [];
    for (const node of frontier) {
      visited++;
      for (const name of ['L','R','S']) {
        const ns = MOVES[name](node.s), key = ns.join(',');
        if (seen.has(key)) continue;
        const path = node.path.concat(name);
        if (solved(ns)) {
          setStatus(fmt('Shortest solution: %path%  (%length% moves, %visited% states explored)', { path: path.join(' '), length: path.length, visited: visited }), 'ok');
          console.log('shortest', path.join(''), 'len', path.length, 'visited', visited);
          return;
        }
        seen.add(key); next.push({ s: ns, path });
      }
    }
    frontier = next; depth++;
    if (depth > 40) break;
  }
  setStatus('No solution found (unreachable).', 'bad');
}

document.getElementById('mL').addEventListener('click', () => apply('L'));
document.getElementById('mR').addEventListener('click', () => apply('R'));
document.getElementById('mS').addEventListener('click', () => apply('S'));
document.getElementById('scramble').addEventListener('click', scramble);
document.getElementById('find').addEventListener('click', find);
document.getElementById('reset').addEventListener('click', () => { state = SOLVED.slice(); render(); setStatus('Reset to solved.', 'ok'); });
render();
Result
Console

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

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rubik/Content licensed under CC BY-NC 4.0.