Heyawake is a binary-determination logic puzzle

Logic puzzle

A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...

 published by Nikoli

Nikoli

Nikoli Co., Ltd. is a Japanese publisher that specializes in games and, especially, logic puzzles. Nikoli is also the nickname of a quarterly magazine issued by the company...

. As of 2011, four books consisting entirely of Heyawake puzzles have been published by Nikoli. It first appeared in Puzzle Communication Nikoli #39 (September 1992).

Rules

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
  Polyomino
  A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling with a connected interior....
  
  ).
• 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.

Solution methods

Note that the first two rules also apply to (for example) Hitori

Hitori

Hitori is a type of logic puzzle published by Nikoli.-Rules:Hitori is played with a grid of squares or cells, and each cell contains a number...

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 3×3 room containing a '5' must have a checkered pattern, with painted cells in all corners and the center.

Computational complexity

The computational complexity

Computational Complexity

Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

 of Heyawake has been analyzed recently: deciding for a given instance of Heyawake whether there exists a solution to the puzzle is NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

. An interpretation of this theoretical result in layman's terms is that this puzzle is as hard to solve as the Boolean satisfiability problem

Boolean satisfiability problem

In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...

, which is a well studied difficult problem in computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

.