Resolución de nonogramas
Algoritmos
Para mi, escribir programas que resuelvan juegos o pasatiempos me parece una forma muy entretenida de implementar algoritmos. Incluso sabiendo resolver este tipo de juegos, no siempre es sencillo describir cómo funcionan los algoritmos que usamos, en los que a menudo interviene la intuición, si no a la hora de desarrollar el procedimiento, sí al menos a la hora de optimizarlo.
Como veremos en este caso, a veces esas optimizaciones intuitivas dificultan descubrir el algoritmo principal. Pero cuando programamos un algoritmo no siempre nos interesan las optimizaciones, o al menos no desde el principio, y es mejor dejarlas para una fase posterior en la elaboración del programa final.
El juego
Pero empecemos por describir qué es un nonograma.
Se trata de un juego que suele incluirse en revistas de pasatiempos, como los crucigramas, sopas de letras o sudokus.
Consiste en una cuadrícula y el objetivo es descubrir para cada casilla si se debe rellenar o no. El resultado suele ser un dibujo o figura, más o menos detallado. Para resolverlo se proporcionan ciertas pistas: para cada fila y columna se da una lista de números. Cada uno de esos números indica un número de casillas consecutivas que se debe rellenar. No se da información de las casillas sin rellenar, pero sabemos que entre cada tramo debe haber al menos una.
Por ejemplo, si la cuadrícula tiene diez casillas de ancho, y para una de las filas nos dan como pista la lista 5, 4, el resultado será cinco casillas rellenas, una vacía y cuatro rellenas.
Resolver una fila o columna cuando las pistas sólo permiten una combinación es sencillo. La cosa se complica cuando hay más de una combinación. Por ejemplo, para la misma cuadrícula, una lista que consista en un único valor, 3, o con valores como 2, 1, 1; no nos permite marcar ninguna casilla. Aquí es donde comienzan las dificultades y la parte entretenida del juego, ya que tendremos que combinar casillas marcadas por pistas de distintas filas y columnas.
Resolución
Para resolver el juego aplicaremos el mismo algoritmo para cada fila y columna tantas veces como sea necesario.
En el ejemplo de la derecha empezaremos por las filas, y continuaremos con las columnas, y si no queda resuelto, volveremos a empezar. En cada iteración deberíamos tener más casillas marcadas como rellenas o como vacías, de modo que tendremos nuevas restricciones a la hora de aplicar el algoritmo.
Una primera aproximación que se me ocurre para el algoritmo es generar todas las posibles combinaciones de las pistas, y quedarnos con las casillas para las que en todas las combinaciones tengamos el mismo valor, ya sea marcada o sin marcar.
Por ejemplo, para la primera fila tenemos las pistas 5,5. Existen quince posibles combinaciones en las que se pueden colocar esos dos grupos de casillas:
XXXXX+XXXXX++++ XXXXX++XXXXX+++ XXXXX+++XXXXX++ XXXXX++++XXXXX+ XXXXX+++++XXXXX +XXXXX+XXXXX+++ +XXXXX++XXXXX++ +XXXXX+++XXXXX+ +XXXXX++++XXXXX ++XXXXX+XXXXX++ ++XXXXX++XXXXX+ ++XXXXX+++XXXXX +++XXXXX+XXXXX+ +++XXXXX++XXXXX ++++XXXXX+XXXXX
En este caso, para las columnas 5 y 11, en todas las combinaciones la casilla está marcada, para el resto de columnas siempre hay al menos una combinación con un valor diferente. Por lo tanto podemos poner una marca en esas dos casillas.
Para la segunda fila tenemos sólo una pista: 11, tendremos por lo tanto cinco combinaciones:
XXXXXXXXXXX++++ +XXXXXXXXXXX+++ ++XXXXXXXXXXX++ +++XXXXXXXXXXX+ ++++XXXXXXXXXXX
En este caso para las columnas 5 a 11, para todas las combinaciones, la casilla está marcada, así que podemos poner una marca en todas ellas.
Con el casillero vacío parece relativamente sencillo generar todas las combinaciones, pero a medida que vayamos determinando el contenido de algunas casillas, las combinaciones posibles se verán limitando.
Al terminar la primera iteración de todas las filas, el casillero tendrá la configuración de la derecha:
Veamos, por ejemplo, qué sucede con la sexta columna, para la que tenemos las pistas 2, 6, y las filas segunda, quinta, sexta, séptima y octava marcadas:
-1--1111------- --------------- 000000110111111 * 000001100111111 * 000011000111111 * 000110000111111 * 001100000111111 * 011000000111111 * 110000000111111 * 000001101111110 * 000011001111110 * 000110001111110 * 001100001111110 * 011000001111110 * 110000001111110 * 000011011111100 * 000110011111100 * 001100011111100 * 011000011111100 * 110000011111100 * 000110111111000 * 001100111111000 * 011000111111000 * 110000111111000 * 001101111110000 * 011001111110000 * 110001111110000 * 011011111100000 110011111100000 110111111000000
Ahora tenemos veintiocho combinaciones, pero las marcadas con asterisco no son válidas, ya que contienen casillas vacías en alguna de las posiciones donde sabemos que deben estar marcadas. Esto nos deja sólo tres combinaciones:
-1--1111------- --------------- 011011111100000 110011111100000 110111111000000 --------------- -1--11111-00000
Ahora podemos añadir marcas a la casilla novena, pero también podemos marcar como vacías las cinco últimas casillas.
Esto último es importante, y tenemos que tener en cuenta que cada casilla puede estar en uno de tres estados: indeterminado, al iniciar el juego, marcada o vacía. El estado vacío e indeterminado no son equivalentes, y las casillas marcadas y vacías generan restricciones a la hora de elegir o descartar combinaciones de pistas.
Algoritmo
Bien, generalicemos. Para resolver el juego usaremos el siguiente algoritmo:
- Repetir mientras haya alguna casilla indeterminada
- Para cada fila
- Generar todas las combinaciones de las pistas
- Eliminar las combinaciones que no se ajusten al estado del casillero
- Asignar el estado "marcado" a las casillas que estén marcadas en todas las combinaciones
- Asignar el estado "vacío" a las casillas que estén vacías en todas las combinaciones
- Para cada columna
- Generar todas las combinaciones de las pistas
- Eliminar las combinaciones que no se ajusten al estado del casillero
- Asignar el estado "marcado" a las casillas que estén marcadas en todas las combinaciones
- Asignar el estado "vacío" a las casillas que estén vacías en todas las combinaciones
Generar combinaciones de pistas
Ya tenemos un algoritmo general para resolver el juego, ahora veamos cómo generar todas las posibles combinaciones de un conjunto de pistas.
Cada conjunto de pistas estará definido por p números, cada uno de ellos con un valor vi.
En total ocuparán k casillas, donde k será la suma de los vi más (p-1). Por ejemplo, para las pistas 1, 3, 5, p es 3, y k es 11, que son las casillas mínimas necesarias para almacenar esas pistas: X·XXX·XXXXX.
Eso deja ancho-k casillas casillas a repartir entre las posibles separaciones entre cada par de pistas. Llamaremos a ese valor r. En nuestro ejemplo,r=15-11, es decir 4.
Existen n=p+1 lugares donde colocar esas h casillas vacías: antes de la primera pista, entre cada dos pistas y después de la última. En cada uno de esos lugares puede haber entre 0 y r casillas vacías, una más en el caso de huecos entre pistas.
Como curiosidad, aunque no aporta mucho al método, para calcular el número de combinaciones tenemos que recurrir a la fórmula de combinaciones con repetición.
Para calcular el número de combinaciones con repetición de n elementos tomados de r en r, esto es: todos los conjuntos posibles no ordenados de r elementos que se pueden formar a partir de un conjunto de n, la fórmula es:
Esa es la fórmula general, pero en nuestro caso n es igual a p+1, por lo tanto, podemos simplificar sustituyendo n-1 por p:
Veamos un par de ejemplos.
Más arriba mostramos las combinaciones para las pistas 2,6 en una fila de 15 casillas. En este caso r vale 15-(2+6+p-1), es decir 6. Y n vale p+1, es decir, 3. Esto es, sobran 6 casillas huecas que deberemos repartir en 3 posiciones diferentes.
Otro ejemplo, tomemos las pistas 2, 3 y 5, para un casillero de 15 casillas. p es 3, y n es 15-(2+3+5+p-1)=3. Por lo tanto, el número de combinaciones será:
Pero lo que nos importa no es tanto el número de combinaciones posibles como el modo de generarlas.
Para ello nos apoyaremos en una lista de pistas pero para las longitudes de las separaciones, que indicarán cómo repartir las casillas huecas huecas sobrantes en las separaciones de las casillas correspondientes a las pistas originales. Para un conjunto de p pistas tendremos que repartir las r casillas entre las p+1 separaciones.
Por ejemplo, para las pistas 1, 3, 5, en 15 casillas, tendremos que generar una lista de grupos de tres valores cuya suma sea 4, que es el valor de r:
4 0 0 3 1 0 2 2 0 1 3 0 0 4 0 3 0 1 2 1 1 1 2 1 0 3 1 2 0 2 1 1 2 0 2 2 1 0 3 0 1 3 0 0 4
Para generar cada combinación posible partiremos de la combinación maestra trivial, es decir, la que se forma dejando sólo una casilla de separación entre cada conjunto de marcas indicados por las pistas. Por ejemplo, para las pistas 1, 3, 5, la combinación inicial será X·XXX·XXXXX.
Ahora sólo tenemos que añadir tantas casillas huecas entre pistas como indique cada grupo. En el ejemplo, para la primera añadiremos cuatro casillas huecas al principio, para la segunda añadiremos un hueco entre la primera y segunda pista y tres al principio, y así sucesivamente.
Pero, ¿cómo generamos esa lista?
Posiblemente, lo mejor será diseñar una función que pueda generar la siguiente combinación a partir de la actual, y que retorne un valor booleano false que indique si la actual es la última, o true si aún es posible generar nuevas combinaciones.
Para ello pasaremos a la función un vector por referencia, con la lista de valores, inicialmente con el valor r en la primera posición, seguido de p ceros.
- indice=0
- Bucle mientras indice < r-1
- Si vector[indice] > 0
- decrementa vector[indice]
- incrementa vector[indice+1]
- Si indice != 0
- vector[0] = vector[indice]
- vector[indice] = 0
- retornar true
- Si vector[indice] == 0 incrementa indice
- Fin de bucle
- retornar false
Empezaremos por el primer elemento. Si no es cero, la función lo decrementará e incrementará el segundo.
Si el elemento decrementado no es el primero, lo moveremos al principio del vector.
Podemos retornar la siguiente combinación.
Si el valor de los primeros r-1 elementos es cero, no quedan combinaciones, y retornamos false.
El código es muy simple:
bool Combinación(std::vector<int> &v) {
size_t indice=0;
while(indice < v.size()-1) {
if(v[indice]>0) {
v[indice]--;
v[indice+1]++;
if(indice != 0) {
v[0] = v[indice];
v[indice] = 0;
}
return true;
} else {
indice++;
}
}
return false;
}
Una vez tenemos la lista de pistas y la de huecos a repartir, conseguir la combinación es sencillo, sólo hay que combinarlas.
Ahora bien, una vez obtenida cada combinación deberemos descartar aquellas que no se ajusten al contenido actual del casillero. Si nuestra combinación tiene marcada alguna casilla que en el casillero esté vacía, o tiene alguna casilla vacía que en el casillero está marcada, no la tendremos en cuenta.
Volvamos al ejemplo de la sexta columna, con las pistas 2, 6, y que tiene el siguiente contenido -1--1111-------. Recordemos que cada casilla puede tener uno de tres estados: indeterminado (-), marcado (1), o vacío (0). Nuestras combinaciones sólo tienen dos: marcado o vacío.
La primera combinación es 000000110111111, que si la comparamos con el contenido:
-1--1111------- 000000110111111
Vemos que en la segunda casilla hay una contradicción, por lo tanto, rechazamos esta combinación.
Lo mismo ocurre con las cuatro siguientes. Con la sexta la contradicción está en la quinta posición:
-1--1111------- 01100000111111
Así procederemos con cada combinación.
Las que se ajusten al contenido previo de las casillas se combinan de modo que obtengamos una plantilla o matriz que sólo deje activas las casillas para las cuales todas las combinaciones válidas tienen los mismos valores: marcados o vacíos. En esa plantilla, las casillas para las que haya valores diferentes en las combinaciones quedarán indefinidas, las que tengan marca en todas las combinaciones quedarán marcadas, y las que estén vacías en todas las combinaciones quedará vacías:
-1--1111------- 011011111100000 110011111100000 110111111000000 --------------- -1--11111-00000
Finalmente podemos traspasar la plantilla directamente a la cuadrícula.
Optimizaciones
Hay que tener en cuenta que el número de combinaciones crece muy rápidamente a medida que el valor de p y r crecen, es decir, a mayor número de pistas y casillas huecas, por ejemplo, para un casillero de 25 casillas, si tenemos como pistas: 1, 1, 1, 1, 1, 1, el número de combinaciones es 27132. Podemos intuir que, por muy bueno que sea nuestro algoritmo de generación, obtener todas las combinaciones y procesarlas puede requerir mucho tiempo y memoria, si no tomamos las medidas oportunas.
Si el casillero fuese muy grande tendríamos que optimizar nuestro algoritmo, y se me ocurren varias maneras.
La primera es descartar las combinaciones que no se ajusten a los valores actuales de las casillas. Si una combinación indica que tenemos que marcar una casilla que actualmente sabemos que está hueca, descartaremos todas las combinaciones en las que esa casilla esté marcada.
La segunda manera es no almacenar todas las combinaciones válidas para posteriormente procesarlas, sino sólo almacenar una combinación que iremos combinando con cada una de las nuevas combinaciones generadas que sean válidas.
Así nuestro algoritmo para cada fila y columna quedará así:
- Obtener el contenido actual del casillero en la fila o columna
- Calcular los valores de r y n, casillas sobrantes y tramos en que repartilos
- Obtener la primera combinación
- Bucle repetir
- Si la combinación es válida, almacenarla
- Obtener la siguiente combinación
- Hasta que no queden combinaciones
- Transferir el resultado al casillero
Por ejemplo, para una fila el código será:
ObtenerContenidoFila(f);
// Calculamos en k las casillas necesarias para almacenar las pistas
k = fila[f].size()-1; // Empezando por las separaciones mínimas entre pistas
for(size_t i=0; i<fila[f].size(); i++) k+=fila[f][i]; // Y sumando las pistas
r = ancho-k; // El valor de r, casillas sobrantes
n = fila[f].size()+1; // El valor de n, pistas+1
// En un vector v almacenamos la primera combinación
v.clear();
v.push_back(r);
for(int i=1; i<n; i++) v.push_back(0);
almacen.clear(); // El acumulado de combinaciones válidas
do {
// Si la combinación actual es válida
if(Valido(fila[f])) {
Almacenar(fila[f]); // La añadimos al almacén
}
} while(Combinacion()); // Siguiente combinación
CopiarContenidoFila(f); // Transferir al casillero
Contingencias
Puede suceder, y tenemos que estar preparados para ello, que el juego no tenga una solución única. En ese caso deberemos evitar entrar en un bucle infinito. Esto es relativamente sencillo de resolver, si en una iteración no se asigna un valor a ninguna casilla, y aún quedan casillas indeterminadas, abandonaremos el bucle indicando que el juego no tiene una única solución.
También puede suceder que no haya ninguna solución. Para detectar estos casos basta con verificar si una casilla debe pasar de marcada a vacía o viceversa. Esto indicará que las pistas de filas y columnas son incompatibles, y el juego no tiene solución.
Una comprobación previa sería sumar las pistas de filas y las de columnas y ver si son iguales. Si no lo fuesen el casillero no sería válido.
He querido mantener el código lo más simple posible, las dimensiones y las pistas forman parte de él, lo que no resulta cómodo si se quieren resolver otros juegos.
Es un programa de consola, así que la salida tampoco es muy elegante.
Programa
| Nombre | Fichero | Fecha | Tamaño | Contador | Descarga |
|---|---|---|---|---|---|
| nonogramas.cpp | nonogramas.cpp.zip | 2025-05-11 | 1548 bytes | 102 |