Heyawake

Heyawake is played on a rectangular grid of cells with no standard size; the grid is divided into variously sized rectangular "rooms" by bold lines following the edges of the cells. Some rooms may contain a single number, typically printed in their upper-left cell; as originally designed, every room was numbered, but this is rarely necessary for solving and is no longer followed.

Some of the cells in the puzzle are to be painted black; the object of the puzzle is to determine for each cell if it must be painted or must be left blank (remaining white). In practice, it is often easier to mark known "blank" cells in some way—for example, by placing a dot in the center of the cell.

The following rules determine which cells are which:

• Rule 1: Painted cells may never be orthogonally connected (they may not share a side, although they can touch diagonally).
• Rule 2: All white cells must be interconnected (form a single polyomino).
• Rule 3: A number indicates exactly how many painted cells there must be in that particular room.
• Rule 4: A room which has no number may contain any number of painted cells, or none.
• Rule 5: Where a straight (orthogonal) line of connected white cells is formed, it must not contain cells from more than two rooms—in other words, any such line of white cells which connects three or more rooms is forbidden.

Note that the first two rules also apply to (for example) Hitori puzzles, and thus these puzzles share some of their solving methods:

• If it is discovered that a cell is painted, it is immediately known that all of the four (orthogonally) adjacent cells must be white (from Rule 1).
• A section of (orthogonally) contiguous white cells cannot be cut off from the rest of the grid (from Rule 2). Black cells may not form a diagonal split across the grid nor a closed loop; any cell that would complete such a "short circuit" must be white instead.

More complex puzzles require combining Rule 1 and Rule 2 to make progress without guessing; the key is recognizing where the cells must assume one of two checkered patterns and one leads to a short circuit.

The remaining rules differentiate Heyawake from other "dynasty" puzzles:

• Rule 5 is the defining rule of the puzzle; black cells must be placed to prevent any (orthogonal) lines of white cells that cross two room borders ("spanners").
• Numbered rooms typically provide solvers a starting place, among other deductions. The following are the simplest examples of rooms defined at the onset:
  • A 2×2 room in the corner of the grid containing a '2' must have one painted cell in the grid corner and the second painted square diagonally outward from the corner. As painted squares may not share a side (Rule 1), the only alternative would disconnect the forced white cell in the corner, violating Rule 2.
  • A 2×3 room with the 3-cell side along a grid border containing a '3' must have a painted cell in the center of the 3-cell side along the border and the other two in the opposite corners of the room, for similar reasons to the above.
  • A 1×3 room containing a '2' must have the two end cells painted, as a painted centre cell would force a breach of rule 1. More generally, a 1×(2n−1) room containing an n must have every other cell within it painted.
  • A 3×3 room containing a '5' must have a checkered pattern, with painted cells in all corners and the center.

• Heyawacky is played like Heyawake, but rooms are not necessarily rectangular. Orthogonal lines of white cells may not exit and re-enter a room; i.e. such lines may not straddle more than one region boundary.
• Symmetry Heyawake is played like Heyawake, but clues indicate whether the pattern of black cells in a room is rotationally symmetric around its centre or not.

The computational complexity of Heyawake has been analyzed:[1] deciding for a given instance of Heyawake whether there exists a solution to the puzzle is NP-complete. An interpretation of this theoretical result in layman's terms is that this puzzle is as hard to solve as the Boolean satisfiability problem, which is a well studied difficult problem in computer science.

List of Nikoli puzzle types

• Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake" (PDF). Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.

• Nikoli's page on Heyawake