茨城の高校生、スパコンで5×5の魔方陣の3億通り近い全解を求める

　筑波大学計算科学研究センターは2月28日、一般公募による「学祭共同利用プログラム」の一環として、茨城県立並木中等教育学校4年次(高校1年)の杉崎行優(すぎざき・ゆきまさ)君の申請が採択され、同センターの朴泰祐教授と共同研究した結果、スパコン「T2K-Tsukuba」を利用して、5×5の魔方陣の全ての解を求めることに成功したと発表した。

　魔方陣は、正方形の縦/横/斜めのマス目に、数字の合計が等しくなるよう1から順に数字を配置したもの。マス目が3×3の時、縦/横/斜めの和は15となり、その解は対称のものを除くと1通りだけだが、4×4では和は34で解は880通りになり、今回解が求められた5×5では和は65で解は2億7,530万5,224通りにも及ぶ。

枝刈り法をもとにした求解アルゴリズム。丸数字は総当たりで数字を入れる順番(1から25の数字そのものではない)、チェック印は自動的に求められるマスを表す。斜めのマスを優先的に埋めることで、自動的に求められるマスの個数をさらに増やすことができた。

　魔方陣の求解は、全ての数字を総当たりで入れて、正解かどうかを確かめていく。しかし、例えば5×5の場合、1列の和が65と分かっているので、1列の4マスまで埋めると残りの1マスは自動的に求められるため、これを総当たりから除くことができる。

　この考え方を「枝刈り法」と言うが、杉崎君は、総当たりのマス目の数を14にまで減らせることに気付いた。総当たりの数が増えると、計算にかかる時間は指数的に増えるため、14から15に増えただけでも計算時間は数十倍になるので、これは重要な気付きだった。

　今回、杉崎君と朴教授は、T2K-Tsukubaの全648ノードの内、32ノード(512CPUコア)、4.7TFLOPSの処理能力を使って並列計算を行ない、約2億7千万通りの全ての解を約2時間36分で求める事に成功した。出力結果は約25GB。

　ちなみに、6×6の解の総数は分かっておらず、現時点では求解は不可能とされている。総当たり数は36から23にまで減らすことができているが、この場合でも現在のプログラムでは150兆年かかる見積もりで、エクサスケールのスパコンでも54万年以上かかるため事実上も不可能となる

　T2K-Tsukubaは、2014年2月末で運用を終了し、同センターでは2014年度から377ノードで960TFLOPSの新スパコン「COMA」(こま)を導入する。