Hispanopedia Wiki
Articulo de referencia

Hashiwokakero

Un rompecabezas de Hashiwokakero (izquierda) y una de sus soluciones. El número de puentes conectados a cada "isla" debe coincidir con el número escrito en esa isla. Hashiwokake...

Hispanopedia WikiContenido en espanolLectura gratuita
Rompecabezas sin resolver
Rompecabezas resuelto
Un rompecabezas de Hashiwokakero (izquierda) y una de sus soluciones. El número de puentes conectados a cada "isla" debe coincidir con el número escrito en esa isla.

Hashiwokakero (橋をかけろHashi o kakero ; lit. "¡construye puentes!") es un tipo de rompecabezas lógico publicado por Nikoli . [ 1 ] También se ha publicado en inglés con el nombre Bridges or Chopsticks (basado en una mala traducción: el hashi del título,橋, significa puente ; hashi escrito con otro carácter,箸, significa palillos ). También ha aparecido en The Times con el nombre Hashi . En Francia , Dinamarca , los Países Bajos y Bélgica se publica con el nombre Ai-Ki-Ai.

Normas

Hashiwokakero se juega en una cuadrícula rectangular de tamaño variable, aunque la cuadrícula en sí no suele dibujarse. Algunas casillas comienzan con números del 1 al 8 (generalmente encerrados en un círculo); estas son las "islas". El resto de las casillas están vacías.

El objetivo es conectar todas las islas dibujando una serie de puentes entre ellas. Los puentes deben cumplir ciertos criterios: [ 2 ]

  • Deben comenzar y terminar en islas distintas, viajando en línea recta entre ellas.
  • No deben cruzar ningún otro puente ni isla.
  • Solo pueden discurrir ortogonalmente (es decir, no pueden discurrir en diagonal).
  • Como máximo, dos puentes conectan un par de islas.
  • El número de puentes conectados a cada isla debe coincidir con el número de puentes que hay en esa isla.
  • Los puentes deben conectar las islas formando un único grupo interconectado.

Métodos de solución

Rompecabezas Hashiwokakero de dificultad moderada ( solución )

Resolver un rompecabezas de Hashiwokakero es una cuestión de fuerza procedimental: una vez determinado dónde debe colocarse un puente, colocarlo allí puede eliminar otros lugares posibles para puentes, forzando la colocación de otro puente, y así sucesivamente. [ 3 ]

Una isla que muestre un '3' en una esquina, un '5' a lo largo del borde exterior o un '7' en cualquier lugar debe tener al menos un puente que se extienda desde ella en cada dirección válida, ya que si una dirección no tuviera un puente, incluso si todas las demás direcciones tuvieran dos, no se habrían colocado suficientes. Un '4' en una esquina, un '6' a lo largo del borde o un '8' en cualquier lugar debe tener dos puentes en cada dirección. Esto se puede generalizar, ya que los puentes adicionales obstruyen las rutas: un '3' que solo se puede recorrer verticalmente debe tener al menos un puente para subir y otro para bajar, por ejemplo.

Es práctica común tachar o rellenar las islas cuya cuota de puentes se ha alcanzado. [ 2 ] Además de reducir errores, esto también puede ayudar a localizar posibles "cortocircuitos": teniendo en cuenta que todas las islas deben estar conectadas por una red de puentes, un puente que crearía una red cerrada a la que no se podrían añadir más puentes solo se puede permitir si proporciona inmediatamente la solución al rompecabezas completo. El ejemplo más sencillo de esto son dos islas que muestran '1' alineadas entre sí; a menos que sean las únicas dos islas en el rompecabezas, no se pueden conectar por un puente, ya que eso completaría una red a la que no se puede añadir nada más y, por lo tanto, obligaría a que esas dos islas fueran inaccesibles para cualquier otra.

No se permitiría ningún puente que aislara por completo un grupo de islas de otro, ya que se crearían dos grupos de islas inconexos. Sin embargo, esta deducción no es muy común en los acertijos de Hashiwokakero .

Determinar si un rompecabezas de Hashiwokakero tiene solución es NP-completo , mediante una reducción a partir de la búsqueda de ciclos hamiltonianos en grafos de distancia unitaria de coordenadas enteras . [ 4 ] Existe una solución que utiliza programación lineal entera en los ejemplos de MathProg incluidos en GLPK . [ 5 ] También se informa sobre una biblioteca de rompecabezas que cuenta hasta 400 islas, así como resultados de programación lineal entera. [ 6 ]

Historia

Hashiwokakero apareció por primera vez en Puzzle Communication Nikoli en el número 31 (septiembre de 1990), aunque una versión anterior del rompecabezas apareció en el número 28 (diciembre de 1989).

Véase también

Referencias

  1. ^ Enciclopedia de rompecabezas, Nikoli, 2004. ISBN 4-89072-406-0.
  2. 1 2 Wanko, Jeffrey J. (2010), "Resolución de problemas deductivos" (PDF) , Mathematics Teaching in the Middle School , 15 (9): 524– 529, doi : 10.5951/MTMS.15.9.0524 , archivado del original (PDF) el 22-01-2021 , recuperado el 14-11-2015.
  3. ↑ Malik, Reza Firsandaya; Efendi, Rusdi; Pratiwi, Eriska Amrina (marzo de 2012), "Resolución del juego de rompecabezas Hashiwokakero con técnicas de resolución de Hashi y búsqueda en profundidad" , Bulletin of Electrical Engineering and Informatics , 1 (1): 61– 68, doi : 10.11591/eei.v1i1.227 (inactivo el 12 de julio de 2025){{citation}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
  4. ↑ Andersson, Daniel (2009), "Hashiwokakero es NP-completo", Information Processing Letters , 109 (19): 1145–1146 , doi : 10.1016/j.ipl.2009.07.017 , MR 2552932 .
  5. ↑ "Repositorio GTLK en Github" . GitHub . Consultado el 20 de octubre de 2022 ..
  6. ↑ Coelho, LC; Laporte, G.; Lindbeck, A.; Vidal, T. (2019), "Instancias de referencia y algoritmo de ramificación y corte para el rompecabezas de Hashiwokakero", arXiv : 1905.00973 [ cs.DM ].
  • Página en inglés de Nikoli sobre Hashiwokakero