積木拼圖也可以讓電腦來解。這篇文章介紹最基本的解法。

想法:從左上的空格開始

電腦會重複下面的步驟。

  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;
}

把 4×5 的框,與 P、T、L、S、3 格的 L 這 5 塊拼塊交給 solve,會回傳 8。也就是說,解法的文章的例題,包含旋轉的方向在內,共有 8 種解答。

及早退回的巧思

上面的程式碼,會一直前進到拼塊放不下為止。但是,在出現被封住的小空隙的那一刻,就能知道前面沒有答案了。

每放一塊拼塊,就檢查空格塊的大小,一旦出現剩下的拼塊做不出來的大小的塊,就馬上退回去。光是這樣,要搜尋的數量就大幅減少。

把 12 種五格骨牌塞進 3×20 長方形的解答全部數過時,加入這個巧思之前,花了 10 分鐘還沒結束。加入之後,大約 6 秒就結束了(這是寫本站文章時的計算,時間會因電腦而異)。

App「提示」的運作方式

App「積木拼圖」的「提示」,也是使用同樣的深度優先搜尋。

  • 只試覆蓋編號最小的空格的放法。
  • 旋轉後能重合的相同形狀拼塊,只試一個。
  • 如果出現比拼塊還小的封閉空隙,就退回去。
  • 為檢查的局面數設定上限,避免花太多時間。

如果照目前的放法填得滿,就會讓覆蓋最難填空格的拼塊與放法發光。如果填不滿,就會和最初做出的答案比對,讓不吻合的拼塊發光,並顯示「把發光的拼塊拿下來,就能順利完成」。

題目的做法在一定能解開的題目是怎麼做的,12 種五格骨牌的解答數量則在五格骨牌的解答裡介紹。