Хашивокакеро - Hashiwokakero
Хашивокакеро (橋 を か け ろ Хаши о какеро; горит «строить мосты!») - это разновидность логическая головоломка опубликовано Николи.[1] Он также был опубликован на английском языке под названием Мосты или же Палочки для еды (на основании неправильного перевода: хаши названия, 橋, средства мост; хаши написано другим персонажем, 箸, средства палочки для еды). Он также появился в Времена под именем Хаши. В Франция, Дания, то Нидерланды, и Бельгия он издается под названием Ai-Ki-Ai.
Правила
Хашивокакеро воспроизводится на прямоугольной сетке без стандартного размера, хотя сама сетка обычно не рисуется. Некоторые ячейки начинаются с цифр от 1 до 8 включительно (обычно обведены кружком); это «острова». Остальные ячейки пусты.
Цель состоит в том, чтобы соединить все острова, проведя серию мостов между островами. Мосты должны соответствовать определенным критериям:[2]
- Они должны начинаться и заканчиваться на разных островах, проходя между ними по прямой.
- Они не должны пересекать другие мосты или острова.
- Они могут идти только перпендикулярно (т. Е. Не могут идти по диагонали).
- Максимум два моста соединяют пару островов.
- Количество мостов, соединенных с каждым островом, должно соответствовать количеству на этом острове.
- Мосты должны соединять острова в единую связанную группу.
Методы решения
Решение Хашивокакеро головоломка является процедурной силой: определив, где должен быть расположен мост, его размещение может устранить другие возможные места для мостов, принудительное размещение другого моста и т. д.[3]
Остров, показывающий «3» в углу, «5» по внешнему краю или «7» в любом месте, должен иметь по крайней мере один мост, исходящий от него в каждом допустимом направлении, поскольку, если в одном направлении не было моста, даже если все на других направлениях было два моста, их будет недостаточно. Очевидно, что «4» в углу, «6» вдоль границы или «8» в любом месте должны иметь по два моста в каждом направлении. Это можно обобщить, так как добавленные мосты препятствуют маршрутам: например, «тройка», по которой можно перемещаться только вертикально, должна иметь как минимум по одному мосту для каждого движения вверх и вниз.
Обычной практикой является вычеркивание или заполнение островов, квота мостов которых была достигнута.[2] Помимо уменьшения количества ошибок, это также может помочь обнаружить потенциальные «короткие замыкания»: помня о том, что все острова должны быть соединены одной сетью мостов, мостом, который создаст замкнутую сеть, к которой нельзя будет добавить дополнительные мосты, может только быть разрешенным, если это сразу дает решение всей головоломки. Самый простой пример - два острова, показывающих цифру «1», выровненных друг относительно друга; если только они не являются двумя островами в головоломке, они не могут быть соединены мостом, так как это завершит сеть, к которой нельзя добавить, и, следовательно, сделает эти два острова недоступными для других.
Любой мост, который полностью изолирует группу островов от другой группы, не будет разрешен, так как тогда будут две группы островов, которые не смогут соединиться. Этот вывод, однако, не очень часто встречается в Хашивокакеро загадки.
Определить, есть ли решение у загадки Хашивокакеро, НП-полный, автор снижение от нахождения Гамильтоновы циклы в целочисленной координате графики единичных расстояний.[4] Есть решение, использующее целочисленное линейное программирование в примерах MathProg, включенных в ГЛПК.[нужна цитата ]. Также сообщается о библиотеке головоломок, насчитывающей до 400 островов, а также о результатах целочисленного линейного программирования.[5]
История
Хашивокакеро впервые появился в Пазл Общение Николи в выпуске № 31 (сентябрь 1990 г.), хотя более ранняя форма головоломки появилась в № 28 (декабрь 1989 г.).
Смотрите также
Рекомендации
- ^ Головоломка Циклопедия, Николи, 2004. ISBN 4-89072-406-0.
- ^ а б Ванко, Джеффри Дж. (2010), «Дедуктивная головоломка» (PDF), Преподавание математики в средней школе, 15 (9): 524–529.
- ^ Малик, Реза Фирсандая; Эфенди, Русди; Пративи, Эриска Амрина (март 2012 г.), "Решение головоломки Хашивокакеро с помощью техники решения Хаши и поиска в глубину", Бюллетень электротехники и информатики, 1 (1): 61–68, Дои:10.11591 / eei.v1i1.227 (неактивно 2020-10-20)CS1 maint: DOI неактивен по состоянию на октябрь 2020 г. (связь)
- ^ Андерссон, Даниэль (2009), «Хашивокакеро является NP-полным», Письма об обработке информации, 109 (19): 1145–1146, Дои:10.1016 / j.ipl.2009.07.017, МИСТЕР 2552932.
- ^ Coelho, L.C .; Laporte, G .; Lindbeck, A .; Видаль, Т. (2019), «Экземпляры тестов и алгоритм ветвей и разрезов для головоломки Хашивокакеро», arXiv:1905.00973 [cs.DM ].