Как устроены головоломки Numberlink
Thread Link — это головоломка Numberlink: пары одинаковых чисел на сетке нужно соединить путями, которые никогда не пересекаются. Идее больше ста лет, за ней скрывается задача, трудная для компьютеров, а несколько простых привычек заметно облегчают решение.
Правила
Поле — это квадратная сетка, на которой стоят числа, каждое ровно дважды. Соедините каждую пару путём, который переходит из клетки в соседнюю клетку по горизонтали или вертикали. Пути могут поворачивать сколько угодно, но два пути не могут занимать одну клетку, поэтому они никогда не пересекаются, и путь не может проходить через чужое число. В Thread Link, как и в большинстве современных версий, головоломка закончена только тогда, когда пути ещё и покрывают все клетки поля.
Головоломка с долгой историей
Такие головоломки с путями появились ещё в девятнадцатом веке: Сэм Лойд опубликовал свой вариант в 1897 году, а в книге Генри Дьюдени «Amusements in Mathematics» 1917 года есть задача об автомобилистах, которые должны доехать до своих гаражей так, чтобы их маршруты не пересеклись. Японское издательство Nikoli сделало популярной форму на сетке под названием Number Link, а с буквами вместо чисел — под названием Arukone. Позже головоломка полюбилась на телефонах, где провести путь пальцем особенно естественно.
Почему это трудно для компьютеров
Соединить пары точек на сетке без пересечений — та же задача, с которой сталкивается инженер, разводя проводники на печатной плате, и в общем случае она NP-полна: неизвестен способ быстро решить любой большой случай, хотя проверить готовый ответ легко. Маленькие поля не проблема для компьютера, который перебирает пути и возвращается назад, но число вариантов растёт взрывообразно вместе с размером поля. Люди решают Numberlink с помощью закономерностей и логики, а не перебирая всё подряд.
Как Thread Link создаёт головоломки
Сначала игра находит случайный путь, проходящий через каждую клетку ровно один раз, — гамильтонов путь. Она начинает с простого пути змейкой и тысячи раз перестраивает его с помощью хода под названием backbite. Затем она режет путь на куски не короче трёх клеток, отбрасывая разрезы, при которых два конца куска касаются друг друга, и ставит число на оба конца каждого куска. Поскольку куски покрывают всю сетку, у каждой головоломки есть решение, заполняющее поле. Генератор случайных чисел с начальным значением привязывает каждую головоломку к её размеру и номеру.
Советы по решению
Начинайте с краёв и углов: пара, числа которой стоят на одном краю, часто может пройти вдоль него. Ищите клетки, у которых только одна свободная соседняя клетка: путь должен войти туда и выйти той же дорогой, а это возможно, только если там стоит число. Никогда не оставляйте островок пустых клеток, до которого не дотянется ни один путь. Если два числа одной пары стоят близко, соедините их пораньше и покороче, чтобы они не мешали остальным. А когда поле заполнено соединёнными парами, но несколько клеток пустуют, обычно одна нить может сделать крюк через них.
Часто задаваемые вопросы
Numberlink — это то же самое, что «соедини точки»?
Нет. В «соедини точки» вы по порядку соединяете пронумерованные точки, чтобы получился рисунок. В Numberlink вы соединяете пары одинаковых чисел, а вся сложность в том, что пути не могут пересекаться и в большинстве версий должны заполнить всё поле.
У каждой ли головоломки только одно решение?
Головоломки в газетах и книгах обычно проверяют, чтобы решение было ровно одно. Thread Link создаёт головоломки на лету, поэтому у некоторых есть несколько способов заполнить поле; игра принимает любое правильное решение.
С какого размера поля начать?
5×5 или 6×6 — чтобы освоить ходы, 7×7 или 8×8 — для быстрой партии, 10×10 или 12×12 — когда хочется чего-то подольше. На больших полях больше пар и длиннее пути, поэтому они требуют больше планирования.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Играть в Thread Link