その号のMathematical Gamesコラムに はeπ√163は整数である(これについては高橋秀俊先生が1975年の高橋コンファレンスで話された. どこかにそれが書かれているかと探したが見当たらない.)とか怪しい話もあり, 結局は四月馬鹿の話題であったのだ.
私もその号のコラムを読み, なーんだと思ったひとりである. それから既に40年経った.
TAOCPには演習問題の解を見る前に自分で試みよとあったので, とりあえずバックトラックしながら解を探すプログラムをSchemeで書き, 解をひとつ見つけた. 結構時間が掛ったが, プログラムを走らせてから長めのミーティングに出ていて, 戻ってきたら解が出力されていた.
ちゃんと4色で塗れた. 探索プログラムより区画どうしの接続データを作るのが面倒であった. またこの図を描くPostScriptのプログラムも予想外に時間がかかった.
接続データはこういう形である.
(0 1 10 11 100 101 102 103 104 105 109) (1 0 2 11 12 109) (2 1 3 12 13 109) (3 2 4 13 14 109) (4 3 5 14 15 109) (5 4 6 15 16 109) ... 途中100行省略 (106 10 95 96 105 107) (107 10 96 97 106 108) (108 10 97 98 107 109) (109 0 1 2 3 4 5 6 7 8 9 10 9 19 98 108)))例えば最上行は「0の区画と隣合うのは1, 10, 11, a0, a1, a2, a3, a4, a5, a9である」という意味. aは10 と書いてある. もちろんaの隣のリストにあるbについて, bの隣のリストにaがあることはチェックした.
得られた解で塗り分けたのが下の図である. かなり美しい.
110の区画でそれぞれの色が使われた数はであった. と書いた理由はTAOCPにひとつの色は7区画でしか使わない解があるという記述があったからだ. そういう解を探すのはまた大変そうだ.
TAOCPではこれをdancing linksで解くつもりらしい. dancing linksのプログラムは以前に書いたこともあるので, そのうちdancing linksでもプログラムを書いてみたい.
ところで各区画に付いている番号には意味があるのかな. 上の図は10次だが, 9次とか描くには番号が手引きになるのだろうか.
0 件のコメント:
コメントを投稿