タイルを敷き詰めるパズル：欠けたマスがあると敷けない理由

この実験で確かめる問い

確かめる問いは二つです。

1. 白と黒のマス数が違う盤は、ドミノで敷けないと言い切れるか。
2. 白と黒のマス数が同じ盤は、必ず敷けるか。

1は理屈で説明がつきます。2は逆向きの話で、成り立つかどうかは自分で盤を作って確かめる価値があります。ゲームの盤面を作る立場からすると、2の答えは大きな意味を持ちます。色の数を数えるだけで「解ける盤」の保証になるなら、検査は一瞬で済みます。そうでなければ、別の検査が必要になります。

準備するものと記録表

用意するものは次のとおりです。

• 4×4の方眼を描いた紙（盤3枚分）、または表計算ソフトのシート
• 色鉛筆か塗りつぶし機能（白黒の塗り分け用）
• ドミノに見立てる「隣り合う2マス」を書き込む鉛筆
• タイマー（盤ごとに3分を上限にします）
• 後述のHTMLを保存するテキストエディタとブラウザ

マスの位置は「(行,列)」で表します。行は上から1、列は左から1と数えます。「行＋列が偶数のマスを白、奇数のマスを黒」と決めると、左上の(1,1)が白になります。これが塗り分けの規則です。

用意する3枚の盤は次のとおりです。「#」が欠けたマス、「.」が使えるマスです。

• 盤A：(1,1)と(4,4)を欠く。対角の2隅です。

#...
....
....
...#

• 盤B：(1,1)と(1,2)を欠く。隣り合う2マスです。

##..
....
....
....

• 盤C：(1,2)、(2,1)、(3,3)、(4,4)の4マスを欠く。

.#..
#...
..#.
...#

記録表は次の形で作ります。

• A、使えるマス数：、白の数：、黒の数：、予想（敷ける／敷けない）：、手で3分試した結果：、プログラムの敷き方の数：
• B、使えるマス数：、白の数：、黒の数：、予想（敷ける／敷けない）：、手で3分試した結果：、プログラムの敷き方の数：
• C、使えるマス数：、白の数：、黒の数：、予想（敷ける／敷けない）：、手で3分試した結果：、プログラムの敷き方の数：

手順

1. 先に数えて、予想を書く

盤を描いたら、まだ敷こうとしないでください。最初にすることは二つです。

1. 欠けたマスを塗りつぶし、残りのマスを上の規則で白黒に塗り分けます。
2. 白と黒の数を数え、記録表に書き込みます。

次に、数を見たうえで「敷ける／敷けない」の予想を書きます。予想の理由も一行添えてください。たとえば「白黒が同数だから敷けると思う」のように書きます。結果を知ってから予想を書くと、後で何も学べなくなります。

2. 手で敷く

盤ごとに3分を上限にして、ドミノを鉛筆で描き込みます。次の記録を取ってください。

• 全マスを覆えたか。覆えた場合は配置を写真か図に残します。
• 覆えなかった場合、最後に残ったマスの位置と、試した並べ方の数（おおよそで構いません）。

「3分で敷けなかった」ことは「敷けない」の証拠になりません。この区別は、次の手順で使います。

3. プログラムで全探索する

次のHTMLをdomino.htmlとして保存し、ブラウザで開きます。白黒の数を数えたうえで、ドミノの敷き方を全部数え上げます。

<!doctype html>
<meta charset="utf-8">
<pre id="out"></pre>
<script>
const rows = [".#..", "#...", "..#.", "...#"]; // #が欠け
const g = rows.map(r => [...r].map(c => c === "#"));
let white = 0, black = 0;
g.forEach((row, r) => row.forEach((hole, c) => {
  if (!hole) { if ((r + c) % 2 === 0) white++; else black++; }
}));
function count() {
  for (let r = 0; r < g.length; r++) {
    for (let c = 0; c < g[r].length; c++) {
      if (g[r][c]) continue;
      let n = 0;
      for (const [dr, dc] of [[0, 1], [1, 0]]) {
        const rr = r + dr, cc = c + dc;
        if (rr < g.length && cc < g[rr].length && !g[rr][cc]) {
          g[r][c] = g[rr][cc] = true;
          n += count();
          g[r][c] = g[rr][cc] = false;
        }
      }
      return n;
    }
  }
  return 1;
}
out.textContent = "白 " + white + " / 黒 " + black +
  " / 敷き方 " + count() + " 通り";
