Introduction

For a generation, Super Mario Bros was the first video game many of us ever touched. The goal is simple: get the little plumber from the left edge of the screen to the flag on the right, jumping over pits and stomping enemies along the way.

On a normal level your instinct does the work. But imagine a level stuffed with switches, locked doors, and keys — flipping one switch raises a wall here and lowers a platform there, and the same passage you just used may now be sealed forever. Suddenly "can Mario even reach the flag?" stops being obvious.

That question — is the goal reachable at all? — is not a quirk of level design. It turns out to be one of the hardest kinds of question we know how to ask about a system that has lots of internal state.

Reach the Flag

Here is a tiny level. Mario starts on the left; the flag is on the right. Between them are doors that are toggled by switches Mario steps on. Move with the buttons and try to find a path to the flag — then let the computer search for you.

<p class="hint">Mario starts on the left; reach the <b>flag</b> on the right. Stepping on a colored <b>switch</b> toggles the matching <b>door</b> (a closed door blocks you). A passage you opened can slam shut again — so the order of your moves matters. Checking a walkthrough is instant; <b>searching</b> for one explodes as switches multiply.</p>
<div id="level" class="level"></div>
<div class="status" id="status">Use ◀ ▶ to walk. Step on switches to toggle doors.</div>
<div class="btns">
  <button id="left" type="button">◀ Move left</button>
  <button id="right" type="button">▶ Move right</button>
  <button id="solve" type="button">Let the computer search</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; }
