Shakashaka

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]

An example Shakashaka puzzle
The same puzzle with solution marked in teal

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]

gollark: mediawiki: php, requires "database" (although it does support SQLite I guess), quite large and complex.
gollark: dokuwiki NOT bad, dokuwiki LACKING BIZARRE FEATURES WHICH ARE SOMEWHAT BEES
gollark: As well as more accurate.
gollark: PotatoWiki... I mean, the documentation is all in the code and it's more fun that way.
gollark: Every random service I add creates some extra maintenence work for me.

References
  1. "Puzzles of nikoli.com". Nikoli. Retrieved 14 August 2014.
  2. "Rules of Shakashaka puzzle". Nikoli. Retrieved 14 August 2014.
  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, 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.