Loading article…
シャカシャカ(シャカシャカ)は、出版社ニコリによって開発されたロジック パズルです。[1]
ルール
シャカシャカは、白と黒の正方形の長方形のグリッド上でプレイされます。一部の黒いセルには数字が含まれている場合があります。
パズルの目的は、白いセルに三角形を配置することです。正方形に配置できる三角形は 4 種類あります。
結果のグリッドでは、
- グリッドの白い部分（黒い三角形で覆われていない部分）は、長方形または正方形を形成する必要があります。
- 数字が書かれた黒いセルは、指定された数の黒い三角形と直交して隣接している必要があります。 [2]
計算の複雑さ
与えられたシャカシャカパズルに解があるかどうかを判断することはNP完全です。 [3] さらに、与えられたシャカシャカパズルの解の数を数えることは#P完全です。[3]
参考文献
- ^ 「nikoli.comのパズル」ニコリ。 2021年8月18日閲覧。
- ^ “シャカシャカパズルのルール”.ニコリ。2021 年8 月 18 日に取得。
- ^ ab Demaine, Erik D. ; 岡本 佳夫; 上原 龍平; 宇野 雄志 (2014)、「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