Hashiwokakero (橋 を か け ろHashi o kakero ; lit. "¡construye puentes!") Es un tipo de acertijo de lógica 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 de Hashi . En Francia , Dinamarca , Holanday Bélgica se publica con el nombre Ai-Ki-Ai.
![Rompecabezas resuelto](http://wikiimg.tojsiabtv.com/wikipedia/commons/f/f6/Val42-Bridge1.png)
Reglas
Hashiwokakero se juega en una cuadrícula rectangular sin tamaño estándar, aunque la cuadrícula en sí no se suele dibujar. Algunas celdas comienzan con números (generalmente rodeados con un círculo) del 1 al 8 inclusive; estas son las "islas". El resto de las celdas están vacías.
El objetivo es conectar todas las islas dibujando una serie de puentes entre las islas. Los puentes deben seguir ciertos criterios: [2]
- Deben comenzar y terminar en islas distintas, viajando en línea recta entre ellas.
- No deben cruzar ningún otro puente o isla.
- Solo pueden correr ortogonalmente (es decir, no pueden correr en diagonal).
- A lo sumo, dos puentes conectan un par de islas.
- El número de puentes conectados a cada isla debe coincidir con el número de esa isla.
- Los puentes deben conectar las islas en un solo grupo conectado.
Métodos de solución
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/5e/Bridges-example.png/200px-Bridges-example.png)
Resolver un rompecabezas de Hashiwokakero es una cuestión de fuerza de procedimiento: habiendo determinado dónde se debe colocar un puente, colocarlo allí puede eliminar otros posibles lugares para puentes, forzar la colocación de otro puente, etc. [3]
Una isla que muestre '3' en una esquina, '5' a lo largo del borde exterior o '7' en cualquier lugar debe tener al menos un puente que irradie en cada dirección válida, porque si una dirección no tuviera un puente, incluso si todas otras direcciones lucían dos puentes, no se habrán colocado suficientes. Obviamente, 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 como puentes agregados que obstruyen las rutas: un '3' que solo se puede viajar desde vertical debe tener al menos un puente para arriba y para abajo, por ejemplo.
Es una práctica común tachar o completar 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 en la que no se podrían agregar más puentes. a sólo se puede permitir si arroja inmediatamente la solución al rompecabezas completo. El ejemplo más simple de esto son dos islas que muestran "1" alineadas entre sí; a menos que sean las únicas dos islas en el rompecabezas, no pueden estar conectadas por un puente, ya que eso completaría una red a la que no se puede agregar y, por lo tanto, obligaría a esas dos islas a ser inalcanzables por otras.
No se permitiría ningún puente que aislara completamente a un grupo de islas de otro grupo, ya que uno tendría dos grupos de islas que no podrían conectarse. Esta deducción, sin embargo, no se ve con mucha frecuencia en los rompecabezas de Hashiwokakero .
Determinar si un acertijo de Hashiwokakero tiene una solución es NP-completo , mediante una reducción de la búsqueda de ciclos hamiltonianos en gráficas de unidades de distancia de coordenadas enteras . [4] Hay una solución que usa programación lineal entera en los ejemplos de MathProg incluidos en GLPK . [ cita requerida ] . También se informa una biblioteca de rompecabezas que cuenta hasta 400 islas, así como resultados de programación lineal entera. [5]
Historia
Hashiwokakero apareció por primera vez en Puzzle Communication Nikoli en el número 31 (septiembre de 1990), aunque una forma anterior del rompecabezas apareció en el número 28 (diciembre de 1989).
Ver también
Referencias
- ^ Puzzle Cyclopedia, Nikoli, 2004. ISBN 4-89072-406-0 .
- ^ a b Wanko, Jeffrey J. (2010), "Deductive Puzzling" (PDF) , Enseñanza de las matemáticas en la escuela secundaria , 15 (9): 524–529, doi : 10.5951 / MTMS.15.9.0524.
- ^ Malik, Reza Firsandaya; Efendi, Rusdi; Pratiwi, Eriska Amrina (marzo de 2012), "Resolviendo el juego de rompecabezas Hashiwokakero con técnicas de resolución de Hashi y búsqueda en profundidad" , Boletín de Ingeniería Eléctrica e Informática , 1 (1): 61–68, doi : 10.11591 / eei.v1i1.227 ( inactivo 31 de mayo de 2021)Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace )
- ^ Andersson, Daniel (2009), "Hashiwokakero is NP-complete", Information Processing Letters , 109 (19): 1145-1146, doi : 10.1016 / j.ipl.2009.07.017 , MR 2552932.
- ^ 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 ].