On peut aussi laisser un ordinateur résoudre le puzzle de blocs. Cet article présente la méthode la plus basique.
L’idée : partir de la case vide en haut à gauche
L’ordinateur répète les étapes suivantes.
- Chercher dans le cadre la case vide la plus en haut à gauche (on regarde de la ligne du haut vers le bas, et de gauche à droite).
- Pour chaque bloc pas encore utilisé, dans toutes ses orientations, vérifier s’il peut être posé de façon à couvrir cette case.
- Si on peut le poser, passer à la case vide suivante (retour à l’étape 1).
- Quand plus aucun bloc ne peut être posé, retirer le dernier bloc posé et essayer le candidat suivant.
- Quand il n’y a plus de case vide, on a trouvé une solution.
La case vide la plus en haut à gauche est forcément couverte par la case la plus en haut à gauche d’un bloc. Il suffit donc d’essayer les façons de poser un bloc en faisant coïncider sa case en haut à gauche avec celle-ci : inutile d’essayer les autres positions.
Dans le schéma ci-dessus, une fois le premier bloc posé, la case vide la plus en haut à gauche est en 2e ligne, 1re colonne (l’anneau doré). On essaie ensuite seulement les façons de couvrir cette case.
Cette façon de chercher, qui avance aussi loin que possible puis revient en arrière pour essayer un autre chemin, s’appelle la recherche en profondeur (backtracking).
En JavaScript
On représente le cadre par un tableau de true (case vide) et false (case remplie), et les blocs par une liste de [ligne, colonne] pour leurs cases. Les cases d’un bloc sont rangées de la ligne du haut vers le bas, et de gauche à droite.
// Cadre : true = case vide. Bloc : liste de [ligne, colonne] de ses cases
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() {
// Chercher la case vide la plus en haut à gauche
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++; // Tout est rempli
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);
// Faire coïncider la case la plus en haut à gauche de la forme avec la case vide
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 l’on passe à solve un cadre de 4×5 et les 5 blocs P, T, L, S et L de 3 cases, elle renvoie 8. Cela signifie que l’exemple de l’article sur la résolution a 8 solutions, orientations comprises.
Revenir en arrière plus tôt
Le code ci-dessus avance jusqu’à ce qu’on ne puisse plus poser de bloc. Mais dès qu’un petit trou enfermé apparaît, on sait déjà qu’il n’y aura pas de solution au-delà.
À chaque bloc posé, on vérifie la taille des morceaux de cases vides, et dès qu’il y a un morceau d’une taille que les blocs restants ne peuvent pas former, on revient tout de suite en arrière. Cela suffit à réduire fortement le nombre de recherches.
Quand nous avons compté toutes les solutions des 12 pentaminos dans un rectangle 3×20, le calcul n’était pas fini au bout de 10 minutes avant d’ajouter cette astuce. Avec elle, il s’est terminé en 6 secondes environ (calcul fait pour écrire les articles de ce site ; le temps varie selon l’ordinateur).
Comment fonctionne l’« Indice » de l’appli
L’« Indice » de l’appli Emboîte-blocs utilise aussi la même recherche en profondeur.
- On n’essaie que les façons de couvrir la case vide de plus petit numéro.
- Pour les blocs de même forme (identiques après rotation), on n’en essaie qu’un seul.
- On revient en arrière quand un trou enfermé est plus petit qu’un bloc.
- On fixe une limite au nombre de positions examinées pour que le calcul ne dure pas trop longtemps.
Si le cadre peut encore être rempli tel qu’il est, l’indice fait briller le bloc qui couvre la case vide la plus difficile à remplir, avec sa façon de se poser. S’il ne peut pas l’être, il compare avec la solution créée au départ, fait briller le bloc qui ne correspond pas et affiche « Retirez le bloc qui brille pour repartir sur la bonne voie ».
La création des puzzles est présentée dans créer des puzzles toujours solubles, et le nombre de solutions des 12 pentaminos dans les solutions des pentaminos.
