Гоиси Хирои , также известный как Хироимоно , - это японский вариант пасьянса с колышками . В нем колышки (или камни на доске Го ) расположены в определенном порядке, и игрок должен подбирать все колышки или камни один за другим. В некоторых вариантах выбор первого камня фиксирован, в то время как в других игрок может выбрать первый камень. [1] После первого камня каждый удаленный камень должен быть взят из следующей занятой позиции по вертикальной или горизонтальной линии от ранее удаленного камня. Кроме того, невозможно изменить направление вдоль линии: каждый шаг от одной позиции к другой должен либо продолжаться в том же направлении, что и предыдущий шаг, либо поворачиваться под прямым углом. из предыдущего шага.
Эти головоломки использовались для ставок на барах в Японии 14-го века [2], а их собрание было опубликовано в японском сборнике головоломок 1727 года [3].
Определение того, может ли данная головоломка быть решена, является NP-полным . Это может быть доказано , либо путем сокращения многих один из 3-выполнимости , [1] или путем экономного уменьшения от тесно связанной с гамильтоновой задачи пути . [4]
Рекомендации
- ^ a b Андерссон, Даниэль (2007), «HIROIMONO - NP-Complete», в Crescenzi, Pierluigi; Пренсипи, Джузеппе; Пуччи, Геппино (ред.), Развлечения с алгоритмами: 4-я Международная конференция, FUN 2007, Кастильончелло, Италия, 3-5 июня 2007 г., Proceedings , Lecture Notes in Computer Science, 4475 , Springer, pp. 30–39, doi : 10.1007 / 978-3-540-72914-3_5 , ISBN 978-3-540-72913-6
- ^ Костелло, Мэтью Дж. (1988), Величайшие загадки всех времен , Дуврские книги по математическим и логическим головоломкам, криптографии и воссозданию слов, Courier Corporation, стр. 9–10, ISBN 9780486292250
- ^ К. Тагая (1727 г.), Вакоку Чи Курабе. Цитируется Fukui, Suetsugu & Suzuki (2017) .
- ^ Фукуи, Масанори; Суэцугу, Коки; Судзуки, Акира (2017), «Сложность« Гоиси Хирои » », выдержки из 20-й Японской конференции по дискретной и вычислительной геометрии, графам и играм (JCDCG³ 2017) (PDF) , стр. 142–143, заархивировано с оригинала (PDF) 12 сентября 2017 г. , дата обращения 11 сентября 2017 г.