Heyawake
Shade rooms according to their clues without isolating unshaded cells or leaving long straight corridors.
Basic Game Premise & Rules
MechanicsHeyawake is an untimed, deterministic pencil-and-paper logic puzzle played on a grid. Every valid puzzle has exactly one unique solution that can be discovered through rigorous deductive reasoning alone, without trial and error or guessing.
- The grid is partitioned into rectangular or polyomino rooms by bold borders.
- Shade some cells black; the remaining cells stay white.
- Room Clues: A number in a room specifies exactly how many cells in that room are shaded black. Rooms without numbers may have any count of shaded cells.
- No Adjacent Shading: Shaded cells can never touch along an edge (orthogonally), though they may touch diagonally at corners.
- Connected White Space: All unshaded (white) cells must remain connected into a single orthogonal territory—no white cell may be cut off or isolated.
- Two-Room Corridor Restriction: An unbroken straight orthogonal line of white cells cannot span across more than two rooms (a white line entering a room and passing completely through it cannot enter a third room).
Rules by Example
See how each rule looks when done correctly versus when violated:
Room Clues & No Adjacent Shaded Cells
A number in a room specifies exactly how many of its cells are shaded. Shaded cells can never touch along a side (orthogonally), though touching at a corner is allowed.
The Two-Room White Line Rule
A continuous straight line of unshaded (white) cells cannot pass through more than two rooms (horizontally or vertically). It must be interrupted by a shaded cell.
White Cell Connectivity
All white (unshaded) cells must form a single connected group. Shaded cells cannot wall off or isolate any white cell.
History & Origins
Origins & EvolutionHeyawake was invented by Nikoli and made its debut in *Puzzle Communication Nikoli* #39 in 1992. Its Japanese title *Heyawake* (へやわけ) translates directly to 'Dividing Rooms' or 'Room Division'.
It quickly earned a reputation among pencil puzzle connoisseurs as one of Nikoli's most elegant and intellectually demanding inventions, standing alongside Nurikabe and Slitherlink. What distinguishes Heyawake is the intricate interplay between its local constraints (room counts and non-adjacent shading) and its subtle global rules (white cell connectedness and the strict two-room corridor restriction). A single shaded cell placed in one corner can trigger a cascade of room-crossing deductions across the entire board.
Mathematical Concepts & Computational Complexity
Computer Science & Discrete MathBeyond its entertainment value, Heyawake formalizes core principles of discrete mathematics, theoretical computer science, and combinatorics:
Independent Sets on Grid Graphs
The requirement that no two shaded cells share an orthogonal edge is identical to finding an Independent Set (or Stable Set) in the grid graph G = (V, E). In an m × n grid, the maximum independent set is ⌈mn / 2⌉ (a checkerboard pattern). Room constraints impose local capacity bounds |I ∩ R_k| = c_k, forcing the independent set to conform to regional quotas.
Computational Complexity: NP-Complete & ASP-Complete
In 2004, Markus Holzer, Pierre McKenzie, and Patrick Traxler published a seminal paper (*The Computational Complexity of Heyawake*) in *Lecture Notes in Computer Science* (SOFSEM 2005) proving that Heyawake is NP-complete via a reduction from 3-SAT. They further showed that determining whether a Heyawake puzzle has another solution (ASP) is ASP-complete. Even when all rooms are restricted to 2×2 or 1×k rectangles, the problem remains NP-complete.
Percolation & Bounded Corridor Cuts
The two-room corridor rule acts as a global anti-percolation constraint: no straight white path can intersect the boundaries of three distinct rooms. For any horizontal or vertical line segment L intersecting rooms R_1, R_2, R_3 in order, the set of cells in L must contain at least one shaded cell. This breaks infinite-range percolation and forces a fractal-like distribution of black cells throughout the grid.
SAT Encoding & Graph Connectivity Formulations
Encoding Heyawake into CNF SAT involves: (1) Vertex independence clauses (¬b_u ∨ ¬b_v) for adjacent cells; (2) Exact-k cardinality networks for numbered rooms; (3) Anti-corridor clauses (⋁_{c ∈ L} b_c) for all segments spanning 3 rooms; and (4) White connectivity, encoded via potential-flow networks or inductive tree parent pointers. These multi-level constraints make Heyawake an ideal benchmark for state-of-the-art CSP and SAT solvers.
References & Further Reading
Bibliography- Holzer, M., McKenzie, P., & Traxler, P. (2004). 'The Computational Complexity of Heyawake'. Lecture Notes in Computer Science, Vol. 3340 (SOFSEM 2005), 184–193. Springer.
- Nikoli (1992). Puzzle Communication Nikoli #39. Tokyo: Nikoli Publishing.
- Demaine, E. D., & Hearn, R. A. (2008). 'Playing Games with Algorithms: Algorithmic Combinatorial Game Theory'. arXiv:0806.0778.
- Seta, T. (2002). 'The Complexity of Several Japanese Pencil Puzzles'. Symposium on Algorithms and Computation (ISAAC).
- Hearn, R. A. (2006). 'Games, Puzzles, and Computation'. PhD Thesis, Massachusetts Institute of Technology.
Free Printable PDF Booklet
Download our beautifully formatted, high-resolution A4 puzzle booklet. Generated directly from the handcrafted levels on AZTest, it contains 50 puzzles ordered from gentle introductory boards up to master-level challenges, followed by complete solutions at the back.
| Difficulty Stage | Grid Size | Description | Puzzles |
|---|---|---|---|
| Intro | 5×5 | Small rooms introducing non-touching black cells and connectivity. | 3 |
| Easy | 5×5 to 6×6 | Room clue deductions and simple corridor blocking. | 12 |
| Medium | 7×7 to 8×8 | Multi-room corridor tracking and white walling avoidance. | 12 |
| Hard | 8×8 to 9×9 | Complex checkerboard parity and 3-room line cuts. | 12 |
| Expert | 9×9 to 10×10 | Intricate architectural layouts demanding comprehensive global analysis. | 11 |
Explore More Logic Puzzles
SeriesSlitherlink
Connect dots to draw a single unbroken loop guided by surrounding cell numbers.
Wolves & Sheep
Draw a Slitherlink loop that fences the gentle sheep in and keeps the fierce wolves out.
Masyu
Draw one closed loop through cell centres that rigorously obeys the black and white pearls.
Nurikabe
Shade the sea to leave numbered white islands of exact sizes in one connected ocean.
Nonogram
Shade runs of cells according to row and column number clues to reveal a hidden picture.
Themed Nonogram
Solve color picture cross puzzles that blossom into vibrant pixel art upon completion.
Hitori
Shade the repeated numbers until every row and column has unique digits, keeping all white cells connected.
Kurodoko
Shade cells so every numbered circle sees exactly that many white cells in its row and column.
Mosaic
Shade cells guided by numbers that count how many cells around them are filled, revealing a hidden picture.
Binairo
Fill every cell with blue or white circles: never three in a row, every line half and half.
Searchlights
Place light beams in white cells so that every numbered black post sees its exact clue count.
Light Up
Place light bulbs to illuminate every white cell without any two shining on each other.
Calcudoku
A Latin square where every outlined cage satisfies its arithmetic target and operator.
Skyscrapers
Place towers of heights 1 to N so that each outside clue sees the exact count of buildings.
Sum Skyscrapers
Skyscrapers where each outside clue is the sum of the heights of all visible buildings.
Suguru
The elegant polyomino number puzzle where no two identical digits can touch, even diagonally.
Futoshiki
A Latin square puzzle with inequality signs pointing between neighboring numbers.
Fillomino
Divide the grid into polyomino blocks where each cell's number equals the area of its block.
Galaxies
Partition the grid into rotational 180° symmetric galaxies, each centered on a single dot.
Shikaku
Cut the whole grid into rectangles and squares, each containing exactly one number: its area.
L-Pieces
Draw borders to partition all white cells into perfect four-cell L-shapes.
Numberlink
Connect pairs of matching numbers with continuous non-crossing paths covering the grid.
Bridges
Connect the island network with straight horizontal and vertical bridges into one united world.
Slant
Draw a diagonal slash in every cell matching the corner numbers, without ever closing a loop.
Tents
Pitch a tent beside every tree with no two tents touching, matching row and column counts.
Marupeke
Place circles and crosses in every cell without creating three in a row in any direction.