Хасивокакеро
Хасивокакеро ( Hashi o kakero ; букв. «строить мосты!») — разновидность логической головоломки, опубликованной Николи . [1] Он также был опубликован на английском языке под названием Bridges или Chopsticks (основываясь на неправильном переводе: хаси в названии 橋 означает мост ; хаси, написанное другим символом 箸 , означает палочки для еды ). Он также появился в The Times под именем Хаши . Во Франции , Дании , Нидерландах и Бельгии он издается под названием «Ай-Ки-Ай».
Правила
[ редактировать ]В хашивакакеро играют на прямоугольной сетке нестандартного размера, хотя сама сетка обычно не рисуется. Некоторые ячейки начинаются с цифр (обычно обведенных кружочком) от 1 до 8 включительно; это «острова». Остальные ячейки пусты.
Цель состоит в том, чтобы соединить все острова, проведя между островами серию мостов. Мосты должны соответствовать определенным критериям: [2]
- Они должны начинаться и заканчиваться на отдельных островах, проходя между ними по прямой линии.
- Они не должны пересекать другие мосты или острова.
- Они могут проходить только ортогонально (т. е. не могут проходить по диагонали).
- Пару островов соединяют максимум два моста.
- Количество мостов, соединенных с каждым островом, должно совпадать с количеством мостов на этом острове.
- Мосты должны соединить острова в единую связную группу.
Методы решения
[ редактировать ]
Решение головоломки Хасивокакеро является вопросом процедурной силы: определив, где должен быть размещен мост, размещение его там может исключить другие возможные места для мостов, принудительно разместить другой мост и так далее. [3]
Остров, показывающий «3» в углу, «5» вдоль внешнего края или «7» в любом месте, должен иметь по крайней мере один мост, отходящий от него в каждом допустимом направлении, поскольку, если в одном направлении нет моста, даже если все на других направлениях было два моста, их было недостаточно. «4» в углу, «6» вдоль границы или «8» в любом месте должны иметь по два моста в каждом направлении. Это можно обобщить, так как добавленные мосты затрудняют маршруты: например, цифра «3», по которой можно двигаться только вертикально, должна иметь хотя бы по одному мосту для движения вверх и вниз.
Это обычная практика вычеркивать или заполнять острова, квота на мосты которых достигнута. [2] Помимо уменьшения количества ошибок, это также может помочь обнаружить потенциальные «короткие замыкания»: имея в виду, что все острова должны быть соединены одной сетью мостов, мостом, который создаст закрытую сеть, к которой нельзя будет добавить никаких дополнительных мостов, можно только разрешено, если оно немедленно дает решение всей головоломки. Самый простой пример — два острова с цифрой «1», выровненных друг по другу; если только они не являются единственными двумя островами в головоломке, их нельзя соединить мостом, поскольку это завершило бы сеть, к которой невозможно добавиться, и, следовательно, сделало бы эти два острова недоступными для других.
Любой мост, который полностью изолировал бы одну группу островов от другой группы, не был бы разрешен, поскольку тогда были бы две группы островов, которые не могли бы соединить. Однако этот вывод нечасто встречается в Хасивокакеро головоломках .
Определение того, имеет ли головоломка Хашиваокеро решение, является NP-полным путем сокращения поиска гамильтоновых циклов с целочисленными координатами в графах единичных расстояний . [4] Решение с использованием целочисленного линейного программирования есть в примерах MathProg, включенных в GLPK . [5] Также сообщается о библиотеке головоломок, насчитывающей до 400 островов, а также о результатах целочисленного линейного программирования. [6]
История
[ редактировать ]Хашивакакеро впервые появился в журнале Puzzle Communication Nikoli в выпуске № 31 (сентябрь 1990 г.), хотя более ранняя форма головоломки появилась в выпуске № 28 (декабрь 1989 г.).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ↑ Puzzle Cyclopedia, Николи, 2004. ISBN 4-89072-406-0 .
- ^ Jump up to: а б Ванко, Джеффри Дж. (2010), «Дедуктивные головоломки» (PDF) , Преподавание математики в средней школе , 15 (9): 524–529, doi : 10.5951/MTMS.15.9.0524 , заархивировано из оригинала (PDF) 22 января 2021 г. , получено 14 ноября 2015 г.
- ^ Малик, Реза Фирсандайя; Эфенди, Русди; Пративи, Эриска Амрина (март 2012 г.), «Решение игры-головоломки Хашиваокеро с использованием методов решения Хаши и поиска в глубину» , Бюллетень электротехники и информатики , 1 (1): 61–68, doi : 10.11591/eei.v1i1.227 ( неактивен 31 января 2024 г.)
{{citation}}: CS1 maint: DOI неактивен по состоянию на январь 2024 г. ( ссылка ) - ^ Андерссон, Дэниел (2009), «Хашивакакеро NP-полн», Information Processing Letters , 109 (19): 1145–1146, doi : 10.1016/j.ipl.2009.07.017 , MR 2552932 .
- ^ «Репозиторий GTLK в Github» . Гитхаб . Проверено 20 октября 2022 г. .
- ^ Коэльо, LC; Лапорт, Г.; Линдбек, А.; Видал, Т. (2019), «Эталонные экземпляры и алгоритм ветвей и разрезов для головоломки Хасивокакеро», arXiv : 1905.00973 [ cs.DM ] .
Внешние ссылки
[ редактировать ]