電通大が「N-queens」問題の世界記録達成

公開 2004年10月06日 18時49分

更新 2004年10月06日 06時48分

[ITmedia]

印刷する

　数学とコンピュータ科学の古典的問題「N-queens」問題の計算で、電気通信大学の研究グループがこのほど世界記録を達成した。並列処理を活用し、1CPUでは6年かかる計算を22日間に短縮した。

　N-queensはチェスの問題。互いに攻撃しないN個のクイーンをN×Nのボードに配置する解の総数を求める。Nの値を大きくするたびに計算量が急激に増え、従来は得られていた解はN＝23が最高だった。

　同大学の大学院情報システム学研究科並列処理学講座は4月、Xeon/2.8GHz×68プロセッサのシステムとC言語による専用プログラムを使い、世界記録となるN＝24の解の計算に成功した。9月にはN＝23の解を計算したフランスのグループも計算に成功し、得られた値は電通大グループと同じだった。解の値は「227514171973736」。

　フランスグループの計算期間は17日間と電通大グループより短いが、記録には先に結果を得た電通大グループが登録される。成果は電子情報通信学会のレターとして採録される予定。計算に使用したプログラム「qn24b」は、ベンチマーク用として公開している。

印刷する