El puzle de bloques también lo puede resolver un ordenador. En este artículo te presentamos el método más básico.
La idea: desde la casilla libre de arriba a la izquierda
El ordenador repite estos pasos.
- Busca en el marco la casilla libre más arriba a la izquierda (mirando desde la fila de arriba, de izquierda a derecha).
- Con cada pieza que aún no se ha usado, probando todas las orientaciones giradas, comprueba si se puede colocar cubriendo esa casilla.
- Si se puede colocar, pasa a la siguiente casilla libre (vuelve al paso 1).
- Si no cabe ninguna pieza, quita la última pieza colocada y prueba la siguiente opción.
- Cuando no quedan casillas libres, ha encontrado una solución.
La casilla libre más arriba a la izquierda siempre queda cubierta por la casilla más arriba a la izquierda de alguna pieza. Por eso basta con probar las colocaciones que hacen coincidir esa casilla de la pieza con ella, y no hace falta probar otras posiciones.
En el diagrama de arriba, después de colocar la primera pieza, la casilla libre más arriba a la izquierda es la de la fila 2, columna 1 (el aro dorado). Ahora se prueban solo las formas de cubrir esa casilla.
Este tipo de búsqueda, que avanza hasta donde puede y, si no sale, vuelve atrás y prueba otro camino, se llama búsqueda en profundidad (o backtracking).
Escrito en JavaScript
El marco se representa con una tabla de true (libre) y false (ocupada), y las piezas con una lista de casillas [fila, columna]. Las casillas de la pieza se ordenan de arriba abajo y, en cada fila, de izquierda a derecha.
// frame: true marks an empty cell. piece: a list of [row, col] cells
function rotate(shape) {
const turned = shape.map(([r, c]) => [c, -r]);
const minR = Math.min(...turned.map(([r]) => r));
const minC = Math.min(...turned.map(([, c]) => c));
return turned
.map(([r, c]) => [r - minR, c - minC])
.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}
function solve(frame, pieces) {
const rows = frame.length;
const cols = frame[0].length;
const used = pieces.map(() => false);
let count = 0;
function search() {
// find the top-left empty cell
let at = -1;
for (let i = 0; i < rows * cols && at < 0; i++) {
if (frame[Math.floor(i / cols)][i % cols]) at = i;
}
if (at < 0) {
count++; // everything is filled
return;
}
const r0 = Math.floor(at / cols);
const c0 = at % cols;
pieces.forEach((piece, p) => {
if (used[p]) return;
let shape = piece;
const seen = new Set();
for (let turn = 0; turn < 4; turn++, shape = rotate(shape)) {
const key = JSON.stringify(shape);
if (seen.has(key)) continue;
seen.add(key);
// line up the shape's top-left cell with the empty cell
const [dr, dc] = shape[0];
const cells = shape.map(([r, c]) => [r - dr + r0, c - dc + c0]);
const fits = cells.every(
([r, c]) => r >= 0 && r < rows && c >= 0 && c < cols && frame[r][c]
);
if (!fits) continue;
cells.forEach(([r, c]) => (frame[r][c] = false));
used[p] = true;
search();
used[p] = false;
cells.forEach(([r, c]) => (frame[r][c] = true));
}
});
}
search();
return count;
} Si pasas a solve el marco de 4×5 y las 5 piezas P, T, L, S y la L de 3 casillas, devuelve 8. Es decir, el ejemplo del artículo sobre cómo resolver tiene 8 soluciones contando las orientaciones giradas.
Volver atrás pronto
El código de arriba sigue avanzando hasta que ya no se puede colocar ninguna pieza. Pero en cuanto aparece un hueco pequeño aislado, ya se sabe que más adelante no habrá solución.
Cada vez que se coloca una pieza, se mira el tamaño de los grupos de casillas libres y, si aparece un grupo de un tamaño que las piezas restantes no pueden formar, se vuelve atrás enseguida. Solo con esto se reduce mucho lo que hay que buscar.
Al contar todas las soluciones de los 12 pentominós en un rectángulo de 3×20, antes de añadir esta idea no terminaba ni después de 10 minutos. Con ella, terminó en unos 6 segundos (es un cálculo hecho al escribir los artículos de este sitio y el tiempo cambia según el ordenador).
Cómo funciona la «Pista» de la app
La «Pista» de Encaja bloques también usa la misma búsqueda en profundidad.
- Prueba solo las formas de cubrir la casilla libre con el número más bajo.
- De las piezas con la misma forma (las que coinciden al girarlas), prueba solo una.
- Vuelve atrás si aparece un hueco aislado más pequeño que una pieza.
- Pone un límite al número de posiciones que examina, para que no tarde demasiado.
Si todavía se puede llenar el marco con la colocación actual, ilumina la pieza y la colocación que cubren la casilla libre más difícil de llenar. Si no se puede, compara con la solución que se creó al principio, ilumina las piezas que no coinciden y avisa con «Quita la pieza que brilla para volver al buen camino».
Cómo se crean los puzles está en cómo se crean puzles que siempre tienen solución, y el número de soluciones de los 12 pentominós en soluciones de los pentominós.
