積木拼圖也可以讓電腦來解。這篇文章介紹最基本的解法。
想法:從左上的空格開始
電腦會重複下面的步驟。
- 在框裡找出最左上方的空格(從上面的列開始,由左往右看)。
- 把還沒用過的拼塊一塊一塊拿出來,旋轉後的方向也全部試過,檢查能不能蓋住那一格。
- 放得下的話,就前進到下一個空格(回到 1)。
- 如果每一塊拼塊都放不下,就把前一塊放的拼塊拿掉,試下一個候選。
- 空格都沒有了,就找到答案了。
最左上方的空格,一定會被某一塊拼塊「最左上方的格子」蓋住。所以,只要試把拼塊的左上格對準那裡的放法就好,不需要試其他位置。
上圖中,放好第 1 塊拼塊之後,最左上方的空格是第 2 列第 1 欄(金框)。接下來,只要試覆蓋這一格的放法。
像這樣,走到走不下去為止,不行就退回去試別條路的搜尋方式,稱為深度優先搜尋(回溯法)。
用 JavaScript 寫寫看
用 true(空格)和 false(已填)的表來表示框,用格子的 [列, 欄] 排列來表示拼塊。拼塊的格子,事先由上面的列開始、由左往右排好。
// 框:true 代表空格。拼塊:由各格的 [列, 欄] 排成的陣列
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() {
// 找出最左上方的空格
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++; // 全部填滿了
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);
// 把形狀最左上方的格子,對齊空格
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;
} 把 4×5 的框,與 P、T、L、S、3 格的 L 這 5 塊拼塊交給 solve,會回傳 8。也就是說,解法的文章的例題,包含旋轉的方向在內,共有 8 種解答。
及早退回的巧思
上面的程式碼,會一直前進到拼塊放不下為止。但是,在出現被封住的小空隙的那一刻,就能知道前面沒有答案了。
每放一塊拼塊,就檢查空格塊的大小,一旦出現剩下的拼塊做不出來的大小的塊,就馬上退回去。光是這樣,要搜尋的數量就大幅減少。
把 12 種五格骨牌塞進 3×20 長方形的解答全部數過時,加入這個巧思之前,花了 10 分鐘還沒結束。加入之後,大約 6 秒就結束了(這是寫本站文章時的計算,時間會因電腦而異)。
App「提示」的運作方式
App「積木拼圖」的「提示」,也是使用同樣的深度優先搜尋。
- 只試覆蓋編號最小的空格的放法。
- 旋轉後能重合的相同形狀拼塊,只試一個。
- 如果出現比拼塊還小的封閉空隙,就退回去。
- 為檢查的局面數設定上限,避免花太多時間。
如果照目前的放法填得滿,就會讓覆蓋最難填空格的拼塊與放法發光。如果填不滿,就會和最初做出的答案比對,讓不吻合的拼塊發光,並顯示「把發光的拼塊拿下來,就能順利完成」。
題目的做法在一定能解開的題目是怎麼做的,12 種五格骨牌的解答數量則在五格骨牌的解答裡介紹。
