タイトル: N-queensの世界記録樹立,6年分の計算を並列処理により22日に短縮 本文: 報道関係者各位                      2003年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 電気通信大学 大学院情報システム学研究科