Хашіокакеро ( Хаші о какеро, інколи Хаші, букв. «будувати мости») — логічна японська головоломка, видана компанією NikoliPuzzle Cyclopedia, Nikoli, 2004. .. Вона також була опублікована англійською мовою під назвою «Мости та Палички для їжі» (через неправильний переклад: «хаші» з ієрогліфа 橋, що означає «міст»; хаші, написане з ієрогліфом 箸, означає палички для їжі). Вона також з'являлася в The Times під назвою «Хаші».У Франції, Данії, Нідерландах та Бельгії вона публікується під назвою «Ай-Кі-Ай».

Правила Хашіокакеро грається на прямокутному полі без стандартного розміру. Деякі клітинки починаються з (зазвичай обведених) чисел від 1 до 8 включно, це «острови».

Мета полягає в тому, щоб з'єднати всі острови, проклавши між ними низку мостів. Мости повинні відповідати певним критеріям:.

Вони повинні починатися та закінчуватися на різних островах, рухаючись по прямій лінії між ними. Вони не повинні перетинатися з іншими мостами чи островами. Вони можуть проходити лишень вертикально або горизонтально. Пару островів з'єднують щонайбільше два мости. Кількість мостів, з'єднаних з кожним островом, повинна збігатися з числом написаним на цьому острові. Мости повинні з'єднувати острови в єдину пов'язану групу.

Методи вирішення

Розв'язання головоломки є питання процедурної сили. Визначивши, де повинен бути розміщений міст, його розміщення в може виключити інші можливі місця для інших мостів.

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

Острови які вже виконали квоту по мостах зазвичай закреслюють для зручності. Окрім зменшення кількості помилок, це також може допомогти виявити потенційні «короткі замикання мостів». Всі острови повинні бути з’єднані однією мережею мостів. Міст який створить замкнуту групу, до якої не можна буде додавати подальші мости, є дозволеним лишень якщо він одразу дасть розв’язок усієї головоломки. Найпростіший приклад цього – два сусідні острови з позначкою «1», якщо вони не є єдиними двома островами в головоломці, їх не можна з’єднати мостом, оскільки це завершить мережу, до якої не можна буде додавати мости, і тому зробить ці два острови недоступними для будь-яких інших.

Будь-який міст, який би повністю ізолював групу островів від іншої групи, не буде дозволений, оскільки тоді виникнуть дві мережі островів, які не зможуть з'єднатися, хоча такі головоломки іноді можуть зустрічатися.

Визначення того, чи має головоломка Хашіокакеро розв'язок, є NP-повним шляхом редукції від знаходження гамільтонових циклів у графах одиничних відстаней з цілочисельними координатами.. Існує розв'язок з використанням цілочисельного лінійного програмування у прикладах MathProg, що входять до GLPK.. Також повідомляється про бібліотеку головоломок, що налічують до 400 островів, а також результати цілочисельного лінійного програмування..

Історія Хашіокакеро вперше з'явився у випуску №31 журналу Puzzle Communication Nikoli (вересень 1990 року), хоча раніший варіант цієї головоломки з'явився у випуску №28 (грудень 1989 року).

Див. також

Хіторі Судоку

Примітки