広井碁石

碁石ひろい（ひろいもの）は、ペグ・ソリティアの日本のバリエーションである。このゲームでは、ペグ（または碁盤上の石）が決まったパターンで配置され、プレーヤーはすべてのペグまたは石を1つずつ拾わなければならない。いくつかのバリエーションでは、最初の石の選択は固定されているが、他のバリエーションではプレーヤーは最初の石を自由に選ぶことができる。^[1] 最初の石の後、取り除かれる各石は、以前に取り除かれた石から垂直または水平の線に沿って次の占められた位置から取られなければならない。また、線に沿って方向を反転することはできません。ある位置から次の位置への各ステップは、前のステップと同じ方向に進むか、前のステップから直角に曲がる必要があります。

これらのパズルは14世紀の日本でバーベットに使用され、 ^[2] それらのコレクションは1727年の日本のパズル本に出版されました。^[3]

与えられたパズルが解けるかどうかを判断することはNP完全です。これは、 3-充足可能性からの多対一還元によって証明できます。^[1]または密接に関連するハミルトン経路問題からの簡潔な還元によって証明できます。^[4]

参考文献

^ ab Andersson, Daniel (2007)、「HIROIMONO は NP 完全である」、Crescenzi, Pierluigi、Prencipe, Giuseppe、Pucci, Geppino (編)、Fun with Algorithms: 4th International Conference、FUN 2007、Castiglioncello、イタリア、2007 年 6 月 3 ～ 5 日、議事録、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
^ コステロ、マシュー・J. (1988)、「史上最大のパズル」、数学と論理パズル、暗号と単語の再現に関するドーバーの本、クーリエ・コーポレーション、pp. 9-10、ISBN 9780486292250
^ 多賀谷和久（1727年）『倭国千枝倉部』福井・末次・鈴木（2017）より引用。
^ 福井正典;末次幸樹;鈴木章（2017）「『碁石広井』の複雑さ」"、第20回離散・計算幾何学、グラフ、ゲームに関する日本会議（JCDCG³ 2017）の抄録（PDF）、pp. 142–143、2017-09-12にオリジナル（PDF）からアーカイブ、 2017-09-11に取得

[andersson-1] Andersson, Daniel (2007)、「HIROIMONO は NP 完全である」、Crescenzi, Pierluigi、Prencipe, Giuseppe、Pucci, Geppino (編)、Fun with Algorithms: 4th International Conference、FUN 2007、Castiglioncello、イタリア、2007 年 6 月 3 ～ 5 日、議事録、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

[2] コステロ、マシュー・J. (1988)、「史上最大のパズル」、数学と論理パズル、暗号と単語の再現に関するドーバーの本、クーリエ・コーポレーション、pp. 9-10、ISBN 9780486292250

[3] 多賀谷和久（1727年）『倭国千枝倉部』福井・末次・鈴木（2017）より引用。

[4] 福井正典;末次幸樹;鈴木章（2017）「『碁石広井』の複雑さ」"、第20回離散・計算幾何学、グラフ、ゲームに関する日本会議（JCDCG³ 2017）の抄録（PDF）、pp. 142–143、2017-09-12にオリジナル（PDF）からアーカイブ、 2017-09-11に取得