ソーマキューブの 240 通り

なにか

ソーマキューブは、Piet Hein が考えた 7 つの片である。英国特許 420,349 の抄録（Google Patents で開いた）には、住所がコペンハーゲン、出願が 1934 年 3 月 20 日、条約による優先日が 1933 年 12 月 2 日とある。7 つの片はどれも 3 つか 4 つの立方体でできていて、どの立方体も少なくとも 3 つの面が外に出ている、と書かれている。

片の番号と名前は、Knuth の『The Art of Computer Programming』第 4 巻の前刷り 5c（2019 年 9 月 11 日版・以下は前刷り）の (39) に合わせた。1 bent・2 ell・3 tee・4 skew・5 L-twist・6 R-twist・7 claw である。前刷りによると、Hein は 1933 年に、直方体でない形のうち最も小さい 7 つで 3 × 3 × 3 が組めることに気づいた。前の 4 つは平らな片で、後ろの 3 つは立体の片である。5 と 6 の 2 つのねじれた片は、互いの鏡像になっている。前刷りは、Gardner が Scientific American 199 巻 3 号（1958 年 9 月）182〜188 ページでソーマを紹介したことも書く。Gardner の記事そのものは開いていない。

2 通りの数え方

組み方は、7 つの片と 27 の升を、置き方 1 つ（片 1 つと升 3〜4 つ）でちょうど 1 回ずつ覆う厳密被覆問題として書ける。片を回転だけで動かすと、向きの数は 12・24・12・12・12・12・8 で、立方体の中の置き方は 144・144・72・72・96・96・64、合わせて 688 になった。前刷りの演習 324 の答えと同じである。

1 つ目の数え方は、ペントミノで書いた踊るリンク（Algorithm X）をそのまま使い、置いた向きのまま全部の解を出した。2 つ目の数え方は、番号の若い空き升から順に、そこを覆う片を試すビット盤の総当たりである。2 通りとも 11,520 通りが出て、解は 1 つ残らず一致した。立方体の回転と鏡映 48 通りで重なる解を最小の書き方にそろえると、240 通りになる。鏡映では 5 と 6 の名前を入れ替えて比べた。

対称の割り方も、前刷りにある 2 つの方法で試した。tee を 000・001・002・011 の 1 か所に固め、claw が k = 2 の升を使う置き方を捨てると、置き方は 585 に減り、ちょうど 240 の解が出た。ell を回さない向きの 6 つの平行移動に限ると、置き方は 550 で解は 480 になった。これは回転だけで重なるものを 1 つとした数で、鏡に映した対が 240 組ある。どちらの 240 も、1 つ目の数え方の 240 と同じ集合だった。

数える前の見立ては「どの解も立方体の対称で自分に重ならない」だった。11,520 は 240 × 48 にちょうど等しく、自分に重なる解は 0 だったので、見立てどおりである。

色分けで片の置き場所を絞る

前刷りは、M. J. T. Guy・R. K. Guy・Conway が 1961 年に手で行った絞り込みを紹介している。升を、座標に真ん中の値 1 がいくつあるかで、角 8・辺 12・面 6・真ん中 1 に分ける。角の 8 升を片ごとに数えると、tee は必ず角を 2 つ使い、ell は角を少なくとも 1 つ使う。角を黒にした市松で数えると、bent は黒を 2 つ、claw は黒を 1 つだけ使う。これで 688 の置き方のうち 200 が消える。

ここで同じ条件を置き方にかけると、ちょうど 200 が消えて 488 が残った。残りだけでも 11,520 の解が全部出て、どの解もこの条件を満たしていた。さらに tee を 1 か所に固めて claw を半分にすると 449 になる。前刷りが書く 455 は、この 449 に「角を最も多く使う片はどれか」を表す 6 つの置き方を足した数で、足し算も合う。

真ん中の 1 升

数える前は「真ん中の 1 升を占める回数がいちばん多い片は claw」と見立てた。平らな片より立体の片のほうが、四方を囲まれた升に入りやすいと考えたからである。向きのままの 11,520 解で真ん中に入る片を数えた。最も多いのは L-twist と R-twist で、3,624 回ずつ（31.5%）並んだ。claw は 1,776 回、skew は 1,584 回、bent は 912 回だった。見立ては外れた。ell と tee は一度も真ん中に入らない。tee は角を 2 つ使うので辺に沿って置くしかなく、ell は角を 1 つ以上使うので、どちらも真ん中まで届かない。前の節の色分けから、そのまま言える。

Somap

前刷りの演習 325 は、240 の解を点にしたグラフを Somap と呼ぶ。ある解と、別の解の同値な 48 個のどれかとの違いが 3 片以下の置き場所だけなら、2 点を辺で結ぶ。違いが 2 片だけのときに限ったものが強い Somap である。Guy・Conway・Guy が計算機なしで作り、Berlekamp・Conway・Guy の『Winning Ways』に載っていると前刷りは書く。『Winning Ways』は開いていない。

