N-queens Homepage in Japanese [Copyright c 2004 Kenji KISE All rights reserved.]


N-queensとは

N-queensは,互いに攻撃をおこなわないようなN個のクィーンを N x N のボードに配置する解の総数を求める問題です.
ここでいうクィーンとはチェスの駒の1つの種類のことで,縦,横,斜めの方向に移動することができます.
例えば,問題サイズが1(N=1)の問題には,1つの解が存在します.
N=2と3の問題に解は存在しません.
N=4の問題には2つの解が存在します.
問題サイズが6 (N=6) の問題には4つの解が存在します.この4つの解を下に示します.それでは,Nが大きい場合には,
いくつの解が存在するのでしょうか?それを求める問題がN-queensです.

N-queensの世界記録樹立、6年分の計算を並列処理により22日に短縮

電気通信大学 大学院情報システム学研究科 並列処理学講座(コンピュータおよびネットワークの高速化を狙いとする
並列・分散情報処理の科学と技術に関する研究)において、N-queens問題の世界記録を樹立しました。

世界記録樹立に関するプレスリリースの内容はこちら.


FireCoreクラスタ,68ノード,Intel Pentium4 Xeon 2.8GHz


qn24b: N-queens の解の数を計算するベンチマークプログラム

qn24bは,引数としてN-queensの問題サイズNを指定して,計算した解を出力します.
また,N=23までの正しい解の情報を保持しているので,これらと,計算により得られた値
とを比較することで,計算結果の正しさを検証することができます.

計算機システムや並列計算機システムの性能を評価するベンチマークとしては,十分に最適化されたプログラムを
利用することが求められます.
qn24bの計算カーネルは,世界で初めて24-queensの解を計算するために最適化を施し,
PCクラスタを用いて24-queensの世界記録を計算したプログラムと同じカーネルを利用しているので,
ベンチマークプログラムに適しています.

様々なプラットフォームに対応するために,
逐次版,MPI(Message Passing Interface)を用いた並列版, OpenMPを用いた並列版のコードを提供しています.

ベンチマーク プログラム qn24b version 1.0 はここからダウンロードしてください.


関連文献など

吉瀬謙二, 片桐孝洋, 本多弘樹, 弓場敏嗣:PCクラスタを用いたN-queens問題の求解,
電子情報通信学会レター, 掲載予定, (2004).

吉瀬謙二, 片桐孝洋, 本多弘樹, 弓場敏嗣:
qn24b:N-queensの解を計算するベンチマークプログラム,
FIT2004第3回情報科学技術フォーラム, 於 同志社大学 京田辺キャンパス, 第4分冊, No.O-011, pp. 389--392 (September 2004)

Kenji Kise, Takahiro Katagiri, Hiroki Honda, and Toshitsugu Yuba:
Solving the 24-queens Problem using MPI on a PC Cluster,
Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communications (June 2004)

吉瀬, 片桐, 本多, 弓場:Clustermaticを用いたPCクラスタの構築,
Technical Report UEC-IS-2004-3, 電気通信大学~ 大学院情報システム学研究科 (2004)


Copyright c 2004 Kenji KISE All rights reserved.