Los nonogramas tienen un conjunto de reglas pequeño y una estructura sorprendentemente rica.
El jugador ve filas, columnas, números, casillas rellenas y marcas X. Debajo de esa interfaz hay un problema binario de restricciones: cada línea debe coincidir con una descripción ordenada de longitudes de bloque, mientras cada casilla debe satisfacer al mismo tiempo su fila y su columna.
Eso plantea preguntas más profundas que «¿qué casilla marco ahora?»:
- ¿Cómo se generan las pistas a partir de una imagen?
- ¿Cómo sabemos que un puzle tiene exactamente una solución?
- ¿Por qué dos puzles del mismo tamaño pueden sentirse completamente distintos en dificultad?
- ¿Cuántos patrones legales puede tener una sola línea de pistas?
- ¿Cómo reproduce un solver informático la lógica de líneas y la propagación?
- ¿Por qué algunas instancias de nonogramas son computacionalmente difíciles aunque muchos puzles publicados sean fáciles para una persona?
La sección de Teoría de VeyraPlay explora estas preguntas sin exigir matemáticas avanzadas al lector.
Los nonogramas como sistema de restricciones
Un nonograma monocromo estándar puede modelarse con estados binarios de casilla:
- rellena;
- vacía.
El estado desconocido existe durante la resolución, pero una solución terminada asigna a cada casilla uno de los dos estados finales.
Cada pista de fila restringe los patrones binarios permitidos para esa fila. Cada pista de columna hace lo mismo en vertical. Como una casilla pertenece simultáneamente a una fila y a una columna, ambos conjuntos de restricciones interactúan.
Una técnica humana como el solapamiento identifica un estado de casilla compartido por todas las colocaciones relevantes. Un solver de líneas puede generalizar la misma idea considerando todos los patrones válidos bajo las restricciones actuales y conservando los estados en los que todos coinciden.
Cómo se crean los nonogramas
La dirección de construcción más sencilla parte de una imagen final de casillas rellenas y vacías.
Para cada fila y columna:
- se recorren los estados finales de las casillas;
- se mide cada bloque consecutivo de casillas rellenas;
- se registran esas longitudes de bloque en orden;
- las secuencias resultantes se usan como pistas del puzle.
Ese proceso genera las pistas, pero no garantiza por sí mismo un buen puzle.
El creador también puede necesitar comprobar:
- que exista al menos una solución;
- que la solución sea única;
- que el recorrido de resolución previsto sea adecuado;
- que la imagen final sea reconocible y visualmente limpia.
Crear tu propio puzle
La construcción manual añade decisiones de diseño antes y después de generar las pistas.
Hay que elegir una cuadrícula y dibujar una imagen que funcione a esa resolución; después se derivan las pistas y se valida el resultado. Cambios visuales minúsculos pueden modificar no solo la imagen, sino también la estructura lógica de varias pistas de fila y columna.
Una imagen bonita no se convierte automáticamente en un nonograma satisfactorio. La calidad del puzle depende de la relación entre el diseño visual y la estructura de restricciones.
Soluciones únicas y ambigüedad
Un conjunto de pistas puede tener:
- ninguna solución;
- exactamente una solución;
- más de una solución.
Son estados matemáticos distintos.
En un puzle lógico convencional, una solución final única suele ser un objetivo básico de calidad. Pero la unicidad también es distinta de cómo puede encontrarse esa solución. Un puzle puede tener una sola solución y aun así requerir razonamientos más profundos que las técnicas locales habituales de línea.
Esta distinción es esencial siempre que hablamos de dificultad.
Por qué la dificultad no depende solo del tamaño
Una cuadrícula mayor contiene más casillas, pero el tamaño por sí solo no indica lo difícil que será el recorrido lógico.
La dificultad depende de factores como:
- lo restringidas que estén las líneas iniciales;
- cuánta holgura tengan las secuencias de pistas;
- con qué frecuencia una deducción sencilla desbloquea líneas cruzadas;
- si el puzle exige asignar segmentos o analizar patrones completos de línea;
- si el progreso necesita propagación en varios pasos;
- si bajo el modelo de resolución elegido acaba siendo necesario usar contradicción o búsqueda.
Por eso una clasificación de dificultad solo tiene sentido en relación con un modelo de operaciones de resolución permitidas o con el comportamiento observado de jugadores reales.
Las matemáticas detrás de las pistas
Una secuencia de pistas contiene longitudes de bloques ordenadas y restricciones obligatorias de separación.
Para m bloques monocromos, la extensión mínima es:
sum(clues) + (m - 1)El espacio no utilizado es la holgura. En una línea completamente desconocida, distribuir esa holgura entre los espacios disponibles genera un conjunto combinatorio de colocaciones legales.
Esas colocaciones no son independientes en toda la cuadrícula, porque cada patrón de fila debe ser compatible con cada patrón de columna en sus intersecciones.
Esta conexión entre simples pistas de longitudes de bloque y un sistema binario de restricciones interdependientes es el núcleo matemático del puzle.
Cómo funcionan los solvers informáticos de nonogramas
Un solver no necesita «ver la imagen». Puede trabajar únicamente con restricciones.
Una arquitectura típica repite:
- calcular o reducir los patrones legales de una línea;
- identificar estados de casilla compartidos por esos patrones;
- registrar las casillas forzadas;
- volver a procesar las líneas cruzadas afectadas por los cambios;
- continuar hasta que no quede progreso directo.
Si la resolución de líneas alcanza un punto fijo, los solvers más potentes pueden añadir probing, supuestos controlados, backtracking, métodos de tipo SAT/CSP u otras técnicas de búsqueda.
La conexión importante con la resolución humana es que el análisis de líneas más la propagación ya explican una gran parte de la lógica habitual de los nonogramas.
Por qué importa la complejidad computacional
Decir que el problema general de los nonogramas contiene casos difíciles en el peor escenario no significa que todos los puzles que abras sean difíciles.
La teoría de complejidad pregunta qué puede ocurrir en familias amplias de entradas a medida que crecen el tamaño y la estructura del puzle. Los puzles publicados son objetos seleccionados deliberadamente, normalmente diseñados para que las deducciones amigables para humanos produzcan un recorrido satisfactorio.
Por tanto, ambas afirmaciones pueden ser ciertas:
- muchos nonogramas corrientes se resuelven eficientemente repitiendo razonamiento local;
- el problema computacional general admite instancias en las que encontrar o decidir una solución resulta mucho más difícil.
La guía de complejidad explica esta distinción sin utilizar NP-completo como sinónimo de «este puzle concreto se siente difícil».
La resolución humana y la informática están relacionadas, pero no son idénticas
Los nombres de técnicas humanas empaquetan demostraciones recurrentes en patrones reconocibles y útiles. Los solvers informáticos pueden representar las mismas restricciones de otra manera.
Por ejemplo:
- una persona ve solapamiento;
- un algoritmo puede intersectar todos los patrones válidos;
- una persona vuelve a escanear una columna cruzada;
- un solver vuelve a colocar esa línea en una cola de procesamiento;
- una persona usa razonamiento por contradicción;
- un solver puede probar temporalmente un estado o abrir una rama en un árbol de búsqueda.
La lógica subyacente puede estar muy relacionada aunque cambien la interfaz y el vocabulario.
Lo que la teoría no nos dice automáticamente
La teoría puede decirnos que un conjunto de pistas tiene varias soluciones o que un modelo de resolución determinado se atasca. No puede definir por sí sola si un puzle es divertido, elegante, visualmente atractivo o apropiado para una audiencia concreta.
Esos son juicios editoriales y de producto que pueden usar señales matemáticas sin reducirse a una sola fórmula.
Esto importa para VeyraPlay porque los futuros generadores y sistemas de dificultad no deberían presentar como clasificación universal objetiva lo que en realidad es un modelo elegido.
Por dónde continuar
Quiero saber cómo se producen las pistas. Lee Cómo se crean los nonogramas.
Quiero diseñar uno por mi cuenta. Lee Cómo crear tu propio nonograma.
Quiero entender la unicidad. Lee Soluciones únicas y nonogramas ambiguos.
Quiero entender la dificultad. Lee Cómo se clasifica la dificultad de un nonograma.
Quiero la base combinatoria. Lee Nonogramas y matemáticas.
Quiero la perspectiva algorítmica. Lee Cómo funcionan los solvers informáticos de nonogramas y Por qué los nonogramas son computacionalmente difíciles.