Shakashaka on:
[Wikipedia]
[Google]
[Amazon]
is a
In the resulting grid,
* The white parts of the grid (uncovered by black triangles) must form a rectangle or a square.
* Black cells with a number must be orthogonally adjacent to the specified number of black triangles.
logic puzzle
A logic puzzle is a puzzle deriving from the mathematical 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 W ...
developed by publisher Nikoli.
Rules
Shakashaka is played on a rectangular grid of white and black squares. Some black cells may contain a number. The objective of the puzzle is to place triangles in some of the white cells. There are four kinds of triangles which can be put in squares:
In the resulting grid,
* The white parts of the grid (uncovered by black triangles) must form a rectangle or a square.
* Black cells with a number must be orthogonally adjacent to the specified number of black triangles.
Computational complexity
It isNP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
to decide whether a given Shakashaka puzzle has a solution.
Furthermore, counting the number of solutions to a given Shakashaka puzzle is #P-complete.
References
Logic puzzles NP-complete problems {{game-stub