ペントミノを長方形に詰める組み方

なにか

ペントミノは、正方形 5 つを辺でつないだ形である。回転と裏返しで重なるものを同じと見ると 12 種類あり、12 枚の面積を合わせると 60 升になる。Dudeney の『The Canterbury Puzzles』（初版 1907 年）に、問題 74「The Broken Chessboard」がある。5 升の片 12 枚と 4 升の片 1 枚で、市松模様の 8 × 8 の盤を組ませる問題である。12 枚はどれも形が違うと本文に書いてある。

60 升の長方形は 6 × 10・5 × 12・4 × 15・3 × 20 の 4 つしかない。ここでは Knuth の『The Art of Computer Programming』第 4 巻の前刷り 5c（2019 年 9 月 11 日版）を前刷りと呼ぶ。前刷りによると、Golomb は 1954 年の論文で 3 × 20 に詰められるかを問い、答えは書かなかった。Hansson がそれより前の 1935 年に解を 1 つ載せていたことも、同じ前刷りが紹介している。6 × 10 の 2339 通りを初めて数え上げたのは Haselgrove 夫妻（1960 年）である。Knuth の論文「Dancing Links」（arXiv:cs/0011047、2000 年）と前刷りの両方がそう書く。夫妻の記事そのものは開けなかった。

2 通りの数え方

詰め方は「12 枚の片」と「60 の升」を、置き方 1 つ（片 1 枚と升 5 つ）でちょうど 1 回ずつ覆う問題として書ける。Knuth はこれを厳密被覆問題と呼び、候補がいちばん少ない項目から枝を張る踊るリンク（Algorithm X）で解いた。1 つ目の数え方はこれを自前で書き、置いた向きのまま全部の解を出した。2 つ目の数え方は、升を短い辺に沿って並べ、まだ埋まっていない最初の升を覆う片を順に試す総当たりである。盤は 60 ビットで持ち、項目の候補を数えることはしない。

置いた向きのまま数えた解は、6 × 10 で 9356、5 × 12 で 4040、4 × 15 で 1472、3 × 20 で 8 だった。箱の回転と裏返しで重なるものを最小の書き方にそろえると、2339・1010・368・2 通りになる。2 通りの数え方で、そろえた解の集合が 1 つ残らず一致した。前刷りの 9356・4040・2339・1010・368 と、3 × 20 の「8 つの解」とも同じである。2 つ目の数え方の探索の節は 3 × 20 で 71,191 個で、前刷りが 20 × 3 の向きの走査で書く 71191 と同じ数だった。1 つ目の数え方の節は 32,978 個で、前刷りの 32,644 個とは少し違う。（2026-09-26 追記）片の項目を前刷りと同じ Conway の文字の順（O・P・Q から Z まで）に並べ替えても、節は 32,978 個のまま変わらなかった。候補が 0 になって引き返した節 23,650 個を数えない数え方でも 32,644 にはならない。差の理由はまだ分からない。

数える前の見立ては「どの解も箱の回転や裏返しで自分に重ならない」だった。半回転で自分に重なる片は箱の中心を含むはずで、それは多くても 1 枚しかない。見立てどおり、向きのままの数はどの箱でもちょうど 4 倍だった。

置き方の数

片 1 枚を箱に置く方法の数は、6 × 10 で 2056、5 × 12 で 1936、4 × 15 で 1696、3 × 20 で 1236 だった。前刷りの表と片ごとに比べると、5 × 12 と 3 × 20 は 12 片とも一致した。6 × 10 は、前刷りが U を 1152 と書く点を除いて 11 片が一致した。U は 152 で、1152 では合計が 2056 にも 2032 にもならない。前刷りが別の所で書く 2032 は、X を左上の 4 分の 1 の 8 か所に限った数で、2056 − 32 + 8 = 2032 になる。

縁に触れる片

