El problema general de los nonogramas es computacionalmente difícil: existen resultados formales de NP-completitud para formulaciones estándar de decisión, y la investigación posterior describe habitualmente la resolución general de nonogramas como NP-hard.
Eso no significa que todos los nonogramas sean difíciles, que los ordenadores no puedan resolverlos ni que un 10×10 necesite tiempo exponencial en la práctica. La teoría de complejidad describe el comportamiento de las instancias más difíciles a medida que crece el tamaño del problema.
¿Qué problema analiza la teoría de complejidad?
Un resultado de complejidad necesita una pregunta computacional precisa.
Una versión simplificada de decisión es:
Dadas las pistas de filas y columnas de un nonograma, ¿existe al menos una cuadrícula de casillas rellenas/vacías que las satisfaga todas?
Una cuadrícula completa propuesta puede comprobarse eficientemente: se recorre cada fila y columna y se comparan las longitudes de sus bloques con las pistas.
La parte difícil es encontrar o decidir la existencia de una solución para todos los conjuntos posibles de pistas.
¿Qué significa NP-completo aquí?
De manera informal, un problema de decisión es NP-completo cuando:
- una solución propuesta puede verificarse eficientemente; y
- el problema es al menos tan difícil como cualquier problema de la clase NP mediante reducciones en tiempo polinómico.
El informe técnico de Ueda y Nagao de 1996 estableció resultados de NP-completitud para nonogramas mediante reducciones parsimoniosas. Trabajos posteriores citan este resultado al discutir la dificultad del problema general.
No necesitas teoría de complejidad para jugar. El resultado importa porque explica por qué no cabe esperar que un conjunto sencillo de trucos locales resuelva eficientemente todas las instancias posibles.
NP-completo no significa «siempre difícil»
Esta es la confusión más importante que hay que evitar.
Sudoku, SAT y muchos otros problemas NP-completos contienen familias enormes de instancias sencillas. Con los nonogramas ocurre lo mismo.
Los editores diseñan deliberadamente puzles con estructura útil:
- pistas informativas;
- solapamientos fuertes;
- propagación productiva entre filas y columnas;
- cuellos de botella controlados;
- a menudo un recorrido lógico agradable para una persona.
Batenburg y Kosters contrastan explícitamente los nonogramas habituales de libros, que muchas veces se resuelven mediante razonamiento local repetido por líneas, con el problema general difícil.
¿Por qué puede crecer tanto el espacio de búsqueda?
Cada línea puede admitir varias disposiciones legales. En toda la cuadrícula, esas decisiones interactúan mediante las casillas compartidas.
Una decisión que parece legal en una fila puede restringir varias columnas; esas columnas restringen otras filas; y una contradicción puede no aparecer hasta después de una cadena larga.
En el peor caso, un solver puede necesitar distinguir entre muchas combinaciones de patrones o ramificar entre alternativas.
Solo el número de cuadrículas binarias posibles es enorme: una cuadrícula de r × c tiene 2^(r·c) asignaciones brutas de relleno/vacío antes de que las pistas eliminen la mayoría.
Los buenos solvers no recorren todas esas asignaciones a ciegas, pero la cifra ilustra por qué importan las restricciones y la poda.
Por qué la lógica de líneas resuelve tantos puzles reales
Los nonogramas diseñados por personas no son instancias aleatorias del peor caso.
Los creadores suelen querer un puzle que revele una imagen reconocible y pueda resolverse con deducciones satisfactorias. Esa presión de diseño selecciona estructuras que el razonamiento habitual por líneas puede aprovechar.
Un solver puede repetir:
- resolver filas restringidas;
- transferir casillas forzadas a columnas;
- resolver las columnas modificadas;
- propagar de nuevo.
Para muchos puzles publicados, eso es suficiente.
La teoría de complejidad solo afirma que algunas entradas válidas escapan a toda estrategia universalmente eficiente, asumiendo la conjetura estándar P ≠ NP.
¿Qué diferencia hay entre NP-hard y NP-completo?
Encontrarás ambos términos en la literatura sobre nonogramas.
- NP-hard significa que un problema es al menos tan difícil como los problemas más difíciles de NP.
- NP-completo añade que el propio problema de decisión pertenece a NP.
Para el problema habitual de decidir si existe una solución, la descripción más fuerte NP-completo es adecuada en el resultado citado. Los trabajos que hablan de resolución de forma más amplia suelen utilizar NP-hard como término paraguas más seguro.
¿La unicidad hace que el problema sea más fácil?
No automáticamente.
Un puzle que sabemos que tiene una sola solución todavía puede ser difícil de resolver. Decidir si existe otra solución está además estrechamente relacionado con problemas difíciles de «otra solución» estudiados en teoría de complejidad.
Para el uso editorial, la conclusión práctica es más sencilla:
único, resoluble por humanos y fácil son tres afirmaciones diferentes.
Por qué los solvers informáticos funcionan bien de todas formas
La dificultad en el peor caso no impide tener algoritmos prácticos muy potentes.
Los solvers aprovechan:
- propagación de restricciones a nivel de línea;
- programación dinámica o filtrado de patrones;
- planificación inteligente de líneas modificadas;
- caché;
- comprobaciones de contradicción;
- heurísticas de ramificación;
- probing;
- tecnologías generales de resolución de restricciones.
Las colecciones reales de puzles contienen además mucha más estructura que las instancias teóricas adversarias.
Como resultado, un solver puede procesar rápidamente muchos puzles grandes diseñados para personas aunque no exista una garantía en tiempo polinómico para el caso general.
Por qué esto importa para el diseño de puzles
Los resultados de complejidad no son solo curiosidades abstractas.
Explican por qué un generador necesita validación en lugar de asumir que cualquier conjunto de pistas se comportará bien. Un candidato puede ser:
- inconsistente;
- ambiguo;
- único pero dependiente de mucha búsqueda;
- único y con una resolución fluida.
Por eso los sistemas de construcción combinan generación con comprobaciones mediante solver y estimaciones de dificultad.
Errores habituales
«NP-completo significa que nadie puede resolver nonogramas eficientemente»
No. Significa que no se conoce un algoritmo en tiempo polinómico para todas las instancias y que encontrar uno tendría consecuencias enormes para la teoría de complejidad.
«Una cuadrícula mayor es exponencialmente difícil por definición»
No. El tamaño amplía el espacio de búsqueda posible, pero una estructura de pistas concreta puede hacer sencilla incluso una instancia grande.
«Si un puzle se resuelve sin adivinar, los nonogramas no pueden ser NP-hard»
Pueden existir subclases fáciles dentro de un problema general difícil. Los puzles publicados suelen seleccionarse precisamente de esas regiones más amigables.
«NP significa no polinómico»
No. NP es el nombre de una clase de complejidad; normalmente se caracteriza por soluciones que pueden verificarse en tiempo polinómico.
Qué aprender después
Para entender los algoritmos que hacen posible la resolución práctica, lee Cómo funcionan los solvers informáticos de nonogramas. Para los bloques combinatorios detrás de las posibilidades de línea, lee Nonogramas y matemáticas.
Preguntas frecuentes
¿Los nonogramas son NP-completos?
La forma estándar de decisión del problema general tiene resultados de NP-completitud en la literatura. Al hablar de resolución de forma más amplia también se resume a menudo como NP-hard.
¿Eso demuestra que todos los puzles necesitan adivinar?
No. Muchos nonogramas publicados están diseñados deliberadamente para resolverse mediante deducciones lógicas locales y propagación.
¿Puede un ordenador resolver nonogramas difíciles?
Sí. NP-completitud no impide resolver instancias individuales de forma efectiva; impide disponer de una garantía eficiente conocida para todas las instancias bajo los supuestos estándar de complejidad.