ナンバーリンク

ナンバーリンクは、グリッド内の数字を結ぶパスを見つけるタイプの論理パズルです。

ルール

プレイヤーは、グリッド上の一致する数字をすべて、1 本の連続した線 (またはパス) でペアにする必要があります。線は分岐したり、交差したりすることはできず、数字は各線の端 (つまり、中央ではない) になければなりません。

問題が適切に設計されていると判断されるのは、解が一意に定まっており^[1]、グリッド内のすべてのセルが埋められている場合に限られますが、Numberlinkの設計者の中にはこれを規定していない人もいます。

歴史

1897年、わずかに異なる形式のパズルがブルックリン・デイリー・イーグル紙のサム・ロイドのコラムに掲載された。^[2]ナンバーリンクの初期の印刷版としては、ヘンリー・アーネスト・デュードニーの著書『Amusements in mathematical』(1917年)に自動車運転者向けのパズルとして掲載されている(パズル番号252)。^{[3]このタイプのパズルは}、ニコリによって「アルコネ」( Alphabet Connection ) と「ナンバリンク」( Number Link )として日本で普及した。アルコネとナンバリンクの唯一の違いは、アルコネではヒントが文字のペア(デュードニーのパズルと同じ)であるのに対し、ナンバリンクではヒントが数字のペアであるという点である。

2006 年現在^{[アップデート]}、ニコリ社からナンバーリンクパズルのみで構成された 3 冊の本が出版されています。

Wire Storm、 Flow Free 、Alphabet Connectionとして知られるこのバージョンは、iOS、Android、Windows Phone向けのアプリとしてリリースされています。^[4]^[5]^[6]^[7]^[8]^[9]

計算の複雑さ

計算問題として、与えられたナンバーリンクパズルの解法を見つけることはNP完全です。^[10] NP完全性は「ジグザグ」パスが許可されていても維持されます。非公式には、これはパスに「不必要な曲がり」がある可能性があることを意味します（より技術的な説明については参考文献を参照してください）。^[11]

参照

ニコリパズルの種類一覧

参考文献

^ Thomas Snyder (2010 年 11 月 19 日). 「Dr. Sudoku の処方箋: Numberlink パズル」. Wired . 2010 年11 月 23 日閲覧。
^ Pegg Jr., Ed (2007). 「Beyond Sudoku」（PDF） . Mathematica Journal . 10 （3）：469–73. 2016年3月3日時点のオリジナル（PDF）からアーカイブ。 2011年9月11日閲覧。
^ Dudeney, Henry (1917)。「問題 252 – 自動車運転者のためのパズル」。数学の娯楽。トーマス・ネルソン。
^ 「Wire Storm - bigst4t22 向けの楽しくて中毒性のあるロジックフローパズルゲーム…」Archive.today 2013年6月20日。2013年6月20日時点のオリジナルよりアーカイブ。 2018年11月22日閲覧。
^ 「Flow Free」。App Store 。 2018年11月22日閲覧。
^ 「Flow Free - Google Play のアプリ」。Play.google.com。2018年11 月 22 日閲覧。
^ 「Alphabet Connection: Arukone on the App Store on iTunes」。iTunes。2015年3月22日時点のオリジナルよりアーカイブ。2015年3月17日閲覧。
^ “アーカイブコピー”. 2015年4月7日時点のオリジナルよりアーカイブ。2013年10月29日閲覧。{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)
^ 「Get Flow Free - Microsoft Store en-GB」。Microsoft Store 。 2018年11月22日閲覧。
^ 幸間浩一、竹永康彦 (2010 年 3 月)、「数リンクパズルの NP 完全性と列挙」、電子情報通信学会技術研究報告。コンピューティングの理論的基礎、109 (465): 1–7
^ アーロン、アドコック;デメイン、エリック D.ディメイン、マーティン・L;オブライエン、マイケル P.ビジャミル、フェルナンド・サンチェス; D. Sullivan、Blair (2014 年 10 月 23 日)、「Zig-Zag Numberlink is NP-Complete」、Journal of Information Processing、23 (3): 239–245、arXiv : 1410.5845、doi :10.2197/ipsjjip.23.239、S2CID 15735280

外部リンク

HTML5 の Numberlink のオンライン版

[1] Thomas Snyder (2010 年 11 月 19 日). 「Dr. Sudoku の処方箋: Numberlink パズル」. Wired . 2010 年11 月 23 日閲覧。

[2] Pegg Jr., Ed (2007). 「Beyond Sudoku」（PDF） . Mathematica Journal . 10 （3）：469–73. 2016年3月3日時点のオリジナル（PDF）からアーカイブ。 2011年9月11日閲覧。

[Dudeney_1917-3] Dudeney, Henry (1917)。「問題 252 – 自動車運転者のためのパズル」。数学の娯楽。トーマス・ネルソン。

[4] 「Wire Storm - bigst4t22 向けの楽しくて中毒性のあるロジックフローパズルゲーム…」Archive.today 2013年6月20日。2013年6月20日時点のオリジナルよりアーカイブ。 2018年11月22日閲覧。

[5] 「Flow Free」。App Store 。 2018年11月22日閲覧。

[6] 「Flow Free - Google Play のアプリ」。Play.google.com。2018年11 月 22 日閲覧。

[7] 「Alphabet Connection: Arukone on the App Store on iTunes」。iTunes。2015年3月22日時点のオリジナルよりアーカイブ。2015年3月17日閲覧。

[8] “アーカイブコピー”. 2015年4月7日時点のオリジナルよりアーカイブ。2013年10月29日閲覧。{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク)

[9] 「Get Flow Free - Microsoft Store en-GB」。Microsoft Store 。 2018年11月22日閲覧。

[10] 幸間浩一、竹永康彦 (2010 年 3 月)、「数リンクパズルの NP 完全性と列挙」、電子情報通信学会技術研究報告。コンピューティングの理論的基礎、109 (465): 1–7

[11] アーロン、アドコック;デメイン、エリック D.ディメイン、マーティン・L;オブライエン、マイケル P.ビジャミル、フェルナンド・サンチェス; D. Sullivan、Blair (2014 年 10 月 23 日)、「Zig-Zag Numberlink is NP-Complete」、Journal of Information Processing、23 (3): 239–245、arXiv : 1410.5845、doi :10.2197/ipsjjip.23.239、S2CID 15735280