# Numberlink

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Numberlink
> Markdown URL: https://mediated.wiki/source/Numberlink.md
> Source: https://en.wikipedia.org/wiki/Numberlink
> Source revision: 1302660567
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Logic puzzle}}
{{CS1 config|mode=cs1}}
{{multiple image
| align     = right
| direction = vertical
| header    = 
| header_align = 
| header_background = 
| footer    = 
| footer_align = 
| footer_background = 
| width     = 200
| background color =

| image1    = Numberlink puzzle.svg
| width1    = 
| alt1      = 
| caption1  = A simple example of a Numberlink puzzle

| image2    = Numberlink puzzle solution.svg
| width2    = 
| alt2      = 
| caption2  = Solution to the Numberlink puzzle

}}

'''Numberlink''' is a type of [logic puzzle](/source/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<ref>{{cite magazine |title=Dr. Sudoku Prescribes: Numberlink Puzzles |url=https://www.wired.com/magazine/2010/11/dr-sudoku-prescribes-numberlink-puzzles-2/ |accessdate=November 23, 2010 |author=Thomas Snyder |author-link=Thomas Snyder |magazine=Wired |date=19 November 2010}}</ref> and all the cells in the grid are filled, although some Numberlink designers do not stipulate this.<ref name=add/>

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.<ref name=add/>

==History==
In 1897, a slightly different form of the puzzle was printed in the ''Brooklyn Daily Eagle'', in a column by [Sam Loyd](/source/Sam_Loyd).<ref>{{cite journal|last=Pegg Jr.|first=Ed|title=Beyond Sudoku|journal=Mathematica Journal|year=2007|volume=10|issue=3|pages=469–73|url=http://www.mathematica-journal.com/issue/v10i3/contents/NumberLink/NumberLink.pdf|accessdate=11 September 2011|archive-url=https://web.archive.org/web/20160303172350/http://www.mathematica-journal.com/issue/v10i3/contents/NumberLink/NumberLink.pdf|archive-date=3 March 2016|url-status=dead}}</ref> Another early, printed version of ''Number Link'' can be found in [Henry Ernest Dudeney](/source/Henry_Ernest_Dudeney)'s book ''Amusements in mathematics'' (1917) as ''a puzzle for motorists'' (puzzle no. 252).<ref name="Dudeney 1917">{{cite book|  last=Dudeney| first=Henry|title=Amusements in mathematics| publisher=Thomas Nelson|year=1917|contribution=Problem 252 – A Puzzle for Motorists|contribution-url=https://archive.org/stream/amusementsinmath00dude#page/72/mode/2up}}</ref> This puzzle type was popularized in Japan by [Nikoli](/source/Nikoli_(publisher)) 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](/source/Flow_Free) and Alphabet Connection have been released as apps for [iOS](/source/iOS), [Android](/source/Android_(operating_system)), [Web](/source/World_Wide_Web) and [Windows Phone](/source/Windows_Phone).<ref>{{cite web|url=https://itunes.apple.com/us/app/wire-storm/id588938206?ls=1&mt=8|archiveurl=https://archive.today/20130620060335/https://itunes.apple.com/us/app/wire-storm/id588938206?ls=1&mt=8|url-status=dead|title=Wire Storm - Fun and Addicting Logic Flow Puzzle Game for bigst4t22,…|date=20 June 2013|archivedate=20 June 2013|website=Archive.today|accessdate=22 November 2018}}</ref><ref>{{cite web|url=https://apps.apple.com/us/app/flow-free/id526641427|title=Flow Free|website=App Store|access-date=22 November 2018}}</ref><ref>{{cite web|url=https://play.google.com/store/apps/details?id=com.bigduckgames.flow|title=Flow Free - Apps on Google Play|website=Play.google.com|accessdate=22 November 2018}}</ref><ref>{{Cite web |url=https://itunes.apple.com/us/app/alphabet-connection-arukone/id560852073?mt=8 |title=Alphabet Connection: Arukone on the App Store on iTunes |website=[iTunes](/source/iTunes) |access-date=2015-03-17 |archive-url=https://web.archive.org/web/20150322225047/https://itunes.apple.com/us/app/alphabet-connection-arukone/id560852073?mt=8 |archive-date=2015-03-22 |url-status=dead }}</ref><ref>{{Cite web |url=https://play.google.com/store/apps/details?id=com.skyler.konekt.android |title=Archived copy |access-date=2013-10-29 |archive-url=https://web.archive.org/web/20150407164111/https://play.google.com/store/apps/details?id=com.skyler.konekt.android |archive-date=2015-04-07 |url-status=dead }}</ref><ref>{{cite web|url=https://flowfree-game.com/|title=Flow Free Game|website=Flow Free Game|accessdate=27 March 2025}}</ref><ref>{{cite web|url=https://www.microsoft.com/en-gb/store/p/flow-free/9wzdncrfj3hr|title=Get Flow Free - Microsoft Store en-GB|website=Microsoft Store|accessdate=22 November 2018}}</ref>

==Computational complexity==
As a [computational problem](/source/computational_problem), finding a solution to a given Numberlink puzzle is [NP-complete](/source/NP-complete), for the versions in which the problem is only to connect all of the pairs of numbers,<ref>{{cite journal
 | last = Lynch | first = James F.
 | date = September 1975
 | doi = 10.1145/1061425.1061430
 | issue = 3
 | journal = ACM SIGDA Newsletter
 | pages = 31–36
 | title = The equivalence of theorem proving and the interconnection problem
 | volume = 5}}</ref><ref>{{cite report
 | last1 = Kramer | first1 = Mark R.
 | last2 = van Leeuwen | first2 = Jan | author2-link = Jan van Leeuwen
 | publisher = University of Utrecht
 | type = Technical report
 | title = Wire-routing is NP-complete
 | url = https://ics-archive.science.uu.nl/research/techreps/repo/CS-1982/1982-04.pdf
 | year = 1982}}</ref> for paths without U-turns that must cover all squares of the grid,<ref>
{{cite journal
 | last1 = Kotsuma
 | first1 = Kouichi
 | last2 = Takenaga
 | first2 = Yasuhiko
 | date= March 2010
 | issue = 465
 | journal = IEICE Technical Reports in Theoretical Foundations of Computing
 | pages = 1–7
 | title = NP-Completeness and Enumeration of Number Link Puzzle
 | volume = 109
 | url = http://ci.nii.ac.jp/naid/110008000705}}</ref> and for the "zig-zag" version in which all squares must be covered but U-turns are allowed.<ref name=add>{{cite journal
| last1 = Adcock
| first1 = Aaron
| last2 = Demaine
| first2 = Erik D.
| last3 = Demaine
| first3 = Martin L
| last4 = O’Brien
| first4 = Michael P.
| last5 = Villaamil
| first5 = Fernando S{\'a}nchez
| last6 = D. Sullivan
| first6 = Blair
| title = Zig-Zag Numberlink is NP-Complete
| journal = Journal of Information Processing
| volume = 23
| issue = 3
| pages = 239–245
|date=October 23, 2014
| doi = 10.2197/ipsjjip.23.239
| arxiv = 1410.5845
| s2cid = 15735280
| url = https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_239/_article}}</ref>

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](/source/polynomial_time) as an instance of the vertex-disjoint paths problem on undirected graphs.<ref>{{cite journal
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1006/jctb.1995.1006
 | issue = 1
 | journal = [Journal of Combinatorial Theory, Series B](/source/Journal_of_Combinatorial_Theory%2C_Series_B)
 | mr = 1309358
 | pages = 65–110
 | title = Graph minors XIII: The disjoint paths problem
 | volume = 63
 | year = 1995}}</ref>

==See also==
*[List of Nikoli puzzle types](/source/List_of_Nikoli_puzzle_types)

==References==
{{Reflist}}

==External links==
*[http://connection.ivank.net Online version of ''Numberlink'' in HTML5]

Category:Logic puzzles
Category:NP-complete problems

---
Adapted from the Wikipedia article [Numberlink](https://en.wikipedia.org/wiki/Numberlink) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Numberlink?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.