积木拼图也可以让计算机来解。这篇文章介绍最基本的解法。
思路:从左上角的空格开始
计算机会重复下面的步骤。
- 在框里找最左上角的空格(从上面的行开始,从左往右看)。
- 把还没用过的拼块一块块拿来,各种旋转朝向都试一遍,检查能不能覆盖那个格放下去。
- 放得下,就进入下一个空格(回到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;
} 给 solve 传入4×5的框,以及P、T、L、S和3格的L这5块拼块,会返回 8。也就是说,解法文章里的例题,把旋转朝向算进去,共有8种答案。
尽早退回的技巧
上面的代码会一直走到拼块放不下为止。不过,一旦出现被困住的小空隙,就能知道那之后没有答案。
每放一块拼块,就检查空格块的大小,一旦出现剩下的拼块做不出来的大小的块,就马上退回。光这一点,要搜索的数量就大大减少。
我把12种五连块装进3×20长方形的答案全部数了一遍,在加入这个技巧之前,10分钟过去了也没结束。加入之后,大约6秒就结束了(这是写本网站文章时的计算,时间会因电脑而异)。
应用“提示”的原理
应用“积木拼图”的“提示”,也用了同样的深度优先搜索。
- 只试覆盖编号最小的空格的放法。
- 旋转后能重合的相同形状拼块,只试一块。
- 一旦出现比拼块还小的被困空隙,就退回。
- 给要检查的局面数设置上限,以免花太长时间。
如果按现在的放法能填满,就让覆盖最难填的空格的拼块和放法发光。如果填不满,就和最初生成的答案对比,让对不上的拼块发光,并提示“把发光的拼块取下来,就能顺利完成”。
出题的方法请看一定有解的题目是怎么做出来的,12种五连块的答案数量请看五连块的答案。
