Номерная ссылка
Numberlink — это тип логической головоломки , в которой нужно найти пути для соединения чисел в сетке.
Правила
[ редактировать ]Игрок должен соединить все совпадающие числа в сетке в отдельные непрерывные линии (или пути). Линии не могут ответвляться или пересекаться друг с другом, а числа должны располагаться в конце каждой строки (т. е. не в середине).
Считается, что задача хорошо разработана только в том случае, если она имеет единственное решение. [1] и все ячейки сетки заполнены, хотя некоторые дизайнеры Numberlink этого не оговаривают.
История
[ редактировать ]В 1897 году немного другая форма головоломки была напечатана в Brooklyn Daily Eagle , в колонке Сэма Лойда . [2] Еще одну раннюю печатную версию Number Link можно найти в Генри Эрнеста Дьюдени книге «Математические развлечения» (1917) как головоломку для автомобилистов (головоломка № 252). [3] Этот тип головоломок был популяризирован в Японии Николи как Аруконе (アルコネ, Alphabet Connection ) и Нанбаринку (ナンバーリンク, Number Link ). Единственная разница между Аруконе и Нанбаринку состоит в том, что в Аруконе подсказками являются пары букв (как в головоломке Дудени), а в Нанбаринку подсказками являются пары чисел.
По состоянию на 2006 год [update]Николи опубликовал три книги, полностью состоящие из головоломок Numberlink.
Версии этого приложения, известные как Wire Storm, Flow Free и Alphabet Connection, были выпущены в виде приложений для iOS , Android и Windows Phone . [4] [5] [6] [7] [8] [9]
Вычислительная сложность
[ редактировать ]В качестве вычислительной задачи поиск решения данной головоломки Numberlink является NP-полной . [10] NP-полнота сохраняется, даже если разрешены «зигзагообразные» пути. Неформально это означает, что пути могут иметь «ненужные изгибы» (более техническое объяснение см. в ссылке). [11]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Томас Снайдер (19 ноября 2010 г.). «Доктор судоку предписывает: головоломки с числовыми связями» . Проводной . Проверено 23 ноября 2010 г.
- ^ Пегг-младший, Эд (2007). «За пределами судоку» (PDF) . Журнал Математика . 10 (3): 469–73. Архивировано из оригинала (PDF) 3 марта 2016 года . Проверено 11 сентября 2011 г.
- ^ Дудени, Генри (1917). «Задача 252 — Головоломка для автомобилистов» . Забавы по математике . Томас Нельсон.
- ^ «Wire Storm — веселая и увлекательная логическая игра-головоломка для bigst4t22,…» . Архив.сегодня . 20 июня 2013 года. Архивировано из оригинала 20 июня 2013 года . Проверено 22 ноября 2018 г.
- ^ «Свободный поток» . Магазин приложений . Проверено 22 ноября 2018 г.
- ^ «Flow Free – Приложения в Google Play» . Play.google.com . Проверено 22 ноября 2018 г.
- ^ «Alphabet Connection: Arukone в App Store в iTunes» . Айтюнс . Архивировано из оригинала 22 марта 2015 г. Проверено 17 марта 2015 г.
- ^ «Архивная копия» . Архивировано из оригинала 7 апреля 2015 г. Проверено 29 октября 2013 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ «Получите Flow бесплатно — Microsoft Store (ru-RU)» . Магазин Майкрософт . Проверено 22 ноября 2018 г.
- ^ Коцума, Коити; Такенага, Ясухико (март 2010 г.), «NP-полнота и перечисление головоломки с числовыми связями» , Технический отчет IEICE. Теоретические основы вычислительной техники , 109 (465): 1–7.
- ^ Адкок, Аарон; Демейн, Эрик Д.; Демейн, Мартин Л; О'Брайен, Майкл П.; Вильямиль, Фернандо Санчес; Д. Салливан, Блер (23 октября 2014 г.), «Зигзагообразная нумерационная связь является NP-полной» , Journal of Information Processing , 23 (3): 239–245, arXiv : 1410.5845 , doi : 10.2197/ipsjjip.23.239 , S2CID 15735280