Numberlink is a type of
logic puzzle
A logic puzzle is a puzzle deriving from the mathematical field of deduction.
History
The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of ''Alice's Adventures in W ...
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.
History
In 1897, a slightly different form of the puzzle was printed in the ''Brooklyn Daily Eagle'', in a column by
Sam Loyd
Samuel Loyd (January 30, 1841 – April 10, 1911), was an American chess player, chess composer, puzzle author, and recreational mathematician. Loyd was born in Philadelphia but raised in New York City.
As a chess composer, he authored a numb ...
. 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.
, three books consisting entirely of Numberlink puzzles have been published by Nikoli.
Versions of this known as Wire Storm, Flow Free and Alphabet Connection have been released as apps for
iOS
iOS (formerly iPhone OS) is a mobile operating system created and developed by Apple Inc. exclusively for its hardware. It is the operating system that powers many of the company's mobile devices, including the iPhone; the term also include ...
,
Android and
Windows Phone
Windows Phone (WP) is a discontinued family of mobile operating systems developed by Microsoft for smartphones as the replacement successor to Windows Mobile and Zune. Windows Phone featured a new user interface derived from the Metro design l ...
.
Computational complexity
As a
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
, finding a solution to a given Numberlink puzzle is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
.
NP-completeness is maintained even if "zig-zag" paths are allowed. Informally, this means paths may have "unnecessary bends" in them (see the reference for a more technical explanation).
[
]
See also
*
List of Nikoli puzzle types is a Japanese publisher that specializes in games and, especially, logic puzzles. ''Nikoli'' is also the nickname of a quarterly magazine (whose full name is ''Puzzle Communication Nikoli'') issued by the company in Tokyo. ''Nikoli'' was establish ...
References
{{Reflist
External links
Nikoli's English page on ''Numberlink''Online version of ''Numberlink'' in HTML5
Logic puzzles