Goishi Hiroi , también conocido como Hiroimono , es una variante japonesa del solitario de clavijas . En él, las clavijas (o piedras en un tablero de Go ) están dispuestas en un patrón establecido, y el jugador debe recoger todas las clavijas o piedras, una por una. En algunas variantes, la elección de la primera piedra es fija, mientras que en otras el jugador es libre de elegir la primera piedra. [1] Después de la primera piedra, cada piedra que se retira debe tomarse de la siguiente posición ocupada a lo largo de una línea vertical u horizontal desde la piedra retirada anteriormente. Además, no es posible invertir la dirección a lo largo de una línea: cada paso de una posición a la siguiente debe continuar en la misma dirección que el paso anterior, o girar en ángulo recto desde el paso anterior.
Estos rompecabezas se usaban para apuestas de bar en el Japón del siglo XIV, [2] y una colección de ellos se publicó en un libro de rompecabezas japonés de 1727. [3]
Determinar si un problema dado puede resolverse es NP-completo . Esto puede demostrarse ya sea mediante una reducción de muchos-uno a partir de la 3-satisfacibilidad , [1] o mediante una reducción parsimoniosa a partir del problema de la trayectoria hamiltoniana , estrechamente relacionado . [4]