Este artículo de eli.li explora el desafío de generar puzzles de Picross (también conocidos como Nonogramas) que sean lógicamente resolubles, evitando ambigüedades que pueden frustrar al jugador. El problema surge porque las pistas en un Picross solo indican la cantidad de bloques consecutivos en una fila o columna, sin especificar su ubicación exacta. Esto puede llevar a múltiples soluciones válidas, como el ejemplo del “Elementary Switch”, donde una configuración de 2x2 puede interpretarse de dos maneras diferentes.
El autor, creador del juego de puzzles procedurally generated 'bicross', describe cómo abordó este problema. A diferencia de los Picross tradicionales basados en imágenes (donde las ambigüedades son más fáciles de evitar), 'bicross' genera sus puzzles de forma aleatoria. Para asegurar que cada puzzle tenga una única solución, implementó un proceso de tres pasos:
- Generación del nivel: Se crea una cuadrícula aleatoria de booleanos (verdadero/falso) y se filtra para asegurar una densidad adecuada (entre 20% y 70%).
- Propagación de restricciones (Constraint Propagation): Se calculan las pistas (números) a partir de la cuadrícula generada. Luego, se utiliza una función llamada
hasUniqueSolutionpara verificar si la cuadrícula puede reconstruirse únicamente a partir de estas pistas. Esta función simula a un jugador lógico perfecto, utilizando un proceso iterativo que implica:- Generación de Permutaciones: Se calculan todas las posibles disposiciones válidas de bloques para cada fila y columna, basadas en las pistas.
- Intersección: Se combinan estas permutaciones para identificar celdas que deben estar llenas en todas las soluciones válidas.
- Poda (Pruning): Se eliminan las permutaciones que contradicen las restricciones impuestas por las filas o columnas.
- Criterios de aceptación: Si el proceso de poda se detiene sin encontrar una solución única o si detecta ambigüedad (múltiples permutaciones válidas), el nivel se descarta y se genera uno nuevo.
Este proceso, aunque computacionalmente intensivo (generando y descartando 5-10 candidatos por nivel), es sorprendentemente rápido gracias a la simplicidad del algoritmo y las limitaciones de tamaño de la cuadrícula (máximo 10x10). El autor destaca que la eficiencia de este enfoque 'brutish' (fuerza bruta) permite generar puzzles en tiempo real, incluso en dispositivos móviles. La clave es que, a diferencia de los juegos tradicionales, 'bicross' penaliza los errores, por lo que la solvabilidad garantizada es crucial.