</script>

仕組みは単純です。左上から順に最初の空きマスを探し、そのマスを右か下のマスと組にしてドミノを置き、残りで再帰的に続けます。最初の空きマスより前は必ず埋まっているので、同じ敷き方を二重に数えることがありません。

使い方は、rowsの4行を盤A・B・Cの文字に差し替えるだけです。動作確認として、全部を"..", ".."の2×2にすると、結果は2通りになります。縦に2枚並べる方法と、横に2枚並べる方法があるためです。ここが合わないときは、コードの写し間違いを疑ってください。

結果の読み方

記録表が埋まったら、次の基準で読みます。

白と黒の数が違う盤の場合。 ドミノは隣り合う2マスを覆うので、必ず白と黒を1つずつ覆います。そのため、数が違う盤は敷けないと断定できます。手で「敷けた」と記録していたなら、数え間違い、ドミノの重なり、斜め置きのいずれかが紛れ込んでいます。配置の図を見直してください。

白と黒の数が同じ盤の場合。 色の数が合うことは、敷けるための必要条件にすぎず、十分条件ではありません。プログラムが0通りと答える盤が、この中にあるかどうかを記録表で確認してください。あったなら、その盤で何が起きているかを探します。次の手がかりが役立ちます。

• 隣り合う空きマスが一つもない孤立マスはないか。
• 欠けたマスに囲まれて、他と切り離された小さな領域はないか。そのような領域の中だけで、白と黒の数は合っているか。

この二つ目の点検は、とても有用です。盤全体では白黒が同数でも、切り離された領域ごとに数えると食い違う場合があります。領域ごとに数える検査を足すと、色の数の判定が一段強くなります。

手の結果とプログラムが食い違った場合。 手で3分間敷けなかった盤が、プログラムでは1通り以上と出ることがあります。その盤は敷けるのに、手で見つけられなかっただけです。逆に、色の数が違うのに手で「敷けた」としたなら、手のほうを疑います。

起こりやすい誤り

• 色の塗り分けの崩れ。 市松模様で一マスずれると、数がすべて狂います。規則は「行＋列が偶数なら白」の一本に固定してください。
• 座標の混同。 行と列を入れ替えて欠けを描くと、別の盤になります。盤を描いた後、欠けた位置を声に出して読み合わせると防げます。
• 「敷けなかった」の言い切り。 手で敷けなかっただけで不可能と結論するのは誤りです。不可能と言えるのは、色の数の食い違いのような理屈があるときか、全探索で0通りと出たときだけです。
• プログラムの盤面の写し間違い。 rowsの各行は同じ長さにしてください。長さが揃っていないと数え方が狂います。
• 予想の後書き。 数えてから予想を書くのは構いません。ただし敷く前に書き終えてください。

ゲームの盤面づくりに持ち帰る

この実験から、タイリング系のパズルを作るときの検査の順序が見えてきます。

1. 使えるマスの総数が偶数か（ドミノの場合）。
2. 白と黒の数が同数か。
3. 孤立マスがないか、領域ごとに白黒が合っているか。
4. 上記を通った盤だけ、全探索で実際に敷けるか確かめる。

1〜3は盤を一度なぞるだけで終わり、軽い検査です。4は盤が大きくなると重くなるので、軽い検査で先に弾いておく価値があります。ただし、1〜3を通っても敷けない盤は残ります。たとえば、離れた二つの領域がそれぞれ横3マスの一列で、全体では白黒が同数になる盤などです。4を省略すると、解けない盤を遊び手に出すおそれがあります。

「解けない」ことを知っていると、パズルの設計に使えます。欠けたマスが遊び手に与えるのは、「どこに置いても最後に一マス余る」という手触りです。その手触りを意図して残すのか、避けるのか。数の側から先に決めておけば、盤の作り方を選べます。

次の行動

まず盤Aを紙に描き、白黒に塗り分けて、数を数える前に予想を書いてください。次に盤B・Cで同じ手順を繰り返し、記録表をプログラムの結果と照らし合わせます。そして、自分で作った盤を一枚加え、領域ごとに数える検査を紙の上で試してみてください。タイリングのパズルが形になったら、index.htmlを入口にしたHTMLとしてアソバースへ投稿し、遊んでもらうことができます。