Super Mario Bros

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.

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">{{hint}}</p>
<div id="level" class="level"></div>
<div class="status" id="status">{{status_default}}</div>
<div class="btns">
  <button id="left" type="button">{{btn_left}}</button>
  <button id="right" type="button">{{btn_right}}</button>
  <button id="solve" type="button">{{btn_solve}}</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; }
.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; }

// Code not found

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.

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 $2^{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.

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

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.