Хашивокакеро

Головоломка

Головоломка Hashiwokakero (слева) и одно из ее решений. Количество мостов, соединенных с каждым «островом», должно соответствовать числу, написанному на этом острове.

Hashiwokakero (橋をかけろHashi o kakero ; букв. «строим мосты!») — тип логической головоломки , опубликованной Николи .^[1] Она также была опубликована на английском языке под названием Bridges или Chopsticks (основанная на неправильном переводе: хаси в названии, 橋, означает мост ; хаси, написанное другим иероглифом, 箸, означает палочки для еды ). Она также появилась в The Times под названием Hashi . Во Франции , Дании , Нидерландах и Бельгии она опубликована под названием Ai-Ki-Ai.

Правила

Hashiwokakero играется на прямоугольной сетке без стандартного размера, хотя сама сетка обычно не рисуется. Некоторые клетки начинаются с (обычно обведенных) чисел от 1 до 8 включительно; это «острова». Остальные клетки пустые.

Цель состоит в том, чтобы соединить все острова, нарисовав ряд мостов между островами. Мосты должны соответствовать определенным критериям: ^[2]

Они должны начинаться и заканчиваться на разных островах, проходя между ними по прямой линии.
Им не следует пересекать никакие другие мосты или острова.
Они могут располагаться только перпендикулярно (т.е. не могут располагаться по диагонали).
Пару островов соединяют максимум два моста.
Количество мостов, соединенных с каждым островом, должно соответствовать количеству мостов на этом острове.
Мосты должны соединять острова в единую связную группу.

Методы решения

Головоломка средней сложности *Hashiwokakero* (решение)

Решение головоломки Hashiwokakero — это вопрос процедурной силы: определив, где должен быть размещен мост, разместив его там, можно исключить другие возможные места для мостов, заставив разместить другой мост и т. д. ^[3]

Остров, показывающий «3» в углу, «5» вдоль внешнего края или «7» в любом месте, должен иметь по крайней мере один мост, исходящий от него в каждом допустимом направлении, поскольку если в одном направлении не было моста, даже если во всех других направлениях было два моста, их было бы недостаточно. «4» в углу, «6» вдоль границы или «8» в любом месте должны иметь два моста в каждом направлении. Это можно обобщить, так как добавленные мосты затрудняют маршруты: «3», по которому можно перемещаться только вертикально, должен иметь по крайней мере один мост вверх и вниз, например.

Обычной практикой является вычеркивание или заполнение островов, квота мостов на которых достигнута. ^[2] Помимо уменьшения ошибок, это также может помочь обнаружить потенциальные «короткие замыкания»: имея в виду, что все острова должны быть соединены одной сетью мостов, мост, который создаст замкнутую сеть, к которой нельзя будет добавить никаких дополнительных мостов, может быть разрешен только в том случае, если он немедленно даст решение всей головоломки. Простейшим примером этого являются два острова, показывающие «1», выровненные друг с другом; если только они не являются единственными двумя островами в головоломке, их нельзя соединить мостом, поскольку это завершит сеть, к которой нельзя будет добавить что-либо, и, следовательно, сделает эти два острова недостижимыми для любых других.

Любой мост, который полностью изолировал бы группу островов от другой группы, не был бы разрешен, поскольку тогда было бы две группы островов, которые не могли бы соединиться. Однако этот вывод не очень часто встречается в головоломках Hashiwokakero .

Определение того, имеет ли головоломка Hashiwokakero решение, является NP-полной задачей , путем сведения к нахождению гамильтоновых циклов в графах единичных расстояний с целыми координатами . ^[4] В примерах MathProg, включенных в GLPK , есть решение с использованием целочисленного линейного программирования . ^[5] Также сообщается о библиотеке головоломок, насчитывающих до 400 островов, а также о результатах целочисленного линейного программирования. ^[6]

История

Hashiwokakero впервые появился в Puzzle Communication Nikoli в выпуске № 31 (сентябрь 1990 г.), хотя более ранняя версия головоломки появилась в выпуске № 28 (декабрь 1989 г.).

Смотрите также

Список типов головоломок Николи

Ссылки

^ Puzzle Cyclopedia, Николи, 2004. ISBN 4-89072-406-0 .
^ ab Wanko, Jeffrey J. (2010), «Дедуктивная головоломка» (PDF) , Преподавание математики в средней школе , 15 (9): 524–529, doi :10.5951/MTMS.15.9.0524, заархивировано из оригинала (PDF) 22.01.2021 , извлечено 14.11.2015.
^ Малик, Реза Фирсандая; Эфенди, Русди; Пративи, Эриска Амрина (март 2012 г.), «Решение головоломки Hashiwokakero с использованием методов решения Hashi и поиска в глубину», Бюллетень электротехники и информатики , 1 (1): 61–68, doi :10.11591/eei.v1i1.227 (неактивен 2024-09-12){{citation}}: CS1 maint: DOI неактивен по состоянию на сентябрь 2024 г. ( ссылка )
^ Андерссон, Дэниел (2009), «Hashiwokakero является NP-полным», Information Processing Letters , 109 (19): 1145–1146, doi :10.1016/j.ipl.2009.07.017, MR 2552932 .
^ "Репозиторий GTLK в Github". GitHub . Получено 20 октября 2022 г. ..
^ Коэльо, Л.К.; Лапорт, Г.; Линдбек, А.; Видал, Т. (2019), «Эталонные экземпляры и алгоритм ветвления и разрезания для головоломки Хашивокакеро», arXiv : 1905.00973 [cs.DM].

Внешние ссылки

Английская страница Николи на Hashiwokakero

[1] Puzzle Cyclopedia, Николи, 2004. ISBN 4-89072-406-0 .

[wanko-2] Wanko, Jeffrey J. (2010), «Дедуктивная головоломка» (PDF) , Преподавание математики в средней школе , 15 (9): 524–529, doi :10.5951/MTMS.15.9.0524, заархивировано из оригинала (PDF) 22.01.2021 , извлечено 14.11.2015.

[3] Малик, Реза Фирсандая; Эфенди, Русди; Пративи, Эриска Амрина (март 2012 г.), «Решение головоломки Hashiwokakero с использованием методов решения Hashi и поиска в глубину», Бюллетень электротехники и информатики , 1 (1): 61–68, doi :10.11591/eei.v1i1.227 (неактивен 2024-09-12){{citation}}: CS1 maint: DOI неактивен по состоянию на сентябрь 2024 г. ( ссылка )

[4] Андерссон, Дэниел (2009), «Hashiwokakero является NP-полным», Information Processing Letters , 109 (19): 1145–1146, doi :10.1016/j.ipl.2009.07.017, MR 2552932 .

[5] "Репозиторий GTLK в Github". GitHub . Получено 20 октября 2022 г. ..

[coelho-6] Коэльо, Л.К.; Лапорт, Г.; Линдбек, А.; Видал, Т. (2019), «Эталонные экземпляры и алгоритм ветвления и разрезания для головоломки Хашивокакеро», arXiv : 1905.00973 [cs.DM].