MacMahonのSuperdomino

MacManonの3色四角形Superdominoにはジグソーパズル風の変形がある. つまり黒は黒と接するが, 白は灰と接するのである. それでも解はある.

白と灰の間の線を凹凸にするとジグソーパズルになるのである. そのジグソーdominoを前回のブログの3色四角形superdominoの図に対応させて描くと次のようになる.


The Winning Waysにはそれを利用したJohn Conwayの1968年のクリスマスカードの絵がある. (ウェブを探したらやっとここに見つかった.)

とりあえず制約条件をすこし修正してプログラムを走らせると, 次の解がまず得られた. この境界をジグソーに対応させたのがその下の図だ.


このジグソーパズルが通常のそれと違うのは, 絵にまったく頼らずに完成することである. それも多くの解(余詰め?)が存在する. ユニーク解にするためにはやはり絵を描くことになろう. それでCheshire Catの絵に上の解を重ねてみたのが下の図だ.


1年ほど前, IBMカードを作ったcraftroboを使って切り出せば, ジグソーパズルが作れるはずだが, こんなに優しいジグソーパズルは作るまでもあるまい.

MacMahonのSuperdomino

The Winning WaysにMacManonのSuperdominoという話題がある. 正n角形で辺と中心で出来る二等辺三角形をm色に塗り分けたものである. m色n角形superdominoという.

4色三角形superdominoは24種, 3色四角形superdominoも24種類ある.



5色五角形superdominoは, 各色を1回ずつ使い裏返しは同じとみると12種だ. この12種で辺の両側が同じ色になるように正十二面体に貼ることができるかがクイズである.

五角形は置いておき, 三角形では辺の長さが三角の辺の2倍の正六角形の中に, 周囲を同一色にし, 内側の相対する辺が同じ色になるように詰めるのがクイズ. 四角形では4×6の長方形で同様にするというのがクイズである.

四角形の, 周囲を黒にした解の一例は以下だ.



十年ほど前, 情報処理学会誌にプログラム・プロムナードの連載があり, 私はそこで「計算機用ジグソーパズル」という記事を書いた. それ以外にも探索問題のプログラムはなんども書いたからちょっとやってみたが, 最初の解が出てくるまでは存外大変であった.

プログラムを書くには24個の箱とその辺を下の図のように番号をつける.



制約としては箱0の辺0の色は2, 箱0の辺3の色は2, 箱1の辺0の色は2, 箱2の辺3の色は箱0の辺1の色, ...のようになる.

そして4色四角形のsuperdominoのプールから, 必要に応じて回転しながら, 制約に合うものを探すことになる.

しかし闇雲に初めても最初の解もなかなか現れない. ある週末, プログラムを走らせたまま帰宅したら, 次の週の初め, 夛くの解が出ていたから, 方針としては良かったのだが, これではあまりにも手抜きであったのでなるべく準備をしてからやりなおすことにした.

左上の箱から番号順に詰めていくとすると, まず辺0がg₀, 辺3がg₃, 辺1と辺2はどうでもよいdomino の集合を*g₀??g₃とする. ?は0,1,2だから要素が9個の集合が出来る. 箱5,11,17,23用には辺1が2だから要素数3の*g₀2?g₃. 箱18から22用には辺2が2だから要素数3の*g₀?2g₃. 箱18用には辺1と2が2だから要素数1のg₀22g₃を用意する.

*2222は(((2 2 2 2) (23 0)))
*02?2は(((0 2 0 2) (13 0)) ((0 2 1 2) (15 0)) ((0 2 2 2) (17 0)))
で, 要素は((u r d l) (i j))の形である. u, r, d, lは上右下左の色(0,1,2), iはdomino番号(0〜23), jは90度の回転した数(0〜3)である.

プログラムの中心は次のようだ.

(define (test n ps is js)
 (define (up ps) (caddr (list-ref ps 5)))
 (define (left ps) (cadar ps))
 (define (try *????)
  (for-each (lambda (x)
   (let ((p (car x)) (i (caadr x)) (j (cadadr x)))
    (if (not (member i is))
     (test (+ n 1) (cons p ps) (cons i is) (cons j js)))))
      *????))
 (case n
  ((0) (try *2??2))
  ((1 2 3 4) (case (left ps) ((0) (try *2??0))
                             ((1) (try *2??1))
                             ((2) (try *2??2))))
  ((5) (case (left ps) ((0) (try *22?0))
                       ((1) (try *22?1))
                       ((2) (try *22?2))))
  ((6 12) (case (up ps) ((0) (try *0??2))
                        ((1) (try *1??2))
            ((2) (try *2??2))))

あとは同様なのでしばらく省略.

  ((24) (begin (display ps) (newline) (display is) (newline)
   (display js)) (newline))))

testの引数はpsがそれまでのdominoの列, isはi, jsはjの列である. (test 0 '() '() '())で起動する.

プログラムをしばらく走らせると解が次々と現れる. とても全解探索する気分にならないが, Martin GardnerのNew Revised Edition Mathematical Diversionsの193ページに解の総数は12261と書いてあった.

1964年の初め, Stanford大学の計算センターで, Gary Feldmanが全解を求めるプログラムを書いた. Algolで書いたプログラムはB5000計算機で40時間かかったそうだ. 結果は8ページの"Documentation of the MacMahon Squares Problem," a Stanford Artificial Intelligence Project Memo No. 12で, 1964年1月16日に計算センターから刊行された.

なおこの話題によると2009年11月21日と29日のブログ 彩色立方体もMacMahonの考えたものらしい.