Un solver informático de nonogramas suele alternar entre dos tareas: resolver líneas individuales bajo las restricciones actuales y propagar cada nueva casilla forzada hacia las líneas cruzadas. Si ese proceso alcanza un punto fijo antes de completar la cuadrícula, los solvers más potentes pueden probar supuestos temporalmente o ramificar entre las posibilidades restantes.
Cada programa implementa los detalles de forma distinta, pero la estructura análisis de línea → propagación → búsqueda es un buen modelo para entender cómo funcionan.
1. Representar el puzle como restricciones
El solver almacena:
- las secuencias de pistas de las filas;
- las secuencias de pistas de las columnas;
- el estado actual de cada casilla: rellena, vacía o desconocida.
Cada fila y columna es un problema unidimensional: encontrar disposiciones de sus bloques de pista que sean compatibles con todas las casillas conocidas.
Una cuadrícula completa solo es válida cuando cada línea tiene al menos una disposición compatible y todas las casillas coinciden en las intersecciones fila-columna.
2. Resolver una línea
Un solver de líneas intenta determinar qué casillas están forzadas por las pistas de esa línea y por sus estados conocidos actuales.
Existen distintas estrategias de implementación.
Una estrategia práctica, documentada por pbnsolve de WebPBN, encuentra una colocación legal con los bloques empujados todo lo posible hacia un extremo y otra hacia el extremo opuesto. Las casillas ocupadas por el mismo bloque en ambas colocaciones extremas pueden marcarse como rellenas; las casillas demostradas entre los mismos bloques pueden marcarse como vacías.
Los solvers de línea más completos pueden enumerar o calcular dinámicamente todos los patrones de línea válidos compatibles con el estado actual e intersectarlos.
3. Volver a colocar las líneas cruzadas afectadas en la lista de trabajo
Supón que un solver de fila demuestra que R4C7 está rellena.
La columna 7 ahora contiene información nueva. Una buena implementación no necesita reiniciar todo el puzle a ciegas: puede programar esa columna afectada para otra pasada.
Si la columna fuerza después casillas en las filas 2 y 8, esas filas vuelven a ser candidatas para procesarse.
Es la versión programática del mismo ritmo fila-columna que utiliza una persona al resolver.
4. Continuar hasta alcanzar un punto fijo de propagación
El solver sigue procesando líneas útiles hasta que ocurre una de estas situaciones:
- todas las casillas están determinadas;
- aparece una contradicción;
- ninguna línea puede producir otra casilla forzada.
El tercer estado es un punto fijo bajo el método de resolución actual. No significa automáticamente que el puzle tenga varias soluciones ni que carezca de solución lógica. Significa que ese motor de inferencia concreto ya no puede avanzar de forma directa.
Un solver de líneas más fuerte todavía podría encontrar un estado forzado que uno más barato no detectó.
5. Detectar contradicciones
Una contradicción aparece cuando los supuestos actuales hacen imposible alguna restricción.
Ejemplos:
- una línea no tiene ninguna colocación válida;
- un bloque confirmado es más largo que su pista;
- un bloque obligatorio ya no cabe en ningún sitio;
- una casilla queda forzada simultáneamente como rellena y vacía por ramas incompatibles.
En términos de patrones, una línea con cero patrones válidos es imposible.
Esto hace que la detección de contradicciones sea útil tanto para validar estados de jugador como para algoritmos de búsqueda.
6. Utilizar probing o búsqueda cuando se agota la lógica directa
Un solver general completo puede necesitar explorar alternativas.
Un enfoque sencillo en profundidad puede:
- elegir una casilla desconocida o una decisión sobre un bloque;
- asumir uno de sus estados legales;
- ejecutar de nuevo la propagación;
- continuar si la rama sigue siendo posible;
- retroceder si termina en contradicción.
Una estrategia de probing explora temporalmente supuestos candidatos y mide sus consecuencias antes de decidir qué rama conservar. pbnsolve de WebPBN documenta este enfoque con detalle.
La distinción importante es que un ordenador puede utilizar búsqueda para garantizar completitud incluso cuando la lógica pensada para una persona se ha detenido.
7. Comprobar unicidad
Para validar un puzle, encontrar una solución no basta.
Un solver puede continuar buscando después de la primera y preguntar si existe una segunda solución completa distinta.
Los resultados son:
- cero soluciones → conjunto de pistas inconsistente;
- una solución → único;
- dos o más → ambiguo.
Esto hace que los solvers automáticos sean valiosos no solo para jugar, sino también en construcción y pipelines de publicación de puzles.
No todos los solvers utilizan el mismo algoritmo
Los nonogramas pueden modelarse con varios marcos computacionales.
Las implementaciones pueden combinar:
- solvers de línea especializados;
- programación dinámica;
- programación por restricciones;
- restricciones booleanas de tipo SAT;
- programación entera;
- búsqueda en profundidad;
- búsqueda heurística;
- probing y caché.
La investigación ha comparado solvers especializados y propuesto formulaciones matemáticas alternativas. No existe una arquitectura única obligatoria.
Lo que define la corrección es que el algoritmo respete las pistas y restricciones de casillas y que, cuando afirma completitud o unicidad, explore suficiente espacio de soluciones para justificar esa afirmación.
Lógica de línea rápida frente a lógica completa
Existe un compromiso de implementación sutil: una rutina de línea muy rápida puede no deducir todas las casillas forzadas disponibles en esa línea.
WebPBN señala expresamente que su rutina de solapamiento izquierda/derecha es rápida pero no completa, por lo que pbnsolve puede ejecutar una comprobación más exhaustiva cuando la resolución ordinaria se atasca.
Esto refleja una diferencia similar en resolución humana:
- una técnica visual barata puede revelar muchas casillas rápidamente;
- el análisis completo de patrones válidos puede revelar más casillas forzadas, pero con mayor coste mental.
Cómo puede un solver estimar dificultad
Si un solver registra su propio trabajo, puede generar características como:
- número de resoluciones de línea;
- número de rondas de propagación;
- inferencia más fuerte necesaria;
- cantidad de patrones considerados;
- número de probes o ramas;
- profundidad máxima de búsqueda.
Esas características pueden alimentar un modelo de dificultad, aunque seguirán describiendo la dificultad en relación con esa arquitectura concreta de solver.
Por qué la resolución general todavía puede ser difícil
Un solver especializado puede hacer que muchos nonogramas de libros parezcan triviales y, sin embargo, no existe un método conocido en tiempo polinómico que resuelva todas las instancias posibles de nonogramas salvo que cambien supuestos fundamentales de la teoría de complejidad.
Es una afirmación sobre el peor caso, no una afirmación de que tu nonograma diario 15×15 necesite un superordenador.
Qué aprender después
Para la teoría detrás de la dificultad en el peor caso, continúa con Por qué los nonogramas son computacionalmente difíciles. Para el equivalente humano de los supuestos temporales, vuelve a Razonamiento por contradicción.
Preguntas frecuentes
¿Los solvers de nonogramas prueban por fuerza bruta todas las cuadrículas?
Los buenos solvers no lo necesitan. Utilizan restricciones de línea y propagación para eliminar enormes cantidades de posibilidades antes de buscar, y muchos puzles publicados se resuelven sin ramificación profunda.
¿Puede un solver demostrar que un puzle tiene solución única?
Sí, siempre que realice una búsqueda suficientemente completa como para descartar todas las soluciones alternativas.
¿Los métodos de resolución humanos e informáticos son iguales?
Se solapan conceptualmente, sobre todo en lógica de líneas y propagación, pero los ordenadores pueden seguir muchas más posibilidades y utilizar búsquedas sistemáticas que serían tediosas para una persona.