An eight-by-eight Shakashaka puzzle grid. Some of the spaces are pre-filled with black squares (some of which contain numbers); others are blank spaces to be filled with triangles.
An example Shakashaka puzzle
The solution to the previous puzzle.
The same puzzle with solution marked in teal

Shakashaka (シャカシャカ) is a logic puzzle developed by publisher Nikoli.[1]

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.[2]

Computational complexity

It is NP-complete to decide whether a given Shakashaka puzzle has a solution.[3] Furthermore, counting the number of solutions to a given Shakashaka puzzle is #P-complete.[3]

References

  1. ↑ "Puzzles of nikoli.com". Nikoli. Retrieved 18 August 2021.
  2. ↑ "Rules of Shakashaka puzzle". Nikoli. Retrieved 18 August 2021.
  3. 1 2 Demaine, Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Computational complexity and an integer programming model of Shakashaka", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A (6): 1213–1219, Bibcode:2014IEITF..97.1213D, doi:10.1587/transfun.E97.A.1213, hdl:10119/12147


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.