プログラミングパズルに関心のある人は雑談しましょう！
こんばんは、deepgreenです。
気分転換に、NQueens問題の世界記録を調べてみたら、面白いことがわかりました。
１. 世界記録は、Ｎ＝２６
Ｎ＝２４ ２００４年４月１１日 電機通信大学 68CPU x ２２日
Ｎ＝２５ ２００５年６月１１日 ProActive 単一CPU換算で５０年以上
Ｎ＝２６ ２００９年７月１１日 tu-dresden FPGA (*1) x ２４０日
*1 : 8*22 2.5 GHz-QuadCore systemsに相当（約176 * 4CPU = 704 CPU)
２．Ｎ＝２６のSolver（ＴＵＤ版と仮称）
何とtakaken版の対称性チェック処理の考え方が採用されています。
ＴＵＤ版は、takaken版の対称性チェック処理のiｆ文をＱｕｅｅｎのｐｒｅ配置により
不要とすることで、さらに高速化を実現しているようです。
★★ 高橋謙一郎さんのアルゴリズムが採用されたのは、すばらしい快挙です。
おめでとうございます。！！！
詳細は、下記のＵＲＬを参照。
en.wikipedia.org/wiki/Eight_queens_puzzle ( 全体 )
(Jeff Somer氏のオリジナル版の約４倍高速(*2)と記述して、高橋謙一郎さんの英語版HPをLink）
www.research.att.com/~njas/sequences/A000170
queens.inf.tu-dresden.de/ ( N=26の結果 )
www.mcsharp.net/nqueens.html ( Solverの簡単な説明 ）
queens.inf.tu-dresden.de/?l=en&n=r
proactive.inria.fr/index.php?page=nqueens25 ( N=25の結果 )
＊２：N=20 Jeff Somerさんの結果 (800 MHz) ２０：３５：０６
takaken版( Athlon XP 2100+ (1.73GHz) ５：０３：３５
--> ＣＰＵ能力差を無視して、割り算をすると約４倍となる。
（ＣＰＵ能力差を考慮すると、やはり２倍程度かな? ）
deepgreenさん、リコメントありがとうございます。 コメントのなかで、特に以下の部分、気になりました。 ＞メモリアクセスそのものもCPUの速度から見れば遅いのでなるべくキャッシュに乗せるような配慮を行う。 ただし、たとえご教示いただいたとしても、今の自分では活用できそうにありません。 とりあえず、一旦撤退させていただきます。 deepgreenさんのご発展お祈り申し上げます。
tsuyoshikさん、はじめまして。 deepgreenです。
ＮＱｕｅｅｎ問題に挑戦する方がいらっしゃったのは、大変うれしいです。
私も、ビット演算手法はことごとく失敗しました。原因は、探索論理が単純であるが、
絞り込みは強力である点にあると判断しました。論理を追加する場合、かなりの絞り
込みができないと絞り込みのオーバーヘッドの方が大きくなり、逆効果となります。
(ということで、数％の改善で断念しました)
tsuyoshikさんの ”端的な場面は上下半分ずつのDataをとりそれをドッキングする手法”
は、私のＨＪ版の考え方に似ているかもしれません。
ＨＪ版の基本アルゴリズムは、（Ｎ＝２４を想定した場合）
1) 部分解（１２ｘ２４の解）を求めます
この解は約１．５Ｔ個ありますので、一度にはメモリに乗せることができませんが、
takaken版（ビット演算法）を使うと約５Ｈで求まります。
2) １２ｘ２４の解を２つ組み合わせて、２４ｘ２４の解を生成します。
部分解は、メモリに乗るように、すこしづつ生成して、結合していきます。
このとき、メモリアクセスそのものもＣＰＵの速度からみれば遅いので
なるべくキャッシュにのせるような配慮を行います。
また、なるべくｕｎｉｑｕｅ解のみを生成するような配慮も必要です。
ＨＪ版の初版（基本バージョン）は、Ｎ＝１８で５７８秒（takaken版は約４分）と
大変、遅かったものです。これが、最新版では約６０秒になってます。
それだけ、いろいろな高速化を織り込む必要がありました。
（できれば、もう少し、改善したいという思いはありますが、．．．no ideaです）
今、ＱＪ版（４分割の合成）で苦戦しています。
なんとか基本バージョンは動きましたが、やはり遅いですね。今回は、ＨＪ版の部品・
アイデアを使っているので、もう少し速くないと。 お先真っ暗です。
tsuyoshikさんも頑張ってください。
まず、高橋さんの「ビット演算活用のJeff Sommersさんプログラムを再帰様式に書き直したもの」をJavaに移植しました。（全数解明版） 次に、自己版をプログラムするが全て数桁遅い。 続けて、自己版は放棄し、ビット演算手法をベースに何種か手を加えるが効果は全てマイナス。 工夫の主体は、予め複数行の特性をDataにおさめ、それを一つの行として扱う手法、端的な場面は上下半分ずつのDataをとりそれをドッキングする手法です。これは自分のrubikcubeでは相当の威力を発揮したので期待したのですが、効果ありませんでした。要因のひとつは、ビット演算の効率が非常に優れていること、次に、このNQueenの成り立ちが探索が深くなるに従い探索巾が狭くなる構造にあると思いました。 今までは外からでしたが、いちど、同じ土俵に上がり、大学生の問題に小学生が挑むような力不足を痛感しました。わざわざコメントするような内容ではないのですが、反応した者がいることをお知らせする意味で書き込みました。 自分のrubikcubeは3ステップでの解明が終わり一段落いたしました。
高橋謙一郎さん、こんばんは。 deepgreenです。
高橋さんと競いあった昔が懐かしいです。
今回も、誰か一緒に挑戦してくれる人が欲しくて早めにｕｐしました。
DG-HJ版をちょっと改良し、takaken版の約４倍の性能となりました。
DG-HJ版(改)で、ようやくQJ(Quarter Join:４分割解の合成)版の準備ができました。
QJ版は、(HJ版では不十分であった）Join処理の高速化を狙っています。
そうは言っても、どうなることやら ????
【実行結果サマリ】
DG-HJ版(改) DG-HJ版 takaken版(rerun) takaken-orginal版
N= 18 60.045 (0.26) 1:23.88 (0.37) 3:48.23 (1.0) 4:55.50 (1.29)
19 -- -- 29:22.07 (1.0) 37:49.96 (1.29)
20 54:00.057 (0.23) 1:08:56.43 (0.29) 3:54:10.34 (1.0) 5:03:35.16 (1.29)
(追記)
私の方もいろいろありまして、静岡県から生まれ故郷の茨城県に戻ってきました。
その関係で私のＨＰの契約を解除しました。（２月末以降削除される予定）
この結果は、どこかに残したいと思っていますが、まだ、未定です。
--------------------------------------------------------------------------
【DG-HJ版(改)実行結果】
unique all ms(1/1000秒)
----------- ------------ ---------
***** N= 4 1 2 0
***** N= 6 1 4 0
***** N= 8 12 92 0
***** N=10 92 724 0
***** N=12 1787 14200 16
***** N=14 45752 365596 109
***** N=16 1846955 14772512 2059
***** N=18 83263591 666090624 60045
***** N=20 4878666808 39029188884 3240057 ( 54:00.057)
deepgreenさん、お久しぶりです。 当ＨＰは放置した状態になっており、久しぶりに掲示板を見て驚きました。 それにしても３倍も高速とはすごいですね。当方は浦島太郎のように自分で 書いたソースコードも理解出来なくなっています。 解の個数を数えるのに、ｎ++ ではなく ｎ×ｍ を積み上げていく方法ですよね。 高速化の成功おめでとうございます。 いろいろあってパズルからは遠ざかった生活をしていますが、あの頃の パズルにかける熱い想いが懐かしく感じています。 大した返事も書けないかも知れませんが何かありましたら、また投稿をお願いします。 とてもいい刺激になります。
こんばんは、deepgreenです。
新しいアプローチ?の最新の状況をお知らせします。
”新しい”といってもビット演算をベースにしたtakaken版とは大きく異なる
という意味です。昔、NQueen問題に挑戦した時ｔｒｙして挫折した方法です。
その当時から、takaken版の完成度は高く、それを超えるには部分解合成法が
有力とみていました。しかし、部分解から全体を合成するjoin処理が重くて
良い結果が得られませんでした。
今回、join処理の高速化を思いついたので、再挑戦をはじめました。
現在は、HJ版(Half-Join：2分割の合成)がほぼ完成し、takaken版に比べて
Ｎ＝２０では約３倍の高速化ができました。
【実行結果サマリ】
DG-HJ版 takaken版(rerun) takaken-orginal版
N= 18 1:23.88 (0.37) 3:48.23 (1.0) 4:55.50 (1.29)
19 -- 29:22.07 (1.0) 37:49.96 (1.29)
20 1:08:56.43 (0.29) 3:54:10.34 (1.0) 5:03:35.16 (1.29)
** DG-HJ版は、２分割処理の都合で偶数のみ対応しています。奇数を求めるには、
同じ考えに基づく、別プログラムが必要です。(今のところ予定なし)
--------------------------------------------------------------------------
【DG-HJ版実行結果】
unique all ms(1/1000秒)
----------- ------------ ---------
***** N= 4 1 2 0
***** N= 6 1 4 0
***** N= 8 12 92 0
***** N=10 92 724 0
***** N=12 1787 14200 15
***** N=14 45752 365596 109
***** N=16 1846955 14772512 3261
***** N=18 83263591 666090624 83881 ( 1:23.88)
***** N=20 4878666808 39029188884 4136434 (1:08:56.43)
deepgreenです。
電気通信大学で、２００４年にＮ＝２４の解を求めたとのニュースを見つけました。
Intel Pentium 4 Xeon 2.8GHzのプロセッサを68個搭載したクラスタで
22日間。解の数は、227,514,171,973,736(全数解）
詳細は、以下のＵＲＬにあります。
http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm
また、このＨＰには論文とプログラムが公開されていたので、ダウンロードして、
ｒｅｒｕｎしてみました。
動作環境 : Pentium4 Xeon 2.8-GHz processor (single processor)
N 全数解 処理時間(秒) ｜ DG-rerun takaken改造版(DGmod版)
16 ｜ 8.66 4.32秒
17 95,815,104 55.5 ｜
18 666,090,624 384.8 ｜ 448.55 3:34.87 (214.87秒)
19 4,968,057,848 3168.6 ｜
20 39,029,188,884 24329.7 ｜ 3:36:32.96 (12992.96秒)
** DG-rerun : 電気通信大学のqn24b_baseをdeepgreenのＰＣで動作させた結果です。
deepgreenのPCは2.1GHzなので、ちょっと遅い結果となりました。
takaken改造版の方が約２倍高速です。どちらもビット演算を基本としていますが、
qn24b_baseでは、unique解を求めず全数解のみを求めています。その処理の差が
性能差となっていると思われます。並列処理を考えて、単純な方法を選択したの
かもしれません。
追記：今、以前の投稿記事をみていたら、塗り壁さんが当時見つけて報告されていま
したね。deepgreenもみていたと思いますが、すっかりわすれていました。
Ｎ＝２５の解をどこかで見つけた人はいらっしゃいますか?
deepgreenです。久しぶりに、NQueens問題に挑戦しています。
高橋謙一郎さんのＨＰのNQueenプログラム(以下 takaken版と仮称）をちょっと
改造してみました。
【実行環境】
ＣＰＵ : Intel Core2 Duo CPU T8100 2.1GHz
メモリ : 4 GB
【実行結果サマリ】
DGmod版 takaken版(rerun) takaken-orginal版
N= 18 3:34.87 (0.94) 3:48.23 (1.0) 4:55.50 (1.29)
19 27:04.72 (0.92) 29:22.07 (1.0) 37:49.96 (1.29)
20 3:36:32.96 (0.92) 3:54:10.34 (1.0) 5:03:35.16 (1.29)
a. DGmod版 : takaken版を数行変更したもの
b. takaken版(rerun) : takaken版をdeepgreenのＰＣでrerunした結果
c. takaken-orginal版 : 高橋謙一郎さんのＨＰの結果を転記
ｂとｃの差は、ＰＣの性能差をみるための比較
ａとｂの差は、改造の効果を表している
★ DGmod版の改善効果はわずかです。
takaken版の完成度が高く、ビット演算をべースにしたアプローチでの
これ以上の改善は難しいという感じがします。
-----------------------------------------------------------------------------
【takaken-DGmod版実行結果】
<------ N-Queens Solutions -----> <---- time ---->
N: Total Unique days hh:mm:ss.--
2: 0 0 0.00
3: 0 0 0.00
4: 2 1 0.00
5: 10 2 0.00
6: 4 1 0.00
7: 40 6 0.00
8: 92 12 0.00
9: 352 46 0.00
10: 724 92 0.00
11: 2680 341 0.00
12: 14200 1787 0.00
13: 73712 9233 0.03
14: 365596 45752 0.11
15: 2279184 285053 0.69
16: 14772512 1846955 4.32
17: 95815104 11977939 29.72
18: 666090624 83263591 3:34.87
19: 4968057848 621012754 27:04.72
20: 39029188884 4878666808 3:36:32.96
21: 314666222712 39333324973 1 06:19:05.10
【takaken版rerun実行結果】
===== takaken orginal source ====
<------ N-Queens Solutions -----> <---- time ---->
N: Total Unique days hh:mm:ss.--
2: 0 0 0.00
3: 0 0 0.00
4: 2 1 0.00
5: 10 2 0.00
6: 4 1 0.00
7: 40 6 0.00
8: 92 12 0.00
9: 352 46 0.00
10: 724 92 0.00
11: 2680 341 0.00
12: 14200 1787 0.01
13: 73712 9233 0.02
14: 365596 45752 0.11
15: 2279184 285053 0.70
16: 14772512 1846955 4.68
17: 95815104 11977939 31.97
18: 666090624 83263591 3:48.23
19: 4968057848 621012754 29:22.07
20: 39029188884 4878666808 3:54:10.34
解けない面が有るので、バージョンアップしてください。