Cómo creamos niveles de pentominós con Dancing Links

Por Nesim Razon, desarrollador Android independiente · 2026-11-10

Cada nivel de Encajar en Pentolings es una promesa: hay una manera de rellenar esta forma con estas piezas. Para cumplirla en 150 niveles, y para darte una pista en cualquier momento, el juego lleva dentro un pequeño resolutor basado en los Dancing Links de Donald Knuth. Aquí explicamos cómo funciona con un ejemplo diminuto que cualquiera puede seguir.

Un puzle de pentominós es un problema de cobertura exacta

Mira un nivel como una lista de reglas. Cada pieza debe usarse exactamente una vez. Cada cuadro de la forma debe cubrirse exactamente una vez. Nada puede solaparse y nada puede sobrar. Un problema formado por reglas así se llama problema de cobertura exacta, y muchos puzles resultan ser justo eso, desde el sudoku hasta la planificación de horarios.

Para que un ordenador lo resuelva, escribimos el problema como una tabla. Cada columna es una regla: una columna por cada pieza y una columna por cada cuadro de la forma. Cada fila es una jugada posible: una pieza concreta, girada de una manera concreta y colocada en un lugar concreto. La fila marca las columnas que cumple: la columna de la propia pieza y los cinco cuadros que cubriría. El puzle está resuelto cuando eliges filas de modo que cada columna quede marcada exactamente una vez.

63 posiciones: las filas de la tabla

Un pentominó se puede girar y voltear, así que primero el juego lista todas las posiciones distintas de cada una de las doce piezas. Gira y refleja la forma y conserva solo los resultados realmente nuevos. La X da 1 posición, la I da 2, la T, la U, la V, la W y la Z dan 4 cada una, y la F, la L, la N, la P y la Y dan 8 cada una. Eso suma 63 posiciones para todo el conjunto, una cifra que el código comprueba.

Después, para la forma del nivel, desliza cada posición a todos los lugares en que los cinco cuadros quedan dentro de la forma. Para un rectángulo de 3x20 con las doce piezas, eso da 1236 filas candidatas. Para el nivel más grande, un rectángulo de 6x10, hay 2056. La tabla tiene 72 columnas: 12 piezas más 60 cuadros.

Un ejemplo diminuto

Toma un rectángulo de 3x5 y las piezas P, U y V. La tabla tiene 3 columnas de pieza y 15 de cuadro, o sea 18 columnas en total. Las piezas tienen 40, 20 y 12 colocaciones posibles, lo que da 72 filas. Al elegir tres filas que marquen cada columna exactamente una vez sale la respuesta: la V en el borde izquierdo e inferior, la U a la derecha y la P en el centro. En texto, las tres filas del tablero se leen VPPUU, VPPPU y VVVUU. Girar o reflejar todo el rectángulo da cuatro versiones de la misma respuesta, así que el resolutor encuentra cuatro soluciones que a una persona le parecen la misma.

Los Dancing Links de Knuth, en palabras sencillas

La búsqueda es el Algoritmo X. Elige una columna que aún no esté cubierta. Prueba cada fila que la marca. Elegir una fila significa que sus otras columnas ya están ocupadas, así que se puede descartar toda fila que choque con ella. Luego se repite con la tabla más pequeña. Si alguna columna se queda sin filas, es que antes elegiste mal, así que retrocedes y pruebas la siguiente fila.

Lo ingenioso es cómo se guarda la tabla. Donald Knuth observó que las marcas se pueden guardar en listas enlazadas, donde cada marca apunta a su vecina de la izquierda, la derecha, arriba y abajo. Quitar una fila consiste en redirigir unos pocos enlaces, y el elemento quitado sigue recordando dónde estaba, de modo que devolverlo es deshacer los pasos al revés. Como los nodos parecen saltar fuera y volver a entrar, llamó a la técnica Dancing Links, enlaces que bailan. En Pentolings, Dlx.kt tiene unas ochenta líneas y trabaja con matrices de enteros simples para ir rápido.