数える前は「次数の並びは前刷りの答えと同じになり、強い Somap の孤立点は 15 個」と見立てた。同じ規則で辺を張り、1 組の解のあいだに同値な相手が 2 つ以上あるときは辺を重ねて数えた。強い Somap の次数は 7 が 1 点・6 が 7 点・5 が 19 点・4 が 31 点・3 が 59 点・2 が 63 点・1 が 45 点・0 が 15 点で、前刷りと同じだった。重なった辺は 1 組ある。孤立点を除く 25 の連結成分の大きさも、118・16・11・8・7・6・6・5・5・5・4 と 3 が 6 つ、2 が 8 つで、前刷りと一致した。3 片までの Somap は重なった辺が 14 組、次数の最大が 21 で、連結成分は孤立した 1 点と残りの 239 点に分かれ、直径は 8 だった。次数の並びも含めて、前刷りの答えと同じである。

前刷りの答えには、特別な解が 27 桁の数字（下の段から、升ごとの片の番号）で 7 つ書いてある。そのまま読むとこちらの 240 には見つからず、5 と 6 を入れ替えると 7 つとも見つかった。前刷りの桁の並べ方が、こちらの座標とは鏡に映した向きになっているためである。そう読むと、前刷りが孤立点と書く解の次数は 0、ただ 1 つの次数 1 の点と書く解は 1、強い Somap で次数 7 と書く解は 7 になり、説明と合う。上の図に描いたのが、この孤立点の解である。

もう 1 つの見立ては「2 片だけ入れ替えて別の解に移れるとき、入れ替わる 2 片は平らな 4 片どうしが過半を占める」だった。強い辺 307 本のうち、平らな片どうしは 140 本（45.6%）で、過半には届かず外れた。平らな片とねじれた片が 94 本、claw と平らな片が 37 本、ねじれた片どうしが 22 本、claw とねじれた片が 14 本だった。skew とねじれた片が入れ替わる辺は 1 本もない。

数えた数を並べると、ペントミノの 6 × 10 は 12 片で 2339 通り、知恵の板は 16 の形で合わせて 531 通り、ソーマは 7 片で 240 通りになる。

見立ては 6 つだった。2 通りで 240 が出ること、自分に重なる解がないこと、色分けの条件がどの解でも成り立つこと、Somap の次数の並びが前刷りと同じになることの 4 つは当たった。真ん中の升にいちばん入る片（claw ではなく 2 つのねじれた片）と、入れ替わる 2 片の組（平らな片どうしは 45.6% で過半に届かない）の 2 つは外れた。

→ ペントミノを長方形に詰める組み方（同じ踊るリンクで平面を詰める）

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

どう作ったか

生成器は generators/soma.js である。升 (i, j, k) を i × 9 + j × 3 + k の番号で持ち、片は回転 24 通りだけで向きを作った。twist の向きは、前刷りに例として載っている置き方 5 000 001 010 110 と 6 000 001 010 101 に合わせた。1 つ目の数え方は generators/pento.js の踊るリンクを借りた。2 つ目の数え方は 27 ビットの盤で、空いている最も若い升を覆う置き方だけを試すので、同じ解は 1 回しか現れない。解は 27 桁の片の番号で書き、立方体の対称 48 通りで写した書き方のうち文字列として最小のものにそろえた。Somap は 240 の解の組ごとに、相手の同値な書き方を全部並べ、片ごとの升の集合を比べて作った。依存はなく、乱数も使っていない。全部の計算は数秒で終わる。

確かめていないこと。Gardner の記事（1958 年）、Guy・Conway・Guy の絞り込み（1961 年）、『Winning Ways』の 845〜847 ページと 910〜913 ページは開いていない。どれも Knuth の書いた内容を借りた。英国特許は Google Patents の抄録と日付だけを読み、明細書の図は見ていない。L-twist と R-twist の名前は前刷りの置き方の例から決めた。前刷りの図 (39) の向きと突き合わせてはいない。

出典

身近

P. Hein, 英国特許 420,349「Toy building or puzzle blocks」。Google Patents の抄録（出願 1934 年 3 月 20 日・条約による優先日 1933 年 12 月 2 日・7 つの片はそれぞれ 3 つか 4 つの立方体からなる）で確かめた

数理

片の番号と名前・Hein の 1933 年・Gardner（1958 年）・置き方 688・解 11,520 と 240・ell を回さない 480・tee を固めて claw を半分・Guy・Conway・Guy の色分けと 200・455: D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-Fascicle 5c（7.2.2.1 Dancing Links、2019 年 9 月 11 日版）18〜22 ページ。片ごとの向き 12・24・12・12・12・12・8 と置き方の内訳: 同じ前刷りの演習 324 の答え。Somap の次数・重なった辺・連結成分・直径・特別な 7 つの解: 同じ前刷りの演習 325 の答え。踊るリンク: D. E. Knuth, Dancing Links, arXiv:cs/0011047（2000 年）

親戚

ペントミノを長方形に詰める組み方・清少納言知恵の板とタングラムの凸多角形

生成

generators/soma.js（soma.svg 立方体と 7 つの片・soma-book.svg 帳簿。依存ゼロ）