Hashiwokakero ("construir puentes" en japonés) es un rompecabezas en el que tienes la tarea de conectar un grupo de islas con puentes. Las reglas son:
- Los puentes deben correr vertical u horizontalmente entre dos islas.
- Los puentes no pueden cruzarse entre sí.
- Un par de islas pueden estar conectadas como máximo por dos puentes paralelos.
- Cada isla está marcada con un número entre 1 y 8, inclusive. El número de puentes conectados a una isla debe coincidir con el número en esa isla.
- Los puentes deben conectar las islas en un solo grupo conectado.
Su tarea es escribir un programa que resuelva los rompecabezas de Hashiwokakero.
Puede suponer que cualquier rompecabezas es solucionable y que solo hay una solución.
El programa debe ser razonablemente eficiente. Por ejemplo, resolver el siguiente rompecabezas de 25x25 no debería tomar más de 10 minutos en una PC promedio y no debería usar más de un gigabyte de memoria. Resolver rompecabezas más pequeños como el 7x7 debería llevar segundos.
Entrada:
El rompecabezas se dará como un mapa 2D de personajes, con los dígitos 1para 8representar islas y espacios que representan agua. Las líneas se rellenarán con espacios si es necesario para que tengan la misma longitud.
Las islas siempre estarán separadas horizontal y verticalmente por al menos un cuadrado de agua para que haya espacio para colocar el puente potencial entre ellas. Siempre habrá al menos dos islas en un rompecabezas.
Su programa debe leer preferiblemente el mapa de rompecabezas a partir de la entrada estándar, pero puede especificar un método de entrada alternativo si su lenguaje de programación lo requiere.
Salida:
La salida debe ser como la entrada, excepto con espacios reemplazados por puentes según sea necesario. Los puentes deben dibujarse utilizando caracteres de dibujo de caja Unicode ─(U + 2500), │(U + 2502), ═(U + 2550) y ║(U + 2551) para representar puentes simples y dobles horizontales y verticales.
Si los caracteres Unicode son un problema, puede utilizar los caracteres ASCII -, |, =y Hen su lugar.
Criterios ganadores:
Este es el código de golf. La solución más corta correcta y razonablemente eficiente gana.
Ejemplos:
Rompecabezas (7x7):
2 2 1
1 4 3
3 2
4
3 2 3
1
3 4 2
Solución:
2─2──1
│1──4─3
3──2║ ║
│ │4 ║
│3─2║ 3
1║ ║ │
3──4─2
Rompecabezas (25x25):
2 2 2 2 1 1 2 2 2 2 2
1 3 5 4 4 2
2 2 4 5 5 4 2 2 1 3
2 1 1 3 3 2 2
3 4 4 4 4 5 4 3 2 3
2 4 5 4 2 3
2 1 4 2 4 3 1 1 2
2 1 3 1 1 6 4 2
3 2 4 3 6 3 2
2 2 3 3 2 5 2 4 3
2 1 1 2
1 3 3 3 3 5 8 7 6 5 4
2 3 1 1 2
1 1 5 1 4 5 6 3 1 2
1 1 2 2 3 4
3 5 4 4 3 3 8 7 5 1 2
2 3 1 2 2 1 1
2 2 2 2 5 7 6 3 3
3 3 6 3 5 3 2 2 2 3
2 1 2 3 2 2
3 4 6 4 5 5 3 3 5 1
2 1 2 2 1 1 3
2 1 1 2 3 6 5 2 2
2 3 4 4 4 2 1
2 2 2 2 2 2 2 1 1 3 2
Solución:
2─2─2──2 1 1─2─2──2──2─2
│ │ │1─3═5══4══4─2│
2 2─4─5══5═4═2│2──1 │ │3
│ 2│ ║1│ 1─3═3─2│ │ 2║
│ ║3═4│4══4─4═5─4─3──2 │3
2 4═5─4│ │ │ ║ │ │2───3│
│2─1║ ║4─2│ 4─3 │ 1│ 1 │2
2│1─3 ║║ │1 ║1──6══4 │ 2│
│3─2──4║ 3══6─3 ║ │ │ │2
2│2═3 │3──2 │ ║ 5─2│ 4─3│
│2─1│ │ │ │ ║ ║ │1 ║ │2
│ 1─3─3─3─3─5═8═7═6──5═4│
2──3───1│1─2│ ║ │ ║ ││
1 │ 1──5─1││ 4─5─6─3─1│2
1│ │1──2║ │2 │ ║ ║ │3═4│
│3─5═4 │4──3│ 3═8═7═5│1│2
2│ │ ║ 3│ 1│2──2║ │ ║1│1│
│2 │ ║ ║2 │2──2│5═7═6─3─3
3│ 3─6─3│ 5═3 │2│ ║2│2─3│
║2 │ ║ │ ║ │ 1│2─3║2│ ║2
3│ 4═6──4─5─5──3─3─5││1║│
│2 │ │1 │ │2║2──1│ ║1││3│
2│ │ 1│ │ 1║2│3══6═5─2││2
│2─3──4═4──4─2│ │ │1│
2─2──2─2──2─2─2 1 1─3─2
1 1entrada?1 1, que es un rompecabezas válido y debe manejarse correctamente.Respuestas:
Haskell, 1074 caracteres
Originalmente, lo tenía aún más puramente japonés al implementar también las funciones primitivas en términos de combinaciones de patrones y listas simples:
Haskell, 1192
se ejecuta en ≈3 minutos en mi i5 .
Versión comentada:
fuente
Python, 1079 caracteres
El código realiza una búsqueda exhaustiva bastante sencilla
S, utilizando cierta propagación de restricciones para que se ejecute en un tiempo razonable.Erepresenta el conjunto actual de aristas, en el formato [desde, hasta, delta, posibles pesos] . desde y hacia son identificadores de isla y delta es 1 para bordes horizontales o W (= ancho de líneas) para bordes verticales. pesos posibles es una sublista de [0,1,2] que codifica el estado actual conocido de ese borde (0 = sin puente, 1 = puente simple, 2 = puente doble).Shace tres cosas Primero, propaga información, como si un borde ya no tiene un peso 0 como posibilidad, luego todos los bordes que lo cruzan se eliminan (sus pesos posibles se establecen en [0]). De manera similar, si la suma del peso mínimo para los bordes incidentes en una isla es igual al peso de la isla, entonces todos esos bordes se establecen al mínimo.En segundo lugar,
Sverifica que el gráfico todavía esté conectado usando bordes no [0] (elQcálculo).Finalmente,
Selige un borde que aún no está completamente determinado y se llama a sí mismo recursivamente, estableciendo ese borde en una de sus posibilidades restantes.Toma alrededor de 2 minutos para el mejor ejemplo.
fuente
print(B);sys.exit(0)C # -
660156612225No particularmente bien golfizado. Utiliza la biblioteca de programación de restricciones de google or-tools. Crea restricciones para el recuento total de bordes y para eliminar puentes cruzados, pero es un poco más difícil definir restricciones para garantizar que todos estén conectados. Agregué lógica para podar los componentes 2 = 2 y 1-1, pero aún tengo que pasar por la lista final (39 en la grande) y eliminar aquellos que no están completamente conectados. Funciona bastante rápido Toma solo un par de segundos en el ejemplo más grande. Sin golf:
fuente