Numberlink

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid.

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid.

Rules

The player has to pair up all the matching numbers on the grid with single continuous lines (or paths). The lines cannot branch off or cross over each other, and the numbers have to fall at the end of each line (i.e., not in the middle). It is considered that a problem is well-designed only if it has a unique solution and all the cells in the grid are filled, although some Numberlink designers do not stipulate this. Another rule that is included in some versions of the puzzle is that a path cannot have any U-turns, as these would allow it to be shortened without changing the other paths.

History

In 1897, a slightly different form of the puzzle was printed in the Brooklyn Daily Eagle, in a column by Sam Loyd. Another early, printed version of Number Link can be found in Henry Ernest Dudeney's book Amusements in mathematics (1917) as a puzzle for motorists (puzzle no. 252). This puzzle type was popularized in Japan by Nikoli as Arukone (アルコネ, Alphabet Connection) and Nanbarinku (ナンバーリンク, Number Link). The only difference between Arukone and Nanbarinku is that in Arukone the clues are letter pairs (as in Dudeney's puzzle), while in Nanbarinku the clues are number pairs. Versions of this known as Wire Storm, Flow Free and Alphabet Connection have been released as apps for iOS, Android, Web and Windows Phone.

Computational complexity

As a computational problem, finding a solution to a given Numberlink puzzle is NP-complete, for the versions in which the problem is only to connect all of the pairs of numbers, for paths without U-turns that must cover all squares of the grid, and for the "zig-zag" version in which all squares must be covered but U-turns are allowed. These hardness results require the number of pairs of numbers to grow with the size of the puzzle. For fixed numbers of pairs, even on arbitrarily large grids, connecting all pairs (without necessarily filling the grid) can be solved in polynomial time as an instance of the vertex-disjoint paths problem on undirected graphs.

See also

List of Nikoli puzzle types

References

External links

Online version of Numberlink in HTML5

Text derived from https://en.wikipedia.org/w/index.php?oldid=1359655947 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

14 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.