Un truco más: en cada paso el resolutor elige la columna con menos filas restantes. Si un cuadro solo se puede cubrir de dos maneras, la búsqueda prueba enseguida esas dos en lugar de vagar por la tabla. Es la versión informática de lo que dijimos en la guía: empieza por los sitios estrechos.

Piezas con candado y niveles justos

Algunos niveles de Pentolings empiezan con una pieza con candado. Esas piezas salen de una solución real: el generador encuentra una respuesta y después congela una o dos de sus piezas. El resolutor las trata como ya elegidas, retira sus cuadros y columnas de la tabla y cuenta lo que queda.

Hacer un nivel es más que resolver. Un generador construye un contorno colocando las piezas junto a otras al azar, así que por construcción existe una solución. Después puntúa muchos contornos: premia las formas compactas, penaliza los agujeros, premia la simetría y prefiere formas con más respuestas en los primeros niveles. Como los contornos hechos así suelen tener exactamente una solución, la dificultad viene sobre todo del número de piezas y de lo extraño del contorno. Cada uno de los 150 niveles se vuelve a resolver en las pruebas, se comprueba que no haya duplicados (una copia girada o reflejada cuenta como la misma) y el último nivel, un rectángulo de 6x10, es el único lugar con una cantidad enorme de respuestas. Una prueba también confirma la cifra clásica para 3x20: ocho, que son las dos respuestas verdaderas por las cuatro maneras de girar o reflejar el rectángulo.

¿Por qué no probar todo sin más?

Podrías resolver un puzle probando cada pieza en cada posición, una tras otra, y comprobando al final. Eso no funciona, ni siquiera para un ordenador. Con doce piezas, 63 posiciones y decenas de lugares, el número de combinaciones es astronómico, y casi todas se solapan o dejan huecos en las primeras jugadas.

El truco es detener una rama mala en cuanto se ve que es mala. El Algoritmo X hace exactamente eso. En el momento en que un cuadro se queda sin ninguna pieza que pueda cubrirlo, la búsqueda deja de profundizar y retrocede. Los Dancing Links hacen que cada retroceso salga barato. Por eso un tablero de 6x10, con 2056 colocaciones candidatas, se resuelve deprisa incluso en un teléfono, y por eso el botón de pista no necesita un servidor.

Lo que aprendimos

La misma lógica del resolutor existe dos veces: en Python, donde el generador construye y comprueba el paquete de 150 niveles, y en Kotlin, que va en la aplicación. Las pruebas de Kotlin vuelven a resolver desde cero cada nivel del paquete. Con dos implementaciones independientes, es poco probable que un error en una se esconda de la otra.

La mayor sorpresa fue lo raro que es que un contorno aleatorio tenga más de una respuesta. Esperábamos que muchos puzles tuvieran varias soluciones y encontramos lo contrario. Resulta que no pasa nada: a los jugadores les importa que un nivel sea resoluble y justo, no cuántas soluciones tiene, así que el juego acepta cualquier relleno válido. Lo que nos da el resolutor es la promesa de que se puede confiar en cada nivel y en cada pista.

Las pistas salen del mismo resolutor

El botón Pista le hace al resolutor una pregunta nueva: dadas las piezas que ya colocaste, ¿cómo encaja el resto? Trata tus piezas colocadas como fijas, resuelve lo que falta e ilumina la siguiente pieza de la respuesta que encuentra. Si sigues la pista, la siguiente puede salir de la memoria sin volver a resolver. El trabajo se hace en segundo plano con un límite de tiempo para que la pantalla nunca se congele.

Si tus piezas colocadas hacen imposible una solución, el resolutor no encuentra nada y el juego te lo dice: no hay solución desde aquí, quita una pieza. Así la pista sirve incluso cuando no estás atascado, solo inseguro. Y el juego acepta cualquier manera válida de rellenar la forma, no solo la que halló el generador, de modo que nunca tienes que adivinar la respuesta del autor.