Введение

Логическая головоломка Numberlink — это тип логической головоломки, в которой нужно найти пути для соединения одинаковых чисел в сетке.

Правила

Игрок должен соединить все одинаковые числа на игровом поле непрерывными линиями (или путями). Линии не должны разветвляться или пересекаться, а числа должны находиться на концах каждой линии (то есть не в середине). Задача считается хорошо спроектированной, только если у неё есть единственное решение и все ячейки игрового поля заполнены, хотя некоторые дизайнеры Numberlink не требуют этого.

История

В 1897 году несколько иная версия головоломки была опубликована в газете Brooklyn Daily Eagle в колонке Сэма Лойда. Другая ранняя печатная версия Number Link встречается в книге Генри Эрнеста Дюденея «Amusements in mathematics» (1917) в качестве головоломки для автомобилистов (головоломка № 252). Этот тип головоломки получила распространение в Японии благодаря компании Nikoli под названиями Аруконе (アルコネ, Alphabet Connection) и Нанбаринку (ナンバーリンク, Number Link). Единственное отличие между Аруконе и Нанбаринку заключается в том, что в Аруконе в качестве подсказок используются пары букв (как в головоломке Дюденея), а в Нанбаринку – пары чисел. По состоянию на 2006 год компания Nikoli опубликовала три книги, полностью состоящие из головоломок Numberlink. Версии этой головоломки, известные как Wire Storm, Flow Free и Alphabet Connection, были выпущены в виде приложений для iOS, Android и Windows Phone.

Комплексность вычислений

Как вычислительная задача, поиск решения головоломки Numberlink является NP-полной. NP-полнота сохраняется даже при разрешении "зигзагообразных" путей. Неформально это означает, что пути могут содержать "лишние изгибы" (см. ссылку для более подробного технического объяснения).