Mahjong Solitaire

You have seen it on every computer: a pile of decorated tiles stacked into a dragon or a pyramid. Mahjong solitaire asks one calm thing of you — find two matching tiles that are free (not covered, open on the left or right), remove them as a pair, and repeat until the table is empty.

It feels effortless. But there is a trap hiding under the relaxation. Sometimes two identical tiles are both free, and the order in which you take pairs decides everything. Remove the wrong pair now and you may strand a tile under a stack forever — a deadlock with matching tiles still on the board and no legal move left.

So a quieter question lurks beneath every layout: is this deal winnable at all, or were you doomed before you touched a single tile? That little question is not a quirk of the game. It is the same line that separates the easy problems from the hardest ones in all of computer science.

Here is a tiny Mahjong layout. A tile is free if nothing sits on top of it and at least one side (left or right) is open. Click a free tile, then click its matching twin to remove the pair. Clear all the tiles to win.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <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; }
.board { position: relative; height: 110px; margin: .6rem 0; }
.tile { position: absolute; width: 52px; height: 64px; display: flex; align-items: center;
        justify-content: center; font: 700 26px ui-monospace, monospace; border-radius: 8px;
        background: #f6efe0; border: 2px solid #c9b78c; color: #6b3f12; box-shadow: 2px 2px 0 #c9b78c;
        user-select: none; transition: transform .08s; }
.tile.free { cursor: pointer; }
.tile.free:hover { transform: translateY(-2px); }
.tile.covered, .tile.blocked { filter: brightness(.82) saturate(.6); cursor: not-allowed; box-shadow: none; }
.tile.sel { outline: 3px solid #2a7de1; outline-offset: 1px; }
.tile.gone { display: none; }
.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 #6b3f12;
         background: #6b3f12; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #6b3f12; }

// Code not found

Notice the asymmetry. Checking a finished sequence of moves is effortless — replay it and confirm every pair was legal and the board ended empty. Finding a winning order is the hard part. Press Auto-solve and the computer searches through the possible move orders; press Reset and try the trap layout, where one greedy wrong move locks the board into a dead end with tiles still on it.

How hard is Mahjong solitaire, really? Not the clicking — the planning.

• Checking a candidate solution is trivial: replay the list of pairs and confirm each removal was legal and the board ended empty.
• Brute force tries every order in which free pairs could be removed. The branching is small at each step, but the number of orderings explodes — and a single early mistake can poison the whole rest of the game.
• It's NP-complete. The decision question — "is there any order of moves that clears this layout?" — is as hard as any problem in NP. Researchers prove this by building logical gadgets out of tiles: a layout where one matching pair can be removed in two ways, and each choice is forced to behave like setting a variable true or false in a SAT formula. The layout clears if and only if the formula is satisfiable.
• So even deciding is-this-deal-winnable is equivalent to the whole NP-complete family. The classic single-suit board Shisen-Sho shares the same hardness, and so do many tile-matching puzzles.

That is the punchline: the moment a layout can't be cleared by quick greedy matching, you are staring at a genuine instance of the same problem behind P vs NP. The deals that lock up on you are not bad luck — some are simply impossible, and telling which is intractable.

"Pick the right order of moves so you never get stuck" is one of the most common shapes a real problem can take, and Mahjong solitaire is its friendly face:

• Planning and scheduling: when each action unlocks others and a wrong early choice dead-ends the whole plan, you are solving a Mahjong-shaped puzzle.
• Dependency resolution: package managers and build systems must remove or install items in an order that never strands a dependency — the same "don't deadlock" question.
• Resource and inventory removal: clearing a warehouse, a stack of containers, or a buffer in an order that avoids blocking is the literal tile-matching problem.
• Teaching complexity: because the rules are so simple and everyone has played it, Mahjong solitaire is a clear on-ramp to what NP-completeness even means.

Learn why Mahjong solitaire is hard and you've met combinatorial planning — the same engine behind SAT, scheduling and countless ordering problems.

Mahjong solitaire hides a beautiful secret: the same matching choices that feel so calm can be wired into logic gadgets, and through them into any problem in NP. Checking a solved board stays instant; deciding whether a layout can be cleared at all is as hard as anything in computer science.

So the next time the tiles lock up with pairs still staring at you, take comfort — you may not have played badly. You've simply run into P vs NP hiding behind a stack of dragons, and for some deals there may be no winning order at all.