.level { display: grid; grid-template-columns: repeat(9, 44px); gap: 4px; margin: .5rem 0; }
.tile { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        font: 700 20px ui-monospace, monospace; border-radius: 8px; user-select: none;
        border: 1px solid #cdd9e3; background: #eef4f8; }
.tile.path { background: #dfeaf2; }
.tile.switch { background: #fff4d6; border-color: #e8c766; }
.tile.flag { background: #d8f3df; border-color: #8fd6a6; }
.tile.door { background: #c9ccd1; border-color: #adb1b8; }
.tile.door.open { background: #eef4f8; border-color: #cdd9e3; }
.tile.mario { box-shadow: inset 0 0 0 3px #e63946; }
.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 .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Generalized Super Mario reachability (1-D slice). The level is a row of tiles.
// A "configuration" = Mario's position AND the open/closed state of every door.
// Stepping on a switch flips its door. A closed door cannot be entered.
// Question: from the start config, is the flag reachable? This is the PSPACE-shaped
// problem (Demaine, Viglietta, Williams). The computer answers it with a BFS over the
// graph of configurations — whose size is (tiles) x 2^(#doors).
const N = 9;
const START = 0, FLAG = 8;
// tile -> {switch: doorId} steps that flip a door when entered.
const SWITCHES = { 2: 0, 5: 1 };      // tile 2 toggles door A, tile 5 toggles door B
const DOORS = { 4: 0, 7: 1 };          // tile 4 = door A, tile 7 = door B
// Initial door states (false = closed). Door A starts CLOSED, door B starts OPEN.
const INIT = [false, true];
const NDOORS = INIT.length;

let pos = START;
let doors = INIT.slice();
let lastSolution = null;

const doorOf = (t) => (t in DOORS) ? DOORS[t] : -1;
const isOpen = (t, d) => { const id = doorOf(t); return id < 0 ? true : d[id]; };

// Apply entering a tile: if it carries a switch, toggle that door.
function enter(t, d){ const nd = d.slice(); if (t in SWITCHES) nd[SWITCHES[t]] = !nd[SWITCHES[t]]; return nd; }

function step(dir){
  const t = pos + dir;
  if (t < 0 || t >= N) return;
  if (!isOpen(t, doors)) { setStatus('A closed door blocks you there.', 'bad'); return; }
  doors = enter(t, doors); pos = t;
  if (pos === FLAG) setStatus('You reached the flag!', 'ok');
  else setStatus('', '');
  render();
}

function render(){
  const lv = document.getElementById('level'); lv.innerHTML = '';
  for (let t = 0; t < N; t++){
    const d = document.createElement('div'); d.className = 'tile';
    if (t in SWITCHES) d.classList.add('switch');
    if (t in DOORS){ d.classList.add('door'); if (isOpen(t, doors)) d.classList.add('open'); }
    if (t === FLAG) d.classList.add('flag');
    if (t === pos) d.classList.add('mario');
    if (t in SWITCHES) d.textContent = 'S';
    else if (t in DOORS) d.textContent = isOpen(t, doors) ? '·' : '▮';
    else if (t === FLAG) d.textContent = '⚑';
    else if (t === pos) d.textContent = 'M';
    lv.appendChild(d);
  }
  if (document.getElementById('level').querySelector('.mario') === null){}
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t || 'Use ◀ ▶ to walk. Step on switches to toggle doors.'; s.className = 'status ' + cls; }

// BFS over configurations: state = position + door bitmask.
function encode(p, d){ let m = 0; for (let i = 0; i < NDOORS; i++) if (d[i]) m |= (1 << i); return p + ':' + m; }
function solve(){
  const startKey = encode(START, INIT);
  const seen = new Set([startKey]);
  const prev = new Map();
  const queue = [{ p: START, d: INIT.slice() }];
  let explored = 0, goal = null;
  while (queue.length){
    const cur = queue.shift(); explored++;
    if (cur.p === FLAG){ goal = cur; break; }
    for (const dir of [-1, 1]){
      const t = cur.p + dir;
      if (t < 0 || t >= N) continue;
      if (!isOpen(t, cur.d)) continue;
      const nd = enter(t, cur.d);
      const key = encode(t, nd);
      if (!seen.has(key)){ seen.add(key); prev.set(key, encode(cur.p, cur.d)); queue.push({ p: t, d: nd }); }
    }
  }
  const total = N * (1 << NDOORS);
  if (goal){
    lastSolution = goal;
    pos = goal.p; doors = goal.d; render();
    setStatus(fmt('Reachable! BFS explored %explored% of %total% configurations.', { explored: explored, total: total }), 'ok');
    console.log('Flag reachable. Explored', explored, 'of', total, 'configurations.');
  } else {
    setStatus('The flag is NOT reachable from the start — no sequence of moves works.', 'bad');
    console.log('Flag unreachable. Explored', explored, 'of', total, 'configurations.');
  }
}

document.getElementById('left').addEventListener('click', () => step(-1));
document.getElementById('right').addEventListener('click', () => step(1));
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => { pos = START; doors = INIT.slice(); render(); setStatus('', ''); });
render();
Result
Console

Notice the catch. A single screen with a few switches has many possible configurations — Mario's position times every on/off combination of the doors. The computer can find a solution by exploring this whole graph of configurations, but its size doubles with every switch you add. Checking a finished walkthrough is easy; searching for one in a level with hundreds of switches is where things blow up.

The Real Complexity

How hard is Super Mario Bros, really? Not the reflexes — the decision: given a level, can Mario reach the goal at all?

  • Checking a proposed walkthrough is easy: replay the moves and see if Mario survives to the flag.
  • Brute force explores the level's configurations — Mario's position combined with the state of every switch and door. With n switches that's up to 2n2^{n} configurations, hopeless for large levels.
  • It's PSPACE-complete. In the paper "Classic Nintendo Games Are (Computationally) Hard" (Aloupis, Demaine, Guo, Viglietta; with later sharpenings by Demaine, Viglietta, Williams), researchers showed that deciding whether a generalized Super Mario Bros level is completable is as hard as any problem solvable in polynomial space. They built gadgets out of in-game elements that wire a level into a Quantified Boolean Formula.
  • PSPACE sits above NP. Problems like SAT are NP-complete; reachability with this kind of reusable, toggle-able state lands in the larger class PSPACE, believed to be strictly harder.

That is the punchline: the moment a level lets switches reconfigure passages you've already crossed, "is the flag reachable?" becomes a genuine instance of a PSPACE-complete problem — the same wall you meet in P vs NP and beyond.

Where It Matters

"Can this system, by flipping switches, ever reach that configuration?" is one of the deepest questions in computing, and Super Mario is its playful face:

  • Model checking and verification: proving that a chip or protocol can never reach an unsafe state is a giant reachability question — exactly the PSPACE shape.
  • Planning and robotics: deciding whether a robot with many movable obstacles can reach a target (motion planning) is famously PSPACE-hard.
  • Puzzle and game AI: solvers for sokoban, sliding blocks, and switch-and-door dungeons all wrestle with the same configuration explosion.
  • Teaching complexity: because the rules are familiar, Mario is a vivid on-ramp to what polynomial space and PSPACE-completeness actually mean.

Learn why Super Mario is hard and you've met reachability with reusable state — the engine under model checking, planning, and the gadget proofs that connect games to SAT.

Conclusion

Super Mario Bros hides a beautiful secret: the switches and doors that make a level interesting can be wired into logical quantifiers, and through them into any problem solvable in polynomial space. Replaying a walkthrough stays instant; deciding whether a level can be finished at all is PSPACE-complete.

So the next time a level loops you back and a wall you opened slams shut, take comfort — you haven't lost the knack. You've simply bumped into a genuine instance of one of the hardest reachability problems we know, dressed up in overalls and a red cap. The limits explored in P vs NP are right there under the flagpole.

Share this article

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

Comments

Loading comments...

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