Das Legepuzzle kann auch ein Computer lösen. In diesem Artikel zeigen wir das einfachste Verfahren.
Die Idee: vom freien Feld oben links aus
Der Computer wiederholt diese Schritte:
- Im Rahmen sucht er das freie Feld ganz oben links (er geht Zeile für Zeile von oben und in jeder Zeile von links nach rechts).
- Er nimmt jedes noch nicht benutzte Teil, probiert alle Drehungen aus und prüft, ob es sich so legen lässt, dass es dieses Feld bedeckt.
- Lässt es sich legen, geht er zum nächsten freien Feld (zurück zu 1).
- Passt kein Teil mehr, nimmt er das zuletzt gelegte Teil wieder heraus und probiert die nächste Möglichkeit.
- Gibt es kein freies Feld mehr, hat er eine Lösung gefunden.
Das freie Feld ganz oben links wird immer vom Feld ganz oben links irgendeines Teils bedeckt. Es genügt also, nur Legearten zu probieren, bei denen das Feld oben links des Teils auf diesem Feld liegt. Andere Positionen musst du nicht ausprobieren.
Im Bild oben ist nach dem ersten Teil das freie Feld ganz oben links das Feld in der 2. Zeile und 1. Spalte (goldener Ring). Als Nächstes werden nur die Arten probiert, dieses Feld zu bedecken.
Ein Verfahren, das so weit vorgeht, wie es geht, und bei einer Sackgasse zurückgeht und einen anderen Weg probiert, heißt Tiefensuche (Backtracking).
In JavaScript geschrieben
Der Rahmen ist eine Tabelle aus true (frei) und false (belegt), ein Teil eine Liste von [Zeile, Spalte] seiner Felder. Die Felder eines Teils sind von oben nach unten und von links nach rechts geordnet.
// Rahmen: true ist ein freies Feld. Teil: Liste von [Zeile, Spalte] der Felder
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() {
// Das freie Feld ganz oben links suchen
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++; // alles gefüllt
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);
// Das Feld ganz oben links der Form auf das freie Feld legen
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;
} Übergibst du an solve einen 4×5-Rahmen und die fünf Teile P, T, L, S und das L mit 3 Feldern, kommt 8 zurück. Das heißt: Das Beispiel im Artikel zum Lösen hat einschließlich der Drehungen 8 Lösungen.
Früh zurückgehen
Der Code oben geht weiter, bis sich kein Teil mehr legen lässt. Doch sobald eine kleine, eingeschlossene Lücke entsteht, steht schon fest, dass es danach keine Lösung gibt.
Nach jedem gelegten Teil prüft man die Größe der Stücke aus freien Feldern. Entsteht ein Stück, das sich mit den übrigen Teilen nicht bilden lässt, geht man sofort zurück. Allein das senkt die Zahl der Suchschritte stark.
Als wir alle Lösungen für die 12 Pentominos im 3×20-Rechteck gezählt haben, war das Programm vor diesem Kniff nach 10 Minuten nicht fertig. Mit dem Kniff war es nach etwa 6 Sekunden fertig (das ist die Rechnung beim Schreiben der Artikel auf dieser Website, die Zeit hängt vom Computer ab).
So funktioniert der „Tipp“ der App
Auch der „Tipp“ der App Holzpuzzle benutzt dieselbe Tiefensuche.
- Er probiert nur Legearten, die das freie Feld mit der kleinsten Nummer bedecken.
- Von gleichen Formen, die sich durch Drehen decken, probiert er nur eine.
- Entsteht eine eingeschlossene Lücke, die kleiner als ein Teil ist, geht er zurück.
- Die Zahl der geprüften Stellungen hat eine Obergrenze, damit es nicht zu lange dauert.
Lässt sich der Rahmen mit der aktuellen Legeweise noch füllen, lässt er das Teil und die Legeweise leuchten, die das am schwersten zu füllende freie Feld bedecken. Lässt er sich nicht mehr füllen, vergleicht er mit der Lösung, die am Anfang gebaut wurde, lässt ein Teil leuchten, das nicht passt, und meldet: „Nimm das leuchtende Teil heraus, dann klappt es.“
Wie die Rätsel gebaut werden, steht in So entstehen immer lösbare Rätsel, die Zahl der Lösungen für die 12 Pentominos in Pentomino-Lösungen.
