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: ... okay, fine, just compile, though to bytecode or something rather than machine code.
gollark: <@!426660245738356738> `load` and `loadstring` both just "compile" code from a supplied string, but take mildly different arguments.
gollark: `shell.run`/`dofile`/`os.run` use load(string) internally *anyway*, you see.
gollark: As has been said, the best way to execute user supplied code if you need to for some reason is `load`/`loadstring`. With environment meddling it can even be sandboxed a bit.
gollark: <@426660245738356738> Writing it to a file and executing it is slower and stupider than using load/loadstring. Please do not do that.

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.