はめこみパズルは、コンピューターに解かせることもできます。この記事では、いちばん基本的な解き方を紹介します。
考え方:左上の空きマスから
コンピューターは、次の手順をくり返します。
- 枠の中で、いちばん左上の空きマスを探す(上の行から、左から順に見る)。
- まだ使っていないピースを1つずつ、回した向きも全部試して、そのマスを覆うように置けるかを調べる。
- 置けたら、次の空きマスへ進む(1に戻る)。
- どのピースも置けなくなったら、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秒ほどで終わりました(このサイトの記事を書くときの計算で、時間はパソコンによって変わります)。
アプリの「ひらめき」のしくみ
アプリ「はめこみパズル」の「ひらめき」も、同じ深さ優先探索を使っています。
- いちばん番号の小さい空きマスを覆う置き方だけを試す。
- 回して重なる同じ形のピースは、1つだけ試す。
- ピースより小さく閉じこめられたすき間ができたら戻る。
- 調べる局面の数に上限を設けて、時間がかかりすぎないようにする。
今の置き方のまま埋め切れるなら、いちばん埋めにくい空きマスを覆うピースと置き方を光らせます。埋め切れないなら、最初に作った答えと比べて合っていないピースを光らせ、「光っているピースを外すと、うまくいきます」と知らせます。
問題の作り方は必ず解ける問題の作り方、12種類のペントミノの答えの数はペントミノの答えで紹介しています。
