N-queensの世界記録樹立，6年分の計算を並列処理により22日に短縮
報道関係者各位 2004年10月5日
プレスリリース 電気通信大学 大学院情報システム学研究科
N-queensの世界記録樹立、6年分の計算を並列処理により22日に短縮
電気通信大学 大学院情報システム学研究科 並列処理学講座（コンピュータお
よびネットワークの高速化を狙いとする並列・分散情報処理の科学と技術に関
する研究）において、N-queens問題の世界記録を樹立しました。
数学および計算機科学の古典的な問題としてN-queensという問題が存在します。
これは、互いに攻撃を行わないようなN個のチェスのクィーンをN x Nのボード
に配置する解の総数を求める問題です。
古くは、チェス盤を利用した8-queensとして1848年にチェスプレーヤーのMax
Bazzelによって導入された問題とされています。2年後の1850年にはCarl Gauss
による解法が議論され、多くの数学者の議論の対象となっています。一般的な
サイズのN-queens問題に拡張され、近年では、計算機科学の例題として広く取
りあげられています。
特に、バックトラックを用いたアルゴリズム、分割統治法、制約充足問題など
の例題として利用されています。
この問題は、クィーンの数に対応するNの値を大きくすると、計算量が一桁程
度急激に増加するために、従来は、N=23 の問題までの解しか得られていませ
んでした。
これに対して、逐次プログラムの効率化と高効率な並列手法を用いて、N-queens
のプログラム(C言語で記述)を構築し、Intel Pentium 4 Xeon 2.8GHzのプロセッ
サを68個搭載するPCクラスタを用いて、世界記録となる N=24 の解を計算する
ことに成功しました。
この計算は、1CPUの場合には6.6年の計算時間が必要となると見積もられていた
もので、この処理を並列処理などにより、68個のプロセッサを用いて、22日間
という現実的な処理時間に短縮することに成功しました。
計算結果が得られたのは2004年4月11日で、得られた N=24 の解の値は、
227,514,171,973,736 です。
その後、N=23の世界記録を樹立したフランスINRIAのProActiveグループにより、
2004年の9月にN=24の解が計算され、我々が計算した値と同じであることが判
明し、計算結果の検証がおこなわれています。フランスのグループは17日間で
結果を得ていますが、先に結果を得た我々が世界記録として登録されます。
この結果は、On-Line Encyclopedia of Integer Sequenceという整数の系列の
データベースにも掲載されました。
今回の世界記録樹立に関する成果は、電子情報通信学会のレターとしての採録
が決まっています。
また、計算に利用したプログラムを誰でも容易に利用できるベンチマークプロ
グラムとして公開しており、この内容に関しては、FIT2004 第3回情報科学技術
フォーラムで発表済みです。
N-queensはGRIDにおけるベンチマークとしても利用されており、2004年の10月
には、GRID上でN-queensの解を計算するコンテストがフランスで開催されます。
【関連するホームページ】
並列処理学講座のホームページ
http://www.yuba.is.uec.ac.jp/
世界記録樹立者のホームページ
http://www.yuba.is.uec.ac.jp/~kis/
http://www.yuba.is.uec.ac.jp/~katagiri/
http://www.yuba.is.uec.ac.jp/~honda/
http://www.yuba.is.uec.ac.jp/~yuba/
英語の技術報告
http://www.yuba.is.uec.ac.jp/~kis/doc/paper/uec-is-2004-06.pdf
ベンチマークプログラムqn24bのホームページ
http://www.yuba.is.uec.ac.jp/~kis/nq/index.htm
On-Line Encyclopedia of Integer Sequence
http://www.research.att.com/~njas/sequences/Seis.html
GRIDコンテストに関するホームページ
http://www-sop.inria.fr/oasis/ProActive/
【本件に関するお問い合わせ先】
電気通信大学 大学院情報システム学研究科 吉瀬 謙二
E-mail: kis@is.uec.ac.jp
TEL: 0424-43-5643
FAX: 0424-43-5644
〒182-8585 東京都調布市調布ヶ丘1-5-1
電気通信大学 大学院情報システム学研究科
≪--- プレスリリース配信：＠Press http://www.atpress.ne.jp/ ---≫
