Community hub
0 subscribers8 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Shakashaka.
Nothing was collected or created yet.
Shakashaka
View on Wikipediafrom Wikipedia
An example Shakashaka puzzle
The same puzzle with solution marked in teal
Shakashaka (シャカシャカ) is a logic puzzle developed by publisher Nikoli.[1]
Rules
[edit]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, not sharing an edge with other white squares/rectangles.
- Black cells with a number must be orthogonally adjacent to the specified number of black triangles.[2]
Computational complexity
[edit]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
[edit]- ^ "Puzzles of nikoli.com". Nikoli. Archived from the original on 8 November 2019. Retrieved 18 August 2021.
- ^ "Rules of Shakashaka puzzle". Nikoli. Archived from the original on 3 December 2020. Retrieved 18 August 2021.
- ^ 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
 | This puzzle/logic game-related article is a stub. You can help Wikipedia by adding missing information. |