Hashiwokakero (橋をかけろHashi o kakero ; lit. "¡construye puentes!") es un tipo de rompecabezas de lógica publicado por Nikoli . [1] También se ha publicado en inglés con el nombre Bridges or Chopsticks (basado en una traducción errónea: 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 , Países Bajos y Bélgica se publica con el nombre de Ai-Ki-Ai.
El Hashiwokakero se juega en una cuadrícula rectangular sin un tamaño estándar, aunque la cuadrícula en sí no suele estar dibujada. Algunas celdas comienzan con números (normalmente rodeados por 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 mediante la construcción de una serie de puentes entre ellas. Los puentes deben cumplir ciertos criterios: [2]
Resolver un rompecabezas Hashiwokakero es una cuestión de fuerza procedimental: una vez determinado dónde debe colocarse un puente, colocarlo allí puede eliminar otros posibles lugares 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 irradia desde ella en cada dirección válida, ya que si una dirección no tiene un puente, incluso si todas las demás direcciones tienen dos puentes, no se habrán 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 agregados obstruyen las rutas: un '3' que solo se puede recorrer verticalmente debe tener al menos un puente para subir y bajar, por ejemplo.
Es una práctica común tachar o rellenar las islas cuyo cupo de puentes se ha alcanzado. [2] Además de reducir los 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 agregar más puentes solo se puede permitir si produce inmediatamente la solución del rompecabezas completo. El ejemplo más simple de esto es 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 pueden agregar más puentes y, por lo tanto, obligaría a que esas dos islas sean inalcanzables para cualquier otra.
No se permitiría ningún puente que aislara por completo un grupo de islas de otro grupo, ya que entonces habría dos grupos de islas que no podrían conectarse. Sin embargo, esta deducción no se ve muy a menudo en los acertijos Hashiwokakero .
Determinar si un rompecabezas de Hashiwokakero tiene una solución es NP-completo , mediante una reducción a partir de la búsqueda de ciclos hamiltonianos en gráficos de distancia unitaria de coordenadas enteras . [4] Hay 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 cuentan hasta 400 islas, así como sobre los resultados de programación lineal entera. [6]
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).
{{citation}}: CS1 maint: DOI inactivo a partir de septiembre de 2024 ( enlace )