NQueens問題は、古典的に有名なパズルですので、パズルの説明等は割愛します。（パズルなどを知りたい方は [4] 参考情報をどうぞ）
以下では、ＮＱueens問題のＳｏｌｖｅｒであるＱＪＨについて情報を公開します。ＱＪＨの開発は、２００９年暮から２０１０年５月（偶数版）、〜２０１０年７月（奇数版）に行いました。
ＱＪＨの基本構想は、”部分解から全体解を構成するというアプローチ”（部分解合成法：Ｐａｒts Assembly Approach)です。
ＱＪＨ は、１／４部分解から全体解を合成する方式を採用しました。１／４部分解を求めることは、全体解に比べて遥かに簡単（高速）です。それを合成する基本論理 も単純です。しかし、高速に合成していく過程はちょっと複雑です。パソコンの基本アーキテクチャの基礎知識が必要となります。ソースプログラムはちょっと 複雑で難しいので、第２６回ゲーム情報学研究会(2011.07.01 sig-GI-26)で発表した資料とあわせてご覧いただければと思います。
ＮＱueens 問題の解法は、ＪｅｆfSomers氏の提案されたビット演算法が主流です。ＱＪＨのようなアプローチは見かけません。まだまだ、改善の余地があるでしょ う。お気づきの点等がございましたら、掲示板または、deepgreen宛てのメールでご連絡いただければ幸いです。
| N | 解の数 | QJH | takaken版 | 電通大(qn24b)版 | ||||
| unique解 | 全数解 | 探索時間(s) | 相対比 | 探索時間(s) | 相対比 | 探索時間(s) | 相対比 | |
| 4 | 1 | 2 | ||||||
| 5 | 2 | 10 | ||||||
| 6 | 1 | 4 | ||||||
| 7 | 6 | 40 | ||||||
| 8 | 12 | 92 | ||||||
| 9 | 46 | 352 | ||||||
| 10 | 92 | 724 | ||||||
| 11 | 341 | 2,680 | ||||||
| 12 | 1,787 | 14,200 | ||||||
| 13 | 9,233 | 73,712 | 0.03 | 0.02 | 0.05 | |||
| 14 | 45,752 | 365,596 | 0.05 | 0.11 | 0.22 | |||
| 15 | 285,053 | 2,279,184 | 0.31 | 0.70 | 1.31 | |||
| 16 | 1,846,955 | 14,772,512 | 0.78 | 1.00 | 4.68 | 6.00 | 8.25 | 10.58 |
| 17 | 11,977,939 | 95,815,104 | 7.41 | 1.00 | 31.97 | 4.31 | 1:01.17 | 8.25 |
| 18 | 83,263,591 | 666,090,624 | 25.37 | 1.00 | 3:48.23 | 9.00 | 7:00.72 | 16.59 |
| 19 | 621,012,754 | 4,968,057,848 | 3:17.59 | 1.00 | 29:22.07 | 8.92 | 57:16.60 | 17.39 |
| 20 | 4,878,666,808 | 39,029,188,884 | 24:07.04 | 1.00 | 3:54:10.34 | 9.71 | 7:19:24.77 | 18.22 |
| 21 | 39,333,324,973 | 314,666,222,712 | 3:05:28.23 | 1.00 | 1 09:17:19.48 | 10.77 | ||
| 22 | 336,376,244,042 | 2,691,008,701,644 | 1 03:08:20.47 | |||||
| Home |