Shakashaka

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

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

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. 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.