Los nonogramas usan muy poca aritmética durante la partida, pero por debajo son un problema combinatorio compacto de restricciones.
Cada pista describe bloques ordenados de casillas rellenas en una línea. Las restricciones de filas y columnas se cruzan sobre las mismas casillas, y resolver consiste en encontrar la cuadrícula binaria que satisface todas a la vez.
Las pistas son descripciones de longitudes de bloque
Una secuencia de pistas registra las longitudes de bloques consecutivos de casillas rellenas.
Por ejemplo:
■■■ ×× ■■ × ■
3 2 1Los números no indican dónde empiezan los bloques. Indican:
- sus longitudes;
- su orden;
- que los bloques monocromos vecinos deben estar separados por al menos una casilla vacía.
Por eso una secuencia de pistas es algo más que una suma.
Extensión mínima
Supón que una línea tiene m bloques de pistas con longitudes:
c1, c2, ..., cmLas casillas rellenas ocupan:
c1 + c2 + ... + cmcasillas, y las m - 1 fronteras entre bloques consecutivos exigen como mínimo una casilla vacía cada una.
Por tanto, el espacio más corto capaz de contener todas las pistas es:
extension minima = sum(pistas) + (numero de pistas - 1)Para una línea de 10 casillas con pistas 3 2:
extension minima = 3 + 2 + 1 = 6La línea dispone por tanto de cuatro casillas de libertad extra de colocación.
Ese espacio adicional es la holgura.
¿Cuántas colocaciones puede tener una secuencia en una línea vacía?
En una línea monocroma sin otras restricciones, la holgura puede repartirse:
- antes del primer bloque;
- después del último bloque;
- como casillas vacías extra en cualquiera de los huecos obligatorios entre bloques.
Si hay m bloques y holgura s, el número de colocaciones completas es:
C(s + m, m)donde C es el coeficiente binomial.
Ejemplo: longitud 10 con pistas 3 2
Ya hemos calculado:
extension minima = 6
holgura = 10 - 6 = 4
m = 2Por tanto, el número de patrones completos legales en una línea totalmente desconocida es:
C(4 + 2, 2) = C(6, 2) = 15Este recuento describe la línea inicial sin restricciones. Una vez que algunas casillas están confirmadas como rellenas o vacías, muchos de esos 15 patrones pueden quedar eliminados.
Por qué funciona matemáticamente el solapamiento
Una casilla queda forzada como rellena cuando todos los patrones válidos bajo las restricciones actuales la rellenan.
Del mismo modo, una casilla queda forzada como vacía cuando todos los patrones válidos la dejan vacía.
El solapamiento es un atajo humano rápido para encontrar algunas de esas casillas comunes sin enumerar explícitamente todas las posibilidades.
La técnica más avanzada de patrones de línea válidos hace explícita la misma idea: generar o razonar sobre todo el conjunto de patrones legales y conservar los estados en los que todos coinciden.
Filas y columnas forman restricciones que se intersectan
Una pista de fila por sí sola restringe una cadena binaria horizontal. Una pista de columna restringe una cadena binaria vertical.
Cada casilla pertenece exactamente a una fila y una columna, así que ambos sistemas están acoplados.
Cuando una fila demuestra que una casilla está rellena, ese estado pasa a ser un valor fijo dentro de la columna cruzada. Algunos patrones de esa columna desaparecen. La columna reducida puede forzar otra casilla, que a su vez cambia otra fila.
Esta reducción repetida es propagación de restricciones.
Un nonograma no se resuelve sumando las pistas
Las sumas son útiles para la extensión mínima y para contar ocupación, pero el puzle depende de posiciones y orden.
Dos secuencias de pistas pueden contener el mismo total de casillas rellenas y comportarse de forma muy distinta:
6
3 3
2 2 2Las tres describen seis casillas rellenas, pero sus huecos obligatorios y las identidades de los bloques crean espacios de colocación diferentes.
Por eso «las pistas suman la longitud de la fila» solo basta en casos de encaje exacto en los que se han incluido correctamente los separadores obligatorios.
La combinatoria crece rápidamente
Incluso una línea individual puede admitir muchas disposiciones legales cuando contiene varios bloques pequeños y mucha holgura.
En toda una cuadrícula, las posibilidades de las filas no pueden elegirse de manera independiente porque todas las columnas también deben satisfacer sus pistas.
El puzle es por tanto un sistema de restricciones sobre muchas variables binarias que interactúan, no una colección de ejercicios independientes de colocación de bloques.
Esa interacción es donde pueden aparecer instancias computacionalmente difíciles.
Por qué estas matemáticas ayudan a una persona
No necesitas calcular coeficientes binomiales mientras juegas.
Pero la matemática subyacente explica varias reglas prácticas:
- poca holgura significa menos colocaciones;
- encaje exacto significa una sola colocación;
- solapamiento encuentra casillas comunes a colocaciones extremas o válidas;
- las X eliminan colocaciones candidatas;
- las casillas rellenas restringen qué identidades de bloque pueden alcanzarlas;
- el cruce de información transfiere restricciones entre los dos sistemas de líneas;
- la contradicción demuestra que una rama contiene cero completados válidos.
Las técnicas del resto del corpus son formas pensadas para humanos de aprovechar estas restricciones sin enumerar manualmente todo el espacio de búsqueda.
¿Es un nonograma un puzle matemático?
Es razonable llamarlo puzle de lógica matemática, pero no necesitas matemáticas avanzadas para resolver nonogramas publicados normales.
La mayor parte del juego consiste en:
- contar casillas;
- comparar longitudes;
- conservar el orden;
- eliminar colocaciones imposibles;
- propagar consecuencias.
La combinatoria más profunda resulta especialmente útil al estudiar algoritmos, generadores, dificultad y complejidad en el peor caso.
Qué aprender después
Para una versión práctica de la idea de conjuntos de colocaciones, lee Patrones de línea válidos. Para resolución algorítmica, continúa con Cómo funcionan los solvers informáticos de nonogramas. Para teoría de complejidad, lee Por qué los nonogramas son computacionalmente difíciles.
Preguntas frecuentes
¿Cuál es la fórmula de extensión mínima para las pistas de un nonograma?
En pistas monocromas estándar, suma todos los valores y añade una casilla vacía obligatoria por cada frontera entre bloques consecutivos.
¿La fórmula del número de colocaciones siempre se puede aplicar?
La fórmula sencilla C(s + m, m) se aplica a una línea sin otras restricciones y con separación monocroma estándar. Las casillas conocidas y las asignaciones de segmentos reducen el conjunto.
¿Necesito combinatoria para resolver nonogramas?
No. Las técnicas habituales empaquetan las consecuencias útiles en deducciones visuales mucho más fáciles de aplicar a mano.