6 × 10 の 2339 通りのうち、12 枚すべてが箱の縁に触れるものは 2 通りだった。前刷りによると、これは Potts が 1960 年 2 月 9 日に Gardner へ知らせた結果である。縁に触れる片はいちばん少なくて 8 枚で、そうなる組み方は 207 通りあった。縁に触れない片がちょうど 1 枚の組み方を片ごとに数えると、F 47・I 0・L 3・N 16・P 9・T 8・U 3・V 1・W 30・X 22・Y 5・Z 11 通りになる。どれも前刷りの答えと同じだった。

数える前は「縁に触れない回数がいちばん多い片は X」と見立てた。十字は腕が 4 方向に出ているので、縁に沿わせにくいと考えたからである。2339 通りの中で縁に触れない回数を片ごとに足すと、W が 997 回で最も多く、F が 914 回、X が 875 回と続いた。見立ては外れた。いちばん少ないのは I の 11 回だった。

十字の置き場所

X の中心が来る升で 2339 通りを分けた。箱の対称で左上の 4 分の 1 に寄せると、置き場所は 8 つになる。数える前は「X の中心が箱の真ん中に近いほど組み方が多い」と見立てた。結果は、短い辺に接して上下の真ん中にある升が 442 通りで最も多く、箱のいちばん真ん中の升は 337 通りだった。見立ては外れた。角の升に中心を置くと隅の 1 升が閉じ込められるので、そこは 0 通りになる。8 つを足すと 2339 に戻る。

どの解にも出ない置き方

前刷りは、X を 8 か所に限った 2032 の置き方のうち、前処理（Algorithm P）が 235 個を取り除けると書く。数える前は「どの解にも出ない置き方は 235 個より多く、470 個には届かない」と見立てた。X を左上の 4 分の 1 に寄せた 2339 通りに出る置き方を集めると 1464 個で、一度も出ない置き方は 568 個あった。前処理が見つける数の 2.4 倍で、見立ての上の端を超えた。

2 つの長方形に割れる詰め方

縦の線 1 本で 2 つの長方形に割れる詰め方も数えた。6 × 10 は 5 列ずつに割れる 16 通りだけで、前刷りの 16 と同じだった。5 × 12 は 264 通りが割れ、前刷りの 264 と同じになる。その中で 5 × 3 と 5 × 9 に割れるのは 8 通り、5 × 5 と 5 × 7 は 16 通り、5 × 6 どうしは 16 通りで、これも前刷りの 8・16・16 に合った。4 × 15 は 4 × 5 と 4 × 10 に割れるものが 40 通りで、前刷りが引く Bouwkamp（1970 年）の 40 と一致した。

1 つだけ合わない数がある。前刷りは、6 × 10 を 5 列ずつに割る線をまたがない置き方が 2032 のうち 1507 個残ると書く。ここで数えると 1514 個だった。解の数 16 は合っており、7 個の差の理由は突き止めていない。（2026-09-26 追記）X 以外の 11 片だけで、線をまたがない置き方が 1508 個ある。X の 8 か所のうち線をまたがないのは 6 か所なので、X をどう選んでも合計は 1508 を下回らない。1507 との差は、X の選び方では説明できない。

真ん中に穴のある盤

8 × 8 の盤の真ん中 2 × 2 を抜くと、ちょうど 60 升になる。Knuth（2000 年）によると、Scott は 1958 年にこの盤の詰め方をすべて計算機で数えた。同じ 2 通りの数え方で、置き方は 1568、詰め方は 65 通り（向きのままで 520）になり、Knuth の論文の 1568・65・520 と同じだった。X の中心の置き場所で分けると 19・20・26 通りで、これも論文の 3 つの場合の数と一致した。

数字を出す前の見立ては 5 つだった。4 つの箱と穴のある盤で文献の数が出ることと、どの解も自分に重ならないことは当たった。縁に触れない片の 1 番（X ではなく W）、十字の置き場所（真ん中ではなく短い辺の側）、どの解にも出ない置き方の数（470 個を超えて 568 個）の 3 つは外れた。

