Numberlink is a type of
logic puzzle
A logic puzzle is a puzzle deriving from the mathematics, mathematical field of deductive reasoning, deduction.
History
The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the a ...
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
Samuel Loyd (January 30, 1841 – April 10, 1911) was an American chess player, chess composer, puzzle author, and recreational mathematics, recreational mathematician. Loyd was born in Philadelphia but raised in New York City.
As a chess comp ...
. 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).iOS
Ios, Io or Nio (, ; ; locally Nios, Νιός) is a Greek island in the Cyclades group in the Aegean Sea. Ios is a hilly island with cliffs down to the sea on most sides. It is situated halfway between Naxos and Santorini. It is about long an ...
, Android, Web
Web most often refers to:
* Spider web, a silken structure created by the animal
* World Wide Web or the Web, an Internet-based hypertext system
Web, WEB, or the Web may also refer to:
Computing
* WEB, a literate programming system created by ...
and Windows Phone
Windows Phone (WP) is a discontinued mobile operating system developed by Microsoft Mobile for smartphones as the replacement successor to Windows Mobile and Zune. Windows Phone featured a new user interface derived from the Metro design languag ...
.
Computational complexity
As a computational problem
In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computati ...
, finding a solution to a given Numberlink puzzle is NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
, 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.polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
as an instance of the vertex-disjoint paths problem on undirected graphs.
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 establi ...
References
{{Reflist
External links
Online version of ''Numberlink'' in HTML5
Logic puzzles
NP-complete problems