先日、ショパンのノクターン20番をアップしたのでそちらの解説でもしようかと思っていたのだけど、ちょっと時間が掛かりそうなので息抜きに。
筑波大学（つくば市）は２月２８日、茨城県立並木中等教育学校（同）の杉崎行優(ゆきまさ)さん（１６）が同大のスーパーコンピューターを使って、「魔方陣」と呼ばれる数字の組み合わせについて、２億７５００万を超える全パターン算出に成功したと発表した。 一般公募で採択されたもので、高校生が大学教授とスパコンの共同研究をするのは珍しいという。 同校は中高一貫校で、杉崎さんは高校１年に相当する４年生。３歳頃からパソコンに触れ、小学４年頃にプログラミングを始めた。先生に紹介された高校生向けの「スーパーコンピューティングコンテスト」に挑戦したいと考え、３年ほど前から、書籍やインターネットを活用して独学でプログラミングの腕を磨いた。 杉崎さんは２０１１年３月に算数の本で魔方陣に出会った。魔方陣は正方形の中にマス目を作り、各マスに数字を入れたもの。縦横斜めのどの列についても、並んでいる数字の和が等しくなる。９マス（縦横各３マス）の魔方陣は、和が１５となる１通りの組み合わせしかないが、２５マス（同５マス）になると２億７５３０万５２２４通り存在することが知られていた。 計算プログラムを作り始めたところ、同大計算科学研究センターがスパコン利用者を公募することをセンターのサイトで知り、１３年１月に申請した。基本的に大学や研究機関などの研究者向けの手続きで、センターも中学生からの申請は初めて。当初はとまどいもあったが、同センターの朴泰祐教授が共同研究する形で利用を認めた。 ２５マスの魔方陣は手当たり次第に数字を当てはめれば計算量が膨大になるため、杉崎さんは「できるだけ計算量を減らせないか」と考えた。そして計算量が少なくてすむ一定のルールを発見。スパコンの頭脳に当たる多くの中央演算処理装置（ＣＰＵ）を効率的に動かす工夫も施し、約２時間３６分の計算ですべての組み合わせを求めた。 アドバイスをしてきた朴教授は「理系的なセンスが素晴らしい。課題に対して改良を重ねることができ、高い能力を持っている」と認める。杉崎さんは「初めてスパコンを使ったが、難しいとは感じず楽しめた」と話している。 （2014年3月2日 読売新聞） |
ちょっとタイトルがむかつくんだけど読売新聞から引用。
魔法陣については、以前3×3の魔方陣の解き方を解説したのだけど、その際に4×4については特に解法を思いつかない、ということでパスしていた。今回の記事を読む限りでは、結局総当りしなければならないから考えるだけ無駄だよね、ということらしい。
以下の文章では以前の解説のときに倣って、横の方向を行、縦の方向を列として表記する。
さて、今回筑波大学で行った計算では試行錯誤というか総当たりしなければならないマス目の数を減らすというのがこのプログラムのミソ。
この記事だけでは具体的に何をやったのかよく分からないのだけど、筑波大学から報告書があがっている。
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功
筑波大学というととある魔術の禁書目録みたいでカッコイイと最近は株が上がりまくっているわけですが、学園都市という売り文句で頭よさげです。この報告書を読めば何をやったかだいたいわかるし、技術がある人なら再現できると思う。ちなみに僕はマルチコアを利用したプログラムとか知らないので無理。1970年代に5×5の魔方陣の全解は2億7530万5224通りあるということが判明しているらしいので、その際に全ての解は求められているのかな。解を出さずに何通りあるかとか分からないよね。
細かい部分は抜きにして、解法について説明してみる。
この図の順番に数字を入れていくことがポイント。従来25マスの内16マスを埋めなければならなかったところが14マスで済むようになったということ。1970年代に計算した奴は今よりもはるかに時間がかかっただろうに、16から減らそうとは思わなかったのか、今よりはるかに時間がかかるんだから工夫しろよとか思う。
左上から右下に向かって斜めに数字を入れていき、4つ目まで入れると、自動的に5つ目は確定される。縦・横・斜めの合計が65になるので引き算すれば出てくる。この時、5つ目の数字が1～25の間に入らなかったらそのパターンはダメということになり、残り20の試行は放棄できる。
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| ④ | ||||
この時点で上のように埋まる。④は4つ目を埋めた時に自動的に埋まるので④とした。 次は逆の対角線を埋める。右上から左下に向かって5,6,7と埋めると左下が自動的に埋まる。
| 1 | 5 | |||
| 2 | 6 | |||
| 3 | ||||
| 7 | 4 | |||
| ⑦ | ④ | |||
ここで、⑦が1～25の間に入らなかったり、既に埋められている数値となったらそのパターンはダメということになり、残り16の試行は放棄できる。 次は一番上の列を左から8,9と埋めると、9と5の間が埋まる。
| 1 | 8 | 9 | ⑨ | 5 |
| 2 | 6 | |||
| 3 | ||||
| 7 | 4 | |||
| ⑦ | ④ | |||
次は、上から②列目を10,11と埋めるとその右端が埋まる。
| 1 | 8 | 9 | ⑨ | 5 |
| 10 | 2 | 11 | 6 | ⑪ |
| 3 | ||||
| 7 | 4 | |||
| ⑦ | ④ | |||
次は左端の真ん中を埋めると左の列が完成する。
| 1 | 8 | 9 | ⑨ | 5 |
| 10 | 2 | 11 | 6 | ⑪ |
| 12 | 3 | |||
| ⑫ | 7 | 4 | ||
| ⑦ | ④ | |||
次は12の右隣を埋めるとその一番下のマスが埋まる。
| 1 | 8 | 9 | ⑨ | 5 |
| 10 | 2 | 11 | 6 | ⑪ |
| 12 | 13 | 3 | ||
| ⑫ | 7 | 4 | ||
| ⑦ | ⑬ | ④ | ||
最後は13の2つ隣を14で埋めると、14の行の右端と列の一番下も埋まる。
| 1 | 8 | 9 | ⑨ | 5 |
| 10 | 2 | 11 | 6 | ⑪ |
| 12 | 13 | 3 | 14 | ⑭ |
| ⑫ | 7 | 4 | ||
| ⑦ | ⑬ | ⑭ | ④ | |
次いで残り3つのマスも埋まる。
| 1 | 8 | 9 | ⑨ | 5 |
| 10 | 2 | 11 | 6 | ⑪ |
| 12 | 13 | 3 | 14 | ⑭ |
| ⑫ | 7 | ⑭ | 4 | ⑭ |
| ⑦ | ⑬ | ⑭ | ⑭ | ④ |
というわけで、14手ですべてのマスを埋めることが出来る。 ちなみに、14手で埋める方法はこれだけというわけではなく、下のようにテキトーに埋めてみても14手でできたりする。
| 1 | 2 | 3 | 4 | ④ |
| 5 | ⑭ | ⑭ | 8 | ⑭ |
| 6 | 13 | 9 | 12 | ⑬ |
| 7 | ⑨ | 10 | 11 | ⑪ |
| ⑦ | 14 | ⑭ | ⑫ | ⑭ |
てなわけで、話をぶり返すようだけど1970年代に計算した人は何で効率化しなかったのかなあと疑問に思うわけ。
逆に終了させるのにかかるのに14手が最小手数と決まったわけでもなく、筑波大学の報告書でもさらに減らせる可能性もありますと書いてあるので、かかる手数を計算する試行というのも面白いかもしれない。この場合、マスを埋める順番は考える必要はなくなってくるため、225=33554432と約3千万回の計算で解くことができる。その後でどの順番でマスを埋めていったらよいかを考えたら良い。これくらいの計算なら普通のPCでもすぐに計算できそう。
この筑波大で行ったアルゴリズムを見ると、対称性に対する評価が抜けているので、これを入れると計算量がだいぶ減らせる。例えば、左上の端に入れたことのある数値が残りの角地に入った時、それは既に計算済みとするだけで最大1/4に減らせる。更に、裏返した形を回避するために、左上が同じで右上に入れたことのある数値が左下にきたときを同じと見なすことで更に1/2にすることができる。この2点を実装するだけで計算量が最大1/8になる。
関連エントリー
20150412 魔方陣の対称性による計算の効率化
20110530 3×3の魔方陣
