ナンバーリンク

ナンバーリンクパズルの簡単な例

ナンバーリンクパズルの解答

ナンバーリンクは、グリッド上の数字をつなぐ経路を見つけるタイプの論理パズルです。

プレイヤーは、グリッド上のすべての一致する数字を、一本の連続した線（または経路）でつなぐ必要があります。線は分岐したり交差したりしてはならず、数字は各線の終点に配置されなければなりません（つまり、線の途中には配置できません）。

問題が適切に設計されているとみなされるのは、一意の解が存在し^{[ 1 ]}、グリッド内のすべてのセルが埋められている場合のみであると考えられているが、Numberlinkの設計者の中にはこれを規定しない者もいる^{[ 2 ] 。}

パズルのいくつかのバージョンに含まれるもう1つのルールは、経路にUターンがあってはならないというものです。Uターンがあると、他の経路を変更せずに経路を短縮できてしまうからです。^{[ 2 ]}

1897年、このパズルの少し異なる形式が、サム・ロイドのコラムでブルックリン・デイリー・イーグル紙に掲載された。^{[ 3 ]}ナンバーリンクの別の初期の印刷版は、ヘンリー・アーネスト・デューデニーの著書『数学の娯楽』 （1917年）に自動車運転者向けのパズル（パズル番号252）として掲載されている。 ^{[ 4 ]}このタイプのパズルは、ニコリによってアルコネ（Alukone、アルファベット接続）とナンバーリンク（Nanbarinku、ナンバーリンク）として日本で普及した。アルコネとナンバリンクの唯一の違いは、アルコネではヒントが文字のペア（デューデニーのパズルと同様）であるのに対し、ナンバリンクではヒントが数字のペアであるという点である。

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

計算問題として、与えられた Numberlink パズルの解を見つけることはNP 完全です。問題がすべての数字のペアを接続することだけであるバージョン^{[ 12 ] [ 13 ]} 、 U ターンなしでグリッドのすべてのマスをカバーする必要があるパスの場合^{[ 14 ]}、およびすべてのマスをカバーする必要があるが U ターンが許可されている「ジグザグ」バージョンの場合^{[ 2 ]です。}

これらの困難性の結果は、パズルのサイズに応じて数値のペアの数を増やす必要があることを示しています。ペアの数が固定されている場合、任意の大きなグリッドでも、すべてのペアを接続する（必ずしもグリッドを埋める必要はない）ことは、無向グラフ上の頂点が互いに素なパスの問題のインスタンスとして多項式時間で解くことができます。 ^{[ 15 ]}

• ニコリパズルの種類一覧

• NumberlinkのHTML5版オンライン