积木拼图也可以让计算机来解。这篇文章介绍最基本的解法。

思路:从左上角的空格开始

计算机会重复下面的步骤。

  1. 在框里找最左上角的空格(从上面的行开始,从左往右看)。
  2. 把还没用过的拼块一块块拿来,各种旋转朝向都试一遍,检查能不能覆盖那个格放下去。
  3. 放得下,就进入下一个空格(回到1)。
  4. 如果哪块拼块都放不下了,就把前一块放下的拼块取下来,试下一个候选。
  5. 没有空格了,就找到了答案。

最左上角的空格,一定会被某块拼块的最左上角的格子覆盖。所以,只要试把拼块的左上角格对准那里的放法就够了,不用试其他位置。

上图里,放下第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种五连块的答案数量请看五连块的答案。