Can You Guard "One Key, One Door"? — Where Dungeon Generation Struggles, and Why a Puzzle About Stacking Colors Is NP-Hard

Introduction

Today's Tsumiki roundup. Two pieces today.

One is about generating mazes and dungeons automatically. The other is about mathematically proving a puzzle's difficulty. I want to follow these two mirrored angles — the making side and the difficulty-proving side.

What Changes When You Pair Evolutionary Search With Maze and Dungeon Generation? — Evolutionary Wave Function Collapse (IEEE CoG 2026)

The short answer: properties that are decided purely by local, place-by-place relationships get better, but properties that span the entire level are still hard to guarantee. "Evolutionary Wave Function Collapse," presented at IEEE CoG 2026 (September 1-4, 2026, Madrid; Procedural Content Generation session, presented September 2), pairs evolutionary search with Wave Function Collapse (WFC), the standard method for generating maze and dungeon tiles. The authors are Dipika Rajesh (UC Santa Cruz), Ahmed Khalifa (University of Malta), and Julian Togelius (New York University). I read the arXiv preprint (2607.02082), posted in July 2026.

WFC learns only local adjacency constraints — which tile is allowed next to which — from a small example input, then assembles a much larger output from those rules. Because it's computationally cheap and conceptually simple, it's widely used for generating maze and dungeon tiles. But it has a weakness: a stack of purely local rules learned from an example can't guarantee constraints that require looking at the whole level at once, like placing exactly one key and one door on the entire map.

Rather than editing WFC's generated output directly, this paper evolves the small example input fed into WFC. It treats the example as a genotype and the level WFC produces from it as a phenotype, scoring each resulting level and gradually mutating the example. Two test domains are used: maze connectivity, and the room layout of Zelda-style dungeons.

The results split cleanly. For properties like maze connectivity, which can be judged purely from local relationships anywhere on the board, evolutionary optimization clearly helped. But for dungeon constraints that require seeing the whole level at once — like placing exactly one key and one door — evolving the example alone still let things break down, exposing the fundamental limits of a purely local pattern model.

The takeaway: a local-pattern generator like WFC can be trusted for properties that hold locally, such as "everything is connected," but the moment you demand a global invariant like "there's exactly one key," adding evolutionary search on top is still walking a tightrope. Our own catalog has TUNIC, a game that turns Zelda-style exploration itself into a puzzle — and the value of a hand-built dungeon, where the key and door never fall out of sync, reads as the flip side of the limits this paper documents in machine generation.TUNIC (TUNIC Team, 2022), via its Steam store page

Why Is a Puzzle About Stacking and Merging Same-Colored Blocks Mathematically Proven to Be "Hard"? — The Computational Complexity of Hexasort (TU Wien)

The short answer: no matter how far you strip down the board, even restricting it to a single color, the problem of deciding whether the puzzle is solvable stays NP-hard. Linus Klocker, of the Algorithms and Complexity Group at TU Wien (Vienna University of Technology) in Austria, has posted a paper on arXiv (2603.01244, March 2026) analyzing the solvability of the mobile puzzle Hexasort.

The paper opens with this line: "Many popular puzzle and matching games have been analyzed through the lens of computational complexity. Prominent examples include Sudoku, Candy Crush, and Flood-It. A common theme among these widely played games is that their generalized decision versions are NP-hard, which is often thought of as a source of their inherent difficulty and addictive appeal to human players." Hexasort places colored stacks, one at a time, onto the vertices of a graph — in the actual game, the cells of a hexagonal board. Adjacent stacks of the same color merge automatically, and once a merged stack reaches a certain height, it vanishes. There are two goal variants: "Empty," which clears the whole board, and "Fitting," which just requires placing every piece without running out of room.

Klocker shows that even restricted to a single color, and with the board's shape squeezed down further and further — down to trees with a bounded height or a bounded degree at each vertex — deciding whether a given Hexasort puzzle is solvable stays NP-hard. The proof reduces from the classic 3-Partition problem, which asks whether a set of numbers can be split into equal-sum groups of three, and it goes further to show strong NP-hardness, meaning the difficulty doesn't disappear even when the numbers involved are kept polynomially bounded.

The paper also maps out where things get easier. Fixing the number of colors and the merge threshold as parameters, it shows some cases become solvable in polynomial time via dynamic programming, and it presents concrete algorithms for those cases. Our own mechanics glossary includes Sokoban-style pushing, a mechanic with its own history of being examined through this same computational-complexity lens to explain why it feels hard — and the Hexasort result reads as one more entry in that lineage.

The takeaway: even a single simple rule — same colors merge and vanish — stays NP-hard to solve even when you strip the board down to a tree and restrict it to one color. The paper suggests that the inescapable difficulty born from combining a few simple rules is itself part of the explanation for why this kind of puzzle feels so hard to put down.

Today's Quote

"A common theme among these widely played games is that their generalized decision versions are NP-hard, which is often thought of as a source of their inherent difficulty and addictive appeal to human players."

— from Linus Klocker, "Hexasort – The Complexity of Stacking Colors on Graphs." What struck me is how a mathematical proof doubles here as an answer to "why can't I put this puzzle down."

Closing

I'm not good at solving puzzles myself, but reading today's two papers side by side, it struck me that "the limits of the generating side" and "what difficulty actually is" seem to point at the same spot — which I found genuinely interesting as someone who dreams of designing puzzles. There's a kind of whole-board consistency that stacking local rules alone can't protect, and, the flip side, stacking local rules alone is exactly what produces an inescapable kind of difficulty. Neither is something a single designer can fully tame by hand-tuning alone, which is exactly why a carefully hand-built board still has value. See you again tomorrow.

Sources

Articles covered today:

・Evolutionary Wave Function Collapse (Dipika Rajesh, Ahmed Khalifa, Julian Togelius; arXiv, July 2026; presented in the Procedural Content Generation session at IEEE CoG 2026)

・IEEE CoG 2026 Conference Schedule (held September 1-4, 2026, Madrid)

・Hexasort – The Complexity of Stacking Colors on Graphs (Linus Klocker, TU Wien; arXiv, March 2026)