Гоиси Хирои
| 1. | Пример с фиксированным первым камнем. |
| 2. | Неудачная попытка: поскольку развороты запрещены, верхний правый камень должен быть последним. |
| 3. | Неудачная попытка: так как камень 4 при его прохождении убирается, то от камня 7 идти некуда. |
| 4. | Единственное решение, даже если камень 1 не зафиксирован. |
Гоиси Хирои , также известный как Хироимоно , представляет собой японский вариант пасьянса с колышками . В нем колышки (или камни на доске Го ) расположены по заданному шаблону, и игрок должен собирать все колышки или камни один за другим. В некоторых вариантах выбор первого камня фиксирован, в других игрок волен выбирать первый камень. [1] После первого камня каждый удаленный камень должен быть взят со следующей занятой позиции по вертикальной или горизонтальной линии от ранее удаленного камня. Кроме того, невозможно изменить направление вдоль линии:каждый шаг из одного положения в следующее должен либо продолжаться в том же направлении, что и предыдущий шаг, либо поворачиваться под прямым углом от предыдущего шага.
Эти головоломки использовались для ставок в барах в Японии 14 века. [2] и их коллекция была опубликована в японском сборнике головоломок 1727 года. [3]
Определение того, можно ли решить данную головоломку, является NP-полным . Это можно доказать либо путем редукции ко многим единицам из 3-выполнимости , [1] или путем экономного сокращения тесно связанной с ней гамильтоновой проблемы пути . [4]
Ссылки
[ редактировать ]- ^ Jump up to: а б Андерссон, Дэниел (2007), «HIROIMONO Is NP-полный», в Крещенци, Пьерлуиджи; Пренсипи, Джузеппе; Пуччи, Джеппино (ред.), «Забава с алгоритмами: 4-я международная конференция», FUN 2007, Кастильончелло, Италия, 3–5 июня 2007 г., Труды , конспекты лекций по информатике, том. 4475, Springer, стр. 30–39, номер документа : 10.1007/978-3-540-72914-3_5 , ISBN. 978-3-540-72913-6
- ^ Костелло, Мэтью Дж. (1988), Величайшие головоломки всех времен , Дуврские книги по математическим и логическим головоломкам, криптографии и воссозданию слов, Courier Corporation, стр. 9–10, ISBN 9780486292250
- ^ Тагая, К. (1727 г.), Вакоку Чие Курабэ . Цитируется Фукуи, Суэцугу и Судзуки (2017) .
- ^ Фукуи, Масанори; Суэцугу, Коки; Судзуки, Акира (2017), «Сложность «Гойси Хирои» », Тезисы 20-й Японской конференции по дискретной и вычислительной геометрии, графикам и играм (JCDCG³ 2017) (PDF) , стр. 142–143, заархивировано из оригинала. (PDF) 12 сентября 2017 г. , получено 11 сентября 2017 г.