Goishi_Hiroi
碁石拾とも呼ばれる碁石拾は、ペグソリテールの日本版です。その中で、ペグ（または囲碁ボード上の石）は一定のパターンで配置されており、プレーヤーはすべてのペグまたは石を1つずつ拾う必要が一部のバリエーションでは、最初の石の選択が固定されていますが、他のバリエーションでは、プレーヤーは最初の石を自由に選択できます。最初の石の後、取り除かれる各石は、前に取り除かれた石からの垂直線または水平線に沿って次の占有位置から取り出されなければなりません。さらに、線に沿って方向を逆にすることはできません。ある位置から次の位置への各ステップは、前のステップと同じ方向に進むか、直角に曲がる必要が前のステップから。
これらのパズルは14世紀の日本でバーベットに使用され、それらのコレクションは1727年から日本のパズルブックに掲載されました。
与えられたパズルを解くことができるかどうかを決定することはNP完全です。これは、3満足度からの多対一還元、または密接に関連するハミルトン閉路問題からの倹約的な還元のいずれかによって証明できます。
参考文献
^ Andersson、Daniel（2007）、 “HIROIMONO Is NP-Complete”、in Crescenzi、Pierluigi; Prencipe、Giuseppe; Pucci、Geppino（eds。）、Fun with Algorithms：4th International Conference、FUN 2007、Castiglioncello、Italy、June 3-5、2007、Proceedings、Lecture Notes in Computer Science、vol。4475、Springer、pp。30–39、doi：10.1007 / 978-3-540-72914-3_5、ISBN 978-3-540-72913-6 ^ Costello、Matthew J.（1988）、史上最高のパズル、数学と論理のパズル、暗号化と単語のレクリエーションに関するドーバーの本、Courier Corporation、pp。9–10、ISBN 9780486292250 ^ タガヤ、K。（1727）、倭国千恵倉部 。福井・末次・鈴木（2017）が引用。
^ 福井正典; 末次、コキ; 鈴木晃（2017）「「碁石拾」の複雑さ」 “、第20回離散計算幾何学、グラフ、ゲームに関する日本会議の要約（JCDCG³2017） （PDF） 、 pp。142–143、2017-09-12にオリジナル （PDF）からアーカイブ、2017-09を取得-11