-
Notifications
You must be signed in to change notification settings - Fork 1
【エイト・クイーン】超高速化手法を詳細説明。N-Queens問題で様々なアルゴリズムをステップバイステップで学ぶ。再帰処理やブルートフォース、バックトラックやビット処理、反転斜軸処理による高速化手法を詳細に記述 世界記録2009年ドレスデン工科大学N26をPCで実現【Ｎクイーン】 Familiarize with algorithm basics such as sorting and recursion and learn the N-Queen problem step by step. Describe the speed-up method by recursion, brute force, backtracking, bit processing and reverse o…
suzukiiichiro/N-Queens
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
/**
------------------- ---------------------------------------
Python/Java/C/Lua/Bash/CUDA で学ぶアルゴリズムとデータ構造
「ステップバイステップでＮ−クイーン問題を最適化」
一般社団法人 共同通信社 情報技術局次長 将来技術開発室長
鈴木維一郎(suzuki.iichiro@kyodonews.jp)
------------------------------------------------------------
Ｎクイーンデモページ
https://suzukiiichiro.github.io/demo/
# 実行
$ nvcc -O3 -arch=sm_61 -m64 -ptx -prec-div=false 04CUDA_Symmetry_BitBoard.cu && POCL_DEBUG=all ./a.out -n ;
# 実行結果
11Bit_CUDA/04CUDA_Symmetry_BitBoard.cu
対称解除法 GPUビットボード
N: Total Unique dd:hh:mm:ss.ms
4: 2 1 000:00:00:00.00
5: 10 2 000:00:00:00.00
6: 4 1 000:00:00:00.00
7: 40 6 000:00:00:00.00
8: 92 12 000:00:00:00.01
9: 352 46 000:00:00:00.01
10: 724 92 000:00:00:00.01
11: 2680 341 000:00:00:00.01
12: 14200 1787 000:00:00:00.02
13: 73712 9233 000:00:00:00.04
14: 365596 45752 000:00:00:00.04
15: 2279184 285053 000:00:00:00.04
16: 14772512 1846955 000:00:00:00.07
17: 95815104 11977939 000:00:00:00.26
18: 666090624 83263591 000:00:00:01.65
19: 4968057848 621012754 000:00:00:13.80
20: 39029188884 4878666808 000:00:02:02.52
21: 314666222712 39333324973 000:00:18:46.52
22: 2691008701644 336376244042 000:03:00:22.54
23: 24233937684440 3029242658210 001:06:03:49.29
24: 227514171973736 28439272956934 012:23:38:21.02
25: 2207893435808352 275986683743434 140:07:39:29.96
|| ||Bash || ||Python|| || Lua |Java | C(CPU) |CUDA(GPU)|| Nクイーン解法の高速化処理ステップ
|| || || || || || | | 再帰|非再帰| 非再帰 ||
|-----------|------------|------------------------------------------------------------------------------
|| || || || || || | | | | || １．ブルートフォース 力任せ探索
|| || || || || || | | | | || ２．配置フラグ（制約テスト高速化）
||N12||07:30||N15|| 07:54||N17||20:48|12:18| 8:40| 9:00| - || ３．バックトラック
||N12||06:48||N15|| 08:21||N17||24:31|12:51| 8:42| 8:46| - || ４．対称解除法
||N12||03:36||N15|| 04:48||N17||16:38| 3:01| 5:52| 6:12| - || ５．枝刈りと最適化
||N12||01:52||N15|| 02:05||N17||09:05| 0:58| 1:05| 1:08| 0:18.07|| ６．ビットマップ
||N12||05:47||N15|| 07:25||N17||23:09| 2:38| 2:41| 2:43| 6:04.57|| ７．ビットマップ＋対称解除法
||N12||05:54||N15|| 08:49||N17||07:33| 2:40| 1:52| 1:51| 4:21.36|| ８．ビットマップ＋対称解除法＋枝刈り
||N12||03:19||N15|| 08:06||N17||12:20| 1:38| 1:41| 1:36| 4:09.32|| ９．クイーンの位置による分岐BOUND1
||N12||03:50||N15|| 08:10||N17||12:18| 1:38| 1:32| 1:32| 4:09.09|| １０．クイーンの位置による分岐BOUND1,2
||N12||02:00||N15|| 02:27||N17||03:32| 1:34| 0:45| 0:43| 1:56.55|| １１．枝刈り
||N12||00:25||N15|| 00:54||N17||02:13| 0:14| 0:18| 0:15| 0:10.87|| １２．最適化
||N12|| ||N15|| 00:19||N17|| | 0:04| 0:04| 0:03| 0:00.35|| １３．並列処理
# Python/Java/C/Lua/Bash版のN-Queen
# https://github.com/suzukiiichiro/N-Queen
# 最新のディレクトリ以下のディレクトリで、多くの部分をビット処理を行っています。
08Bit_Bash
09Bit_GCC
10Bit_Python
11Bit_CUDA
こちらでロジックなどを詳細に説明しています。
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
================
ディレクトリ説明
================
01Bash/
Bash版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
# N: Total Unique hh:mm:ss
# 2: 0 0 0:00:00
# 3: 0 0 0:00:00
# 4: 2 1 0:00:00
# 5: 10 2 0:00:00
# 6: 4 1 0:00:00
# 7: 40 6 0:00:00
# 8: 92 12 0:00:00
# 9: 352 46 0:00:00
# 10: 724 92 0:00:01
# 11: 2680 341 0:00:05
# 12: 14200 1787 0:00:25
02Lua/
# Lua版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
N: Total Unique hh:mm:ss
2: 0 0 00:00:00
3: 0 0 00:00:00
4: 2 1 00:00:00
5: 10 2 00:00:00
6: 4 1 00:00:00
7: 40 6 00:00:00
8: 92 12 00:00:00
9: 352 46 00:00:00
10: 724 92 00:00:00
11: 2680 341 00:00:00
12: 14200 1787 00:00:00
13: 73712 9233 00:00:00
14: 365596 45752 00:00:00
15: 2279184 285053 00:00:03
16: 14772512 1846955 00:00:20
17: 95815104 11977939 00:02:13
03Python/
# Python版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
# N: Total Unique hh:mm:ss.ms
# 4: 2 1 0:00:00.124
# 5: 10 2 0:00:00.110
# 6: 4 1 0:00:00.116
# 7: 40 6 0:00:00.115
# 8: 92 12 0:00:00.119
# 9: 352 46 0:00:00.118
# 10: 724 92 0:00:00.121
# 11: 2680 341 0:00:00.122
# 12: 14200 1787 0:00:00.228
# 13: 73712 9233 0:00:00.641
# 14: 365596 45752 0:00:03.227
# 15: 2279184 285053 0:00:19.973
04Java/
# Java版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
N: Total Unique hh:mm:ss.SSS
4: 2 1 00:00:00.001
5: 10 2 00:00:00.001
6: 4 1 00:00:00.000
7: 40 6 00:00:00.001
8: 92 12 00:00:00.001
9: 352 46 00:00:00.001
10: 724 92 00:00:00.001
11: 2680 341 00:00:00.003
12: 14200 1787 00:00:00.002
13: 73712 9233 00:00:00.005
14: 365596 45752 00:00:00.021
15: 2279184 285053 00:00:00.102
16: 14772512 1846955 00:00:00.631
17: 95815104 11977939 00:00:04.253
05C/
# C版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
N: Total Unique dd:hh:mm:ss.ms
2: 0 0 00:00:00:00.00
3: 0 0 00:00:00:00.00
4: 2 1 00:00:00:00.00
5: 10 2 00:00:00:00.00
6: 4 1 00:00:00:00.00
7: 40 6 00:00:00:00.00
8: 92 12 00:00:00:00.00
9: 352 46 00:00:00:00.00
10: 724 92 00:00:00:00.00
11: 2680 341 00:00:00:00.00
12: 14200 1787 00:00:00:00.00
13: 73712 9233 00:00:00:00.00
14: 365596 45752 00:00:00:00.01
15: 2279184 285053 00:00:00:00.07
16: 14772512 1846955 00:00:00:00.52
17: 95815104 11977939 00:00:00:03.86
18: 666090624 83263591 00:00:00:30.94
19: 4968057848 621012754 00:00:05:08.98
20: 39029188884 4878666808 00:00:40:31.91
21: 314666222712 39333324973 00:05:38:49.56
22: 2691008701644 336376244042 02:02:03:49.27
23: 24233937684440 3029242658210 22:12:20:11.13
06OpenCL/
# OpenCL版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
57. GPU(07_55 *N*si*si*si アルゴリムは全部のせ 構造体分割+BOUND1によるバケツリレー)
N: Total Unique dd:hh:mm:ss.ms
4: 8 4 00:00:00:00.30
5: 10 22 00:00:00:00.26
6: 4 127 00:00:00:00.27
7: 40 377 00:00:00:00.27
8: 92 828 00:00:00:00.27
9: 352 1567 00:00:00:00.29
10: 724 2632 00:00:00:00.28
11: 2680 4268 00:00:00:00.29
12: 14200 7523 00:00:00:00.30
13: 73712 17254 00:00:00:00.29
14: 365596 56588 00:00:00:00.44
15: 2279184 299288 00:00:00:00.92
16: 14772512 1865227 00:00:00:04.26
17: 95815104 12000940 00:00:00:35.17
18: 666090624 83292067 00:00:03:52.20
19: 4968057848 621047505 00:00:28:07.91
07CUDA/
# GPU nvcc版 以下のBit版を作成する前のバージョンです。値をビットではなく配列で管理しています。
$ nvcc -O3 CUDA13_N-Queen.cu && ./a.out -g
１３．GPU 非再帰 並列処理 CUDA
N: Total Unique dd:hh:mm:ss.ms
4: 2 1 00:00:00:00.37
5: 10 2 00:00:00:00.00
6: 4 1 00:00:00:00.00
7: 40 6 00:00:00:00.00
8: 92 12 00:00:00:00.01
9: 352 46 00:00:00:00.01
10: 724 92 00:00:00:00.01
11: 2680 341 00:00:00:00.01
12: 14200 1787 00:00:00:00.02
13: 73712 9233 00:00:00:00.03
14: 365596 45752 00:00:00:00.03
15: 2279184 285053 00:00:00:00.04
16: 14772512 1846955 00:00:00:00.08
17: 95815104 11977939 00:00:00:00.35
18: 666090624 83263591 00:00:00:02.60
19: 4968057848 621012754 00:00:00:22.23
20: 39029188884 4878666808 00:00:03:26.80
21: 314666222712 39333324973 00:00:33:09.52
以下は、値を配列からビットで管理しています。
すべてをビット計算によって高速に処理し、メモリも最小限に抑えることができます。
速度は上記の対象解除法が一枚上手ではありますが、長時間の処理でＮの限界まで挑戦するという目的では、以下のシリーズ（キャリーチェーン）が良いと思います。
# 08Bit_Bash/
Bashでアルゴリズムを学ぶのに最適です。 並列処理に`xargs`を使っています。
こちらでロジックなどを詳細に説明しています。
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
## bash版
<> 08Bash_carryChain_parallel.sh 並列処理
N: Total Unique hh:mm:ss
4: 0 0 0:00:00
5: 8 1 0:00:00
6: 4 1 0:00:00
7: 40 6 0:00:00
8: 92 12 0:00:01
9: 352 46 0:00:03
10: 724 92 0:00:15
11: 2680 341 0:00:52
12: 14200 1788 0:02:49
13: 73712 9237 0:09:18
14: 365596 45771 0:28:48
15: 2279184 285095 1:49:12
# 09Bit_GCC/
Ｃ言語で安定と省メモリに特化したビット処理ロジックを`pthread`で並列処理しています。
現存するエイトクイーンの中で最も高速で安定したプログラムです。
こちらでロジックなどを詳細に説明しています。
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
bash-3.2$ gcc -Wshift-negative-value -Wall -W -O3 -g -ftrapv -std=c99 -mtune=native -march=native 17GCC_carryChain.c -o 17GCC && ./17GCC
７．キャリーチェーン
N: Total Unique dd:hh:mm:ss.ms
4: 2 1 00:00:00:00.00
5: 10 2 00:00:00:00.00
6: 4 1 00:00:00:00.00
7: 40 6 00:00:00:00.00
8: 92 12 00:00:00:00.00
9: 352 46 00:00:00:00.00
10: 724 92 00:00:00:00.00
11: 2680 341 00:00:00:00.00
12: 14200 1788 00:00:00:00.00
13: 73712 9237 00:00:00:00.01
14: 365596 45771 00:00:00:00.06
15: 2279184 285095 00:00:00:00.25
16: 14772512 1847425 00:00:00:01.42
17: 95815104 11979381 00:00:00:10.25
18: 666090624 83274576 00:00:01:17.58
19: 4968057848 621051686 00:00:09:19.01
20: 39029188884 4878995797 00:01:12:06.58
bash-3.2$
# 10Bit_Python/
09BIt_GCCをPythonに移植しています。マルチスレッド、マルチプロセスで動作しますが、処理速度は期待できません。
こちらでロジックなどを詳細に説明しています。
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
bash-3.2$ python 13Python_multiProcess.py
キャリーチェーン マルチプロセス
N: Total Unique hh:mm:ss.ms
5: 10 2 0:00:00.061
6: 4 1 0:00:00.126
7: 40 6 0:00:00.135
8: 92 12 0:00:00.327
9: 352 46 0:00:00.766
10: 724 92 0:00:02.327
11: 2680 341 0:00:09.042
12: 14200 1788 0:00:19.871
13: 73712 9237 0:00:53.388
14: 365596 45771 0:02:19.974
15: 2279184 285095 0:05:51.522
16: 14772512 1847425 0:17:01.656
17: 95815104 11979381 1:07:04.713
bash-3.2$ python 13Python_multiProcess.py
キャリーチェーン マルチプロセス
N: Total Unique hh:mm:ss.ms
5: 10 2 0:00:00.061
6: 4 1 0:00:00.126
7: 40 6 0:00:00.135
8: 92 12 0:00:00.327
9: 352 46 0:00:00.766
10: 724 92 0:00:02.327
11: 2680 341 0:00:09.042
12: 14200 1788 0:00:19.871
13: 73712 9237 0:00:53.388
14: 365596 45771 0:02:19.974
15: 2279184 285095 0:05:51.522
16: 14772512 1847425 0:17:01.656
17: 95815104 11979381 1:07:04.713
# 11Bit_CUDA/
09Bit_GCCをCUDAに移植したプログラムで、現在開発中です。過去の`07CUDA`は、Ｎ２５でメモリ量が肥大し、システムはバーストしましたが、こちらのバージョンでＮ２５を解決することができました。
こちらでロジックなどを詳細に説明しています。
https://suzukiiichiro.github.io/search/?keyword=Ｎクイーン問題
対称解除法 GPUビットボード
N: Total Unique dd:hh:mm:ss.ms
4: 2 1 000:00:00:00.00
5: 10 2 000:00:00:00.00
6: 4 1 000:00:00:00.00
7: 40 6 000:00:00:00.00
8: 92 12 000:00:00:00.01
9: 352 46 000:00:00:00.01
10: 724 92 000:00:00:00.01
11: 2680 341 000:00:00:00.01
12: 14200 1787 000:00:00:00.02
13: 73712 9233 000:00:00:00.04
14: 365596 45752 000:00:00:00.04
15: 2279184 285053 000:00:00:00.04
16: 14772512 1846955 000:00:00:00.07
17: 95815104 11977939 000:00:00:00.26
18: 666090624 83263591 000:00:00:01.65
19: 4968057848 621012754 000:00:00:13.80
20: 39029188884 4878666808 000:00:02:02.52
21: 314666222712 39333324973 000:00:18:46.52
22: 2691008701644 336376244042 000:03:00:22.54
23: 24233937684440 3029242658210 001:06:03:49.29
24: 227514171973736 28439272956934 012:23:38:21.02
25: 2207893435808352 275986683743434 140:07:39:29.96
Ｎクイーンデモページ
https://suzukiiichiro.github.io/N-Queens/demo/
世界一 日本一 分解合成法 対照解除法 ビットマップ
-------------------------------------- 鈴木維一郎 dresden ProAct 電通大 QJH版 高橋謙一郎 Somers版(N22)
N: Total Unique dd:hh:mm:ss
2: 0 0 00:00:00:00
3: 0 0 00:00:00:00
4: 2 1 00:00:00:00
5: 10 2 00:00:00:00
6: 4 1 00:00:00:00
7: 40 6 00:00:00:00
8: 92 12 00:00:00:00
9: 352 46 00:00:00:00
10: 724 92 00:00:00:00
11: 2680 341 00:00:00:00
12: 14200 1787 00:00:00:00
13: 73712 9233 00:00:00:00
14: 365596 45752 00:00:00:00
15: 2279184 285053 00:00:00:00 00:00:00:00 00:00:00:00 00:00:04
16: 14772512 1846955 00:00:00:00 00:00:00:00 00:00:00:04 00:00:23
17: 95815104 11977939 00:00:00:00 00:00:00:07 00:00:00:31 00:02:38
18: 666090624 83263591 00:00:00:01 00:00:00:12 00:00:00:25 00:00:03:48 00:19:26
19: 4968057848 621012754 00:00:00:13 00:00:00:42 00:00:03:17 00:00:29:22 02:31:24
20: 39029188884 4878666808 00:00:02:02 00:00:04:46 00:00:24:07 00:03:54:10 20:35:06
21: 314666222712 39333324973 00:00:18:46 00:00:41:37 00:03:05:28 01:09:17:19
22 2691008701644 336376244042 00:03:00:22 00:05:50:02 01:03:08:20
23 24233937684440 3029242658210 01:06:03:49 02:08:52:30
24 227514171973736 28439272956934 12:23:38:21 21:18:10:31
25 2207893435808352 275986683743434 140:07:39:29
26 22317699616364044 2789712466510289 240日
27 23490796715412252829363791967678199 一年以上
*****************************
N-Queens問題とは
*****************************
Nクイーン問題とは、「8列×8行のチェスボードに8個のクイーンを、互いに効きが
当たらないように並べよ」という８クイーン問題のクイーン(N)を、どこまで大き
なNまで解を求めることができるかという問題。
クイーンとは、チェスで使われているクイーンを指し、チェス盤の中で、縦、横、
斜めにどこまでも進むことができる駒で、日本の将棋でいう「飛車と角」を合わ
せた動きとなる。８列×８行で構成される一般的なチェスボードにおける8-Queens
問題の解は、解の総数は92個である。比較的単純な問題なので、学部レベルの演
習問題として取り上げられることが多い。
8-Queens問題程度であれば、人力またはプログラムによる「力まかせ探索」でも
解を求めることができるが、Nが大きくなると解が一気に爆発し、実用的な時間で
は解けなくなる。
現在すべての解が判明しているものは、2004年に電気通信大学でIntel Pentium 4
Xeon 2.8GHzのプロセッサを68個搭載するPCクラスタ×20日をかけてn=24を解決し、
世界一に、その後2005 年にニッツァ大学でn=25、2009年にドレスデン工科大学で
N-26、さらに2016年に同工科大学でN=27の解を求めることに成功している。
JeffSommers氏のビット演算を用いたエレガントなアルゴリズムに加え、対称解除
法、並列処理、部分解合成法、圧縮や枝刈りなど、先端技術でワールドレコードが
次々と更新されている。
歴史あるチェスのパズル問題が現代数学における未解決問題の解明につながる可能性
https://gigazine.net/news/20170905-million-dollar-chess-problem/
Nクイーンは今のコンピュータでは絶対解けない。解けたら1億円もらえるよ
https://www.gizmodo.jp/2017/10/eight-queens-puzzle.html
解けたら賞金1億円！ 数学の7つの未解決問題のひとつ「P≠NP」問題へのアプローチがもたらすもの
https://logmi.jp/tech/articles/45330
N24 ２００４年４月１１日 電気通信大学 2004年4月 68CPU x 22日(1,496 CPU日 N24)
N25 ２００５年６月１１日 ProActive 2005年5月 185 days 4 hours 54 minutes 52 seconds 854
Java grid computation by INRIA, France
Real >6 Months
Sequential >53 Years
http://www-sop.inria.fr/oasis/ProActive2/apps/nqueens25.html
N26 ２００９年７月１１日 tu-dresden FPGA ( *1 : 8*22 2.5 GHz-QuadCore systemsに相当（約176 * 4CPU = 704 CPU)) x ２４０日(168,960 CPU日 N26)
9-month cpmputation of FPGAs completing July 1,2009.
Result confirmed by Russian MC# super computing project on August 30,2009.
N27 ２０１６年 月 日 tu-dresden
https://github.com/preusser/q27
JSomers版 (N=22)
巧みなビット演算による高速化
上下反転の解を考慮し、探索を半分に削減
Jeff Somers氏がN=23の解を求めるときに使用した解法
電気通信大学版 qn24b (N=24)
JSomers版を改良し、７〜２４％の性能向上
電通大でN=24を求めるときに使用した解法
ProActive(N=25)
http://www-sop.inria.fr/oasis/ProActive2/apps/nqueens25.html
takaken版
JSomers版を高橋謙一郎氏が改良
対称性に着目して代表解のみを探索
再帰呼び出しによるプログラム解毒性の向上
*************************
はじめに
*************************
幸運にもこのページを参照することができたN-Queen(Nクイーン）エンジニアは少数だろう。
Google検索またはGit検索でたどり着いたのだとは思うが、確率は奇跡に近い。
エンジニアにしてこのページを参照できた奇跡ついでにもう少しだけ読み進めて欲しい。
具体的には以下のリンクにわかりやすく書いてある。
エイト・クイーン問題
https://ja.wikipedia.org/wiki/エイト・クイーン
エイト・クイーンは、1848年から存在し、ガウスなど著名な科学者が研究した工学研究の
頂点となる研究である。名前の通り８つのクイーンの解を求めるというパズルであり、
Nクイーンは、エイトクイーンの拡張版で、Nの値は８、９、１０，１１，１２･･･と言った風
に増え続け、そのNの値であるボードの解を求めるものである。
*************************
歴史的未解決問題に懸賞金
*************************
歴史あるチェスのパズル問題が現代数学における未解決問題の解明につながる可能性
http://gigazine.net/news/20170905-million-dollar-chess-problem/
1000年を超える歴史を持つボードゲーム「チェス」には単なるゲームの勝敗ではなく、
そのルールに即したさまざまなパズルの課題「チェス・プロブレム」が存在しています。
エイト・クイーンはチェスの駒のうち、8個のクイーンだけを使うパズルなのですが、そ
の規模を大きく拡大して行くと、現代数学における未解決問題であり、1億円の賞金がか
かる「P対NP問題」の解明につながるものと考えられています。
2017 | “Simple” chess puzzle holds key to $1m prize | University of St Andrews
https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
Can You Solve the Million-Dollar, Unsolvable Chess Problem? - Atlas Obscura
http://www.atlasobscura.com/articles/queens-puzzle-chess-problem-solution-software
Nクイーンは今のコンピュータでは絶対解けない。解けたら1億円もらえるよ
https://www.gizmodo.jp/2017/10/eight-queens-puzzle.html
「エイト・クイーン」は1848年にチェスプレイヤーのマックス・ベッツェルによって提
案されたパズル。8×8マスのチェス盤の上に、縦横と斜め方向にどこまででも進めるとい
う駒・クイーンを8個並べるというものなのですが、その際には「どの駒も他の駒に取ら
れるような位置においてはいけない」というルールが設定されています。このルールに
従った場合にいくつの正解が存在するのか、長らくの間にわたって謎とされていたので
すが、考案から100年以上が経過した1874年にGuntherが行列式を用いて解く方法を提案
し、イギリスのグレイシャー(Glaisher)によって全解(基本解)が12個であることを確認
しています。
この問題は、チェス盤の一辺のマスの数とクイーンの数を同一にしたn-クイーン問題と
も呼ばれており、nの数が増えるに連れて飛躍的にその解数が増大することが知られてい
ます。記事作成時点で全ての解が判明しているのは、2009年にドレスデン工科大学で計
算された「26-クイーン」で、その基本解は2789兆7124億6651万289個、転回形などのバ
リエーション解を含めると、その数は2京2317兆6996億1636万4044個にもなることがわかっ
ています。
セント・アンドルーズ大学のコンピューターサイエンティストであるIan Gent博士らに
よる研究チームは、この「n-クイーン問題」から派生する「n-クイーン穴埋め問題」
(n-Queens Completion)パズルの複雑性に関する(PDF
http://jair.org/media/5512/live-5512-10126-jair.pdf)論文を作成しています。n-ク
イーン穴埋め問題は、チェス盤の上にあらかじめいくつかのクイーンの駒を並べておい
た状態で、残りのクイーンを全て埋めるというパズル問題です。
基本的にこの問題を解決するためにはバックトラック法と呼ばれる、いわば「総当たり
法」が用いられますが、全ての選択肢を試すためには膨大な時間が必要とされ、しかも
マスとクイーンの数が多くなるとその時間は指数関数的に一気に増加します。Gent氏に
よると、この「n-クイーン穴埋め問題」を素早く解決できるコンピューターやアルゴリ
ズムの開発が進むことで、我々が日々抱えている問題を解決する技術の進化が期待でき
るとのこと。先述のように、現代の科学でも解決できているn-クイーン問題は26×26マス
の「26-クイーン」にとどまっており、穴埋め問題であってもそこから先へと進むために
は、現在はまだ存在していない新しい技術を開発することが必須となってきます。
この問題は、2000年にアメリカのクレイ数学研究所が100万ドル(約1億1000万円)の賞金
とともに設定したミレニアム懸賞問題の一つに数えられる「P対NP問題」の証明につなが
るものとされています。これは、「答えを見つけるのは難しいかもしれないが、答えが
あっているかどうかは素早くチェックできる問題」のことをNP問題、「簡単に素早く解
ける問題」のことをP問題とした時に、「素早く解けるP問題はすべて答えを素早く確認
できるNP問題である」ことは証明されているが、その逆、つまり「答えを素早く確認で
きるNP問題はすべて、素早く解けるか？」という問題を証明するというもの。 これを解
くためには膨大な量の計算を素早く行うことが必要になり、現代のコンピューター技術
でも解決までには数万年の時間が必要になると考えられています。
*************************
参考リンクなど
*************************
GooleなどWebを探索すると無数のページがあることがわかる。その中でも充実したサイトを
紹介したい。おおよそ以下のサイトをかみしめて読み解けば情報は９０％網羅されている。
N-Queens 問題(Nobuhide Tsudaさん)
*************************
はじめに
力まかせ探索（Brute-force search）
バックトラッキング
制約テスト高速化（配置フラグ）
ビット演算（ビットマップ）による高速化
対称解除去
枝刈りによる高速化
http://vivi.dyndns.org/tech/puzzle/NQueen.html
Puzzle DE Programming(M.Hiroiさん）
*************************
バックトラックとビット演算による高速化
http://www.geocities.jp/m_hiroi/puzzle/nqueens.html
takakenさん（高橋謙一郎さん）のページ
*************************
Ｎクイーン問題（解の個数を求める）
ビット処理を用いた基本形
ビット処理を用いたプログラムの仕組み
ユニーク解の判定方法
ユニーク解の個数を求める
ユニーク解から全解への展開
ソースプログラムと実行結果
http://www.ic-net.or.jp/home/takaken/nt/queen/index.html
の、みなさんが掲示板で議論している模様(貴重ですね）
http://www2.ic-net.or.jp/~takaken/auto/guest/bbs62.html
ptimal Queens
*************************
英語だが、上記の全てがJavaで書かれていて群を抜いている
http://penguin.ewu.edu/~trolfe/Queens/OptQueen.html
その他のリンク
https://rosettacode.org/wiki/N-queens_problem
http://www.cc.kyoto-su.ac.jp/~yamada/ap/backtrack.html
http://yucchi.jp/java/java_tip/n_queens_problem/n_queens_problem.html
http://www.shido.info/py/queen_py3.html
http://toraneko75.sakura.ne.jp/wp/?p=223
http://yoshiiz.blog129.fc2.com/blog-entry-380.html
http://nw.tsuda.ac.jp/class/algoB/c6.html
http://www.kawa.net/works/js/8queens/nqueens.html
http://www.yasugi.ai.kyutech.ac.jp/2012/4/nq.html
http://www.neuro.sfc.keio.ac.jp/~masato/jv/nqueen/MPneuron.java
http://fujimura2.fiw-web.net/java/lang/page-20-3.html
https://github.com/pankajmore/DPP/blob/master/EPI/src/puzzles/NQueens.java
http://www.kanadas.com/ccm/queens-sort/index-j.html
http://chiiji.s10.xrea.com/nn/nqueen/nqueenn.shtml
http://www.neuro.sfc.keio.ac.jp/~masato/jv/nqueen/nqueenDemo.htm
ここからは参考情報のメモとして
N=22発見 JeffSomers
ビットマップを N-Queens に最初に応用したのは Jeff Somers 氏のようだ。
参照：The N Queens Problem
http://www.jsomers.com/nqueen_demo/nqueens.html(リンク切れのようだ）
N=24発見 電気通信大学
2004年、電気通信大学の研究グループが、処理を並列化し
N=24 の解の個数を世界で初めて発見。
http://www.arch.cs.titech.ac.jp/~kise/nq/
プレスリリース
http://www.arch.cs.titech.ac.jp/~kise/nq/press-2004-10-05.txt
電通大が「N-queens」問題の世界記録達成
http://www.itmedia.co.jp/news/articles/0410/06/news079.html
University of North Texas
http://larc.unt.edu/ian/24queens/
NQueens問題
ＱＪＨの基本構想は、”部分解から全体解を構成するというアプローチ”（部分解合成法：Ｐａｒts Assembly Approach)です。
http://deepgreen.game.coocan.jp/NQueens/nqueen_index.htm
N Queens World records
http://www.nqueens.de/sub/WorldRecord.en.html
N=21-23 computed by Sylvain PION (Sylvain.Pion(AT)sophia.inria.fr) and Joel-Yann FOURRE (Joel-Yann.Fourre(AT)ens.fr).
N=24 from Kenji KISE (kis(AT)is.uec.ac.jp), Sep 01 2004
N=25 from Objectweb ProActive INRIA Team (proactive(AT)objectweb.org), Jun 11 2005 [Communicated by Alexandre Di Costanzo (Alexandre.Di_Costanzo(AT)sophia.inria.fr)]. This calculation took about 53 years of CPU time.N=25 has been confirmed by the NTU 25Queen Project at National Taiwan University and Ming Chuan University, led by Yuh-Pyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.
N=26 as calculated by Queens(AT)TUD [http://queens.inf.tu-dresden.de/]. - Thomas B. Preußer, Jul 11 2009
N=27 as calculated by the Q27 Project [https://github.com/preusser/q27]. - Thomas B. Preußer, Sep 23 2016
*****************************
このぺーじにはなにがあるのか
*****************************
具体的にこのページにはNクイーンのプログラムがある。
コンパイル
$ gcc -pthread -O3 -Wall 07_**NQueen.c -o NQueen
実行
$ ./NQueen
を試して欲しい。
Nクイーンの解決には処理を分解して一つ一つ丁寧に理解すべくステップが必要だ。
最初はステップ１のソースを何度も見て書いて理解するしかない。
もちろん、簡単なだけに解決時間も相当かかる。処理が終わるまでにコーヒーが飲み終わってしまうかもしれない。
ステップ15までくると、およそ１秒もかからずに処理が終了する。１分かかっていたことが１秒で終わることに
興味がわかないかもしれない。がしかし、１００年かかることが１年かからないとしたらどうだろう。
人工知能AI技術は、デバイスの進化、処理の高速化、解法の最適化（アルゴリズム）の三位一体だ。
順番に、とばすことなくじっくりと読み進めて欲しい。たぶん、日本中のNクイーンプログラムをここまで分解して
ステップにまとめているサイトはそう多くはないはずだ。
さらに、このサイトはNクイーンプログラムを複数のプログラム言語で習熟出来る準備がある。
例えば以下の通りだ。
Java版 N-Queen
https://github.com/suzukiiichiro/AI_Algorithm_N-Queen
Bash版 N-Queen
https://github.com/suzukiiichiro/AI_Algorithm_Bash
Lua版 N-Queen
https://github.com/suzukiiichiro/AI_Algorithm_Lua
C版 N-Queen
https://github.com/suzukiiichiro/AI_Algorithm_C
C版
およそ全てのプログラム言語の中で最も高速に処理できると言われている。事実そうだ。
まだ何もわからない初学の人はC言語から始めるべきだ。
マルチスレッドなど、Javaに比べて複雑に記述する必要がある分、プログラムの端々までの
深い知識が必要だ。C言語マスターは間違いなく、Javaプログラマよりシステム技術を網羅的に深く理解している。
Java版
C言語があまりにも難解と言われ、取っつきやすい部分を残し、Cでできることを取りこぼさずにできた言語がJavaだ。
マルチスレッドも、C言語よりもわかりやすい。システム技術の表層的な知識だけしかないのであればJavaがよい。
システムがわかった気になる危険な言語でもある。結論から言えばJavaができてもLinuxコマンドやBash、カーネルの
理解は１つも進まない。
Bash版
Linux/UNIXを学ぶのであればBash版をおすすめする。
https://github.com/suzukiiichiro/AI_Algorithm_Bash
なぜBashなのかは以下に書いておいた。
https://github.com/suzukiiichiro/AI_Algorithm_Bash/blob/master/002UNIXBasic
Bashは遅い。だが強力だ。Linuxの力を手に入れることができる。
どの言語で学ぶのかを迷っているのであれば迷わず「Bash」を選んで欲しい。
その次はLua->Java->Cだ。
Lua版
スマートフォンアプリが世の中のテクノロジーを牽引しているのは間違いない。
そのアプリ開発で幅を利かせているのがLua言語だ。コンパクトで高速、周りとの相性も良いときている。
上記、どの言語から始めても良いと思う。できる人はどの言語でもすらすら書ける。
では、以下から本題に入る。
各お好みの言語ディレクトリのREADMEを見て欲しい。では
About
【エイト・クイーン】超高速化手法を詳細説明。N-Queens問題で様々なアルゴリズムをステップバイステップで学ぶ。再帰処理やブルートフォース、バックトラックやビット処理、反転斜軸処理による高速化手法を詳細に記述 世界記録2009年ドレスデン工科大学N26をPCで実現【Ｎクイーン】 Familiarize with algorithm basics such as sorting and recursion and learn the N-Queen problem step by step. Describe the speed-up method by recursion, brute force, backtracking, bit processing and reverse o…
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published