高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター

概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算

[htnmiki]

おねーさんがロボットになっちゃう！

[takamii228]

おねえさん再来の予感

[nyomonyomo]

脳裏に「おねえさん」という単語が浮かんだがブコメをみたら皆さんも同じ事考えてたみたいで安心したｗ

[Hiro0138]

5x5が2時間36分で6x6が150兆年って組み合わせ爆発すげ～

[midnightseminar]

「6×6魔方陣へのチャレンジは、現時点では不可能と判断しています。総当たり数を36から23まで減らすことができていますが、現在のプログラムでは150兆年かかると見積もられています」

[SWIMATH2]

MacBookAirたんの計算によると、総当たりは13個以下ではできないようですよ

[t_f_m]

http://www.ccs.tsukuba.ac.jp/wordpress/uploads/2014/02/image4.png これ、一般化したら(2n-1)魔方陣の枝刈りに使えるんじゃ？

[airj12]

6x6から完全におねえさん案件なのか

[earth2001y]

ロードバランスのばらつきでかいなー。さて、6x6が解ける日は来るだろうか。

[masaba]

魔法陣 全解

[milkya]

これを提案して実装した高校生はもちろんすごいと思うが、こんなハイレベルな大学の公募事業に応募することを支援した高校の先生もすごいと思う。普段からどういう指導してるんだろう。

[gam-22]

#kernelvm

[teajay]

どうやって計算時間を減らしたか、具体的な作戦が書いてある。コアの使い方の説明は特に知らなかったこと。

[nagaichi]

5×5で約2時間36分。6×6なら何時間かかるでしょうね？

[makou]

なるほど爆発ゴロー。

[zakinco]

おお～

[sniff_jp]

スパコンTUEEE

[kaeru8823]

ハンドヘルドコンピュータでデジタルデビル的な話かと

[kuippa]

高校生がスパコンにアクセスできるパスがあるってのが凄いよね。。。

[Yasima]

思ってた魔法陣と違う

[myrmecoleon]

6×6の魔方陣てまだ総数わかってないのね。

[fujixe]

全解はすでに求められてるけど、枝刈りのやり方を工夫してスパコンで速く求められるようにしました、ってことでしょ。解くのは誰だって「成功」するわけで、そこが論点じゃない。

[ROYGB]

コンピュータで無理やり解くというのは四色問題がはじめだったかな。

[taraxacum_off]

「高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功」。魔方陣を解くのは総当たりしかないのね

[kiron00]

すごいなあ。気がついて検証しようと具体的なアクション起こして結果出すとか、各ステップがそれぞれ立派だわ

[kenichioride]

「枝刈り法」は無駄を省くために大事。

[kamei_rio]

「杉﨑君はこの枝刈り法をもとに、総当たりのマス目の数を25から14まで減らせることに気づきました」スパコーン

[gn_spawn]

T2K筑波実際に見てきたけどすごかった(こなみ)

[mobius118_7]

使用ノード数は32ノードが最適だったのだろうか？ その理由が知りたい 648ノードを技術的な問題で使用出来なかったのならちょっと残念

[honeniq]

150兆年って小学生が考えそうな数字で楽しそう

[mohno]

高校生ってのがいいね。

[mmuuishikawa]

すばらしい

[cider_kondo]

「今回は総当たりを14で行いましたが、これが最も少ないかどうかはわかりません。さらに減らせる可能性もあります」がいろいろと怖い。