Гоиши Хирои, известная также как Хироимоно, — это японский вариант солитера. В этой игре колышки (или камни на доске Го) расставляются в определенном порядке, и игрок должен собрать их все по одному. В некоторых вариантах tвыбор первого камня фиксирован, в то время как в других игрок может свободно выбрать его. После первого камня каждый следующий удаляемый камень должен быть взят из следующей занятой позиции по вертикали или горизонтали от предыдущего. Кроме того, нельзя менять направление движения по линии: каждый шаг от одной позиции к другой должен либо продолжать предыдущее движение в том же направлении, либо поворачивать под прямым углом.
Эти головоломки использовались для в XIV веке, а сборник из них был опубликован в японской книге головоломок 1727.
Определение того, может ли быть решена данная головоломка, является NP-полна. Это может быть доказано либо с помощью полиномиальной сводимости из 3-выполнимости, либо с помощью из тесно связанной задачи о гамильтоновом пути.
Примечания
Категория:Логические игры Категория:Японские настольные игры