Jump to content

Shakashaka

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by JanSuchy (talk | contribs) at 11:28, 27 February 2021 (+author-link = Erik Demaine). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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] The objective is to fill the white squares in a given grid with a pattern of triangles such that each white area in the resulting grid has a rectangular shape. Furthermore, each black square in the grid marked with a number must be orthogonally adjacent to the specified number of 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 14 August 2014.
  2. ^ "Rules of Shakashaka puzzle". Nikoli. Retrieved 14 August 2014.
  3. ^ a b 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


Stub icon

This game-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Shakashaka&oldid=1009220282"