→ 清少納言知恵の板とタングラムの凸多角形（決まった片で形を組む数）

→ 畳の敷き方（決まった板で床を埋める数え上げ）

→ Wang タイル（決まった板で平面を埋める）

Dudeney の盤は、色と向きを守ると 4 通り

（2026-09-26 追記）問題 74 は、12 枚に 4 升の正方形を 1 枚足して 8 × 8 の盤を組む問題である。本文は「a perfect board properly chequered」、つまり市松模様がきちんとそろった盤を求める。片は割れた盤の破片なので、升ごとに黒と白が塗ってある。Gutenberg 版の問題の図（images/120.png）から 13 片の塗り分けと向きを目で読んだ。読んだ塗り分けは、どの片でも隣り合う升の色が違い、黒の升を足すと 32 になった。

Knuth の前刷りは、演習 274 の答えで、正方形を足した 8 × 8 の詰め方を 16146 通りとする。正方形の置き方は、1 升か 2 升の区画をすぐに切り離すものを除けばどこでもよい、とも書いてある。同じ答えの注には、Dudeney の塗り分けに合わせ、どの片も裏返さないとすると、解は 4 つだけになるとある。

まず色を見ずに数えた。1 つ目の数え方（踊るリンク）では、X の中心を左上の三角の 6 か所に限った。置き方は 2327 で、前刷りの 2327 と同じである。解は 19,371 個で、盤の 8 つの対称で重なるものを 1 つと数えると 16146 通りになった。2 つ目の数え方（ビット盤の総当たり）では、X を鏡に映した側の三角に限った。重なるものを 1 つにした解の集合は、1 つ残らず一致した。向きのままの数は 129,168 で、ちょうど 8 倍になる。X の中心の置き場所で分けると 6683・2763・1490・3475・1735 通りで、隅に近い 1 か所は 0 通りだった。前刷りの「本質的に違う 5 か所」はこの 5 つにあたる。

次に、盤の色を固定して 4 つの条件で数えた。色を合わせて裏返さない詰め方は 8 つで、半回転で重なる組を 1 つと数えると 4 通りになり、前刷りの 4 と同じだった。置き方の段階で色の合わない置き方を除き、2 通りの数え方で直接数えても 8 になる。色を合わせて裏返してよい場合は 276（重なるものを 1 つとして 69 通り）、色を見ずに裏返さない場合は 2088（同じく 522 通り）だった。

解答の図（images/221.png）の片の境目は、升の境目ごとに太い線の画素を数えて読んだ。細い線は多くても 67、太い線は少なくても 98 で、90 を境に分けられる。4 通りのうち 1 つは、境目 112 本がすべて図と合った。残りの 3 通りと、その半回転は 40〜56 本が違う。Dudeney の答えは 4 通りのうちの 1 つである。

2 × 2 の正方形の置き場所で 129,168 を分けると、4 つの隅がそれぞれ 10,054 で最も多く、4 隅で全体の 31.1% になった。真ん中は 520 で最も少ない。この 520 は、真ん中 2 × 2 を抜いた盤の 65 通りの 8 倍で、上の節の数え方と一致する。

ここからは、数える前に見立てを書いてから数えた。問いは、ペントミノ 12 枚の塗り分けを Dudeney の図から替えたら、色を合わせて裏返さない詰め方の数がどう変わるかである。5 升の片はどちらの色が 3 升になるかで塗り分けが決まるので、塗り方は 2¹² 通りあり、黒の合計が 32 になるのは 660 通りである。裏返さない 2088 の詰め方を、片ごとに図と同じ色か逆の色かで分けて数えた。

見立ては 3 つだった。1 つ目は「黒が 32 になっても、詰め方が 1 つもない塗り方がある」。660 通りのうち詰め方があるのは 384 通りで、276 通りには 1 つもなかった。当たりである。2 つ目は「Dudeney の塗り方の 8 は、真ん中あたりの数」。詰め方の数の真ん中は 4 で、8 より多い塗り方は 58 通りしかない。Dudeney の塗り方は多い側にあり、見立ては外れた。最も多いのは P と T の色だけを逆にした塗り方で、44 通りある。3 つ目は「X の中心が黒の塗り方のほうが詰め方は少ない」。中心が黒の塗り方も白の塗り方も、合わせて 1044 通りずつで同じだった。外れである。盤を 90° 回すと、片は裏返らないまま盤の色だけが入れ替わる。だから、ある塗り方と白黒を入れ替えた塗り方は、いつも同じ数になる。いちばん多い塗り方と、詰め方のない塗り方の 1 つは、置き方の段階で色を絞って 2 通りで数え直し、44 と 0 になった。

どう作ったか

生成器は generators/pento.js である。片は Golomb の 12 文字で持ち、8 通りの回転と裏返しから形の違う向きだけを残した。1 つ目の数え方は、Knuth の論文の手順どおりに双方向の連結リストで Algorithm X を書いた。2 つ目の数え方は、升に走査の順番を振り、各置き方をその中で最も早い升に束ねておく。まだ埋まっていない最初の升を必ず覆う置き方だけを試すので、同じ詰め方は 1 回しか現れない。重なる解のまとめ方は、箱の対称で写した書き方のうち文字列として最小のものにそろえた。1 つ目の数え方の解は generators/data/pento/ に書き出し、検査のたびに 2 つ目の数え方で出し直した解と突き合わせる。Dudeney の盤は 2 つ目の数え方が約 2 分かかるので、その結果は data に置き、検査では X を鏡の側に置いた踊るリンクで数え直して 16146 の書き方と突き合わせる。解答の図の境目の読み取り値も data に置いた。依存はなく、乱数も使っていない。

確かめていないこと。Haselgrove 夫妻の記事（Eureka 23 号、1960 年）は、ウェブ上の写しが途中までしか保存されておらず読めなかった。Golomb（1954 年）・Hansson（1935 年）・Scott（1958 年）・Potts（1960 年）・Bouwkamp（1970 年）は開いていない。どれも Knuth の書いた内容をそのまま借りた。Dudeney が 13 片の塗り分けをどう決めたかは、本文にも解答にも書かれていない。

出典

身近

H. E. Dudeney, The Canterbury Puzzles and Other Curious Problems（初版 1907 年）の問題 74「The Broken Chessboard」。Project Gutenberg の電子版（#27635）の本文と解答で確かめた。13 片の塗り分けと向きは同じ版の問題の図（images/120.png）、答えの境目は解答の図（images/221.png）から読んだ

数理

厳密被覆と踊るリンク・8 × 8 の中央抜きの 1568・65・520 と X の置き場所ごとの 19・20・26・6 × 10 の 2339: D. E. Knuth, Dancing Links, arXiv:cs/0011047（2000 年）。4 つの箱の解の数・置き方の数・3 × 20 の探索の節 71191・縁に触れる片の数・割れる詰め方の数・Algorithm P の 235 個・割る線をまたがない 1507 個: D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-Fascicle 5c（7.2.2.1 Dancing Links、2019 年 9 月 11 日版）の本文と演習 268〜272 の答え。正方形を足した 8 × 8 の 16146 と置き方 2327、色を合わせて裏返さない 4: 同じ前刷りの演習 274 の答えと表（答え 263）。そこで引かれる Golomb（1954 年）・Hansson（1935 年）・Haselgrove 夫妻（1960 年）・Potts（1960 年）・Bouwkamp（1970 年）は開いていない

親戚

清少納言知恵の板とタングラムの凸多角形・畳の敷き方・Wang タイル

生成

generators/pento.js（pento.svg 4 つの箱・pento-book.svg 帳簿・pento-dudeney.svg Dudeney の盤。data/pento/ に 1 つ目の数え方の解、8x8O.txt に Dudeney の盤の 16146 の書き方、dudeney.json に 2 つ目の数え方の結果、dudeney-figure.json に解答の図の境目の読み取り値。依存ゼロ）