NQueens 問題への新しいアプローチ（部分解合成法）について

萩野谷 一二email : deepgreen@libra.nifty.jp

あらすじ

NQueens 問題とは準備（用語の説明）
部分解合成法（PAA）の概要
QJH-even 版の実装
QJH-odd 版の概要
実測結果
まとめ

NQueens 問題とは
下記の条件を満たすクイーン配置の数を求める問題
 N x N のチェスボードに N 個のクイーンを配置
 クイーンはお互いの効き筋をさけて配置

QQQQ

 クイーンの効き筋は縦、横、斜めの４方向

QQ

 反転対称解は存在しない
 回転対称解は存在する（90°、180°）

QQ

Q
Q

８ ｘ ８の問題の例
QQ

最近の状況
すでに解決済の問題
Ｎ

公表日

すべての解の数

unique解の数24

2004.04.11

227,514,171,973,736

28,439,272,956,934

25

2005.06.11

2,207,893,435,808,350

275,986,683,743,43426

2009.07.11

22,317,699,616,364,000

2,789,712,466,510,280

27

未解決

 クイーンの数とともに、急激に解の数も増大（約 10 倍のペース）
 N=27 以降は未解決解決に必要な CPU 資源
N

公表日

公表機関名

基本ﾌﾟﾛｸﾞﾗﾑCPU 資源（延べ） 必要な CPU 資源も約 10 倍ずつ増大

242004.04.11

電気通信大学qn24b

1,496 CPU・日[1]

 PC クラスタや FGPA を使った並列処

25

2005.06.11

ProActive

不明

18,250 CPU・日

[2]

26

2009.07.11

Tu-dresden

JSomers 版の改良版

168,960 CPU・日

[3]

理が主流

最近の Solver
Solver 名
JSomers 版(仮称）[7]qn24b [8]takaken 版(仮称）[9]特徴など 巧みなビット演算による高速化
 上下反転の解を考慮し、探索を半分に削減
 Jeff Somers 氏が N=23 の解を求めるときに使用した解法
 JSomer 版を改良し、7～14％の性能向上
 電通大で N=24 を求める時に使用した解法
 JSomer 版を高橋謙一郎氏が改良
 対称性に着目して代表解（後述）のみを探索
 再帰呼び出しによるプログラム解読性の向上

JSomers 版のビット演算

takaken 版の代表解の判定条件
Qb i t
X n+1
Ln+1
Rn+1
Mn+1

=
=
=
==-Mn ＆ M n
Xn | bit( Ln | bit ) << 1
( Rn | bit ) >> 1
(2N - 1) & ~ ( X n+1 | L n+1 |R n+1)

クイーンの配置禁止区間

開発の経緯□未解決の問題に挑戦するには、約 10 倍の性能 up が必要
takaken 版の性能 : 3.2μs / 解 1 個 ≒ 6400 クロック / 解 1 個
 JSomers 版のビット演算方式では実現困難□部分解合成法では？
N=24 の場合半分の問題（12 x 24）は約 5 時間で求まるが、全体の問題（24 x 24）は 1496 CPU・日かかる
また、半分の問題の解の数は約 1.5T 個。フレーム分割（後述）すれば、メモリ常駐可能な範囲

 可能性あり
課題はジョイン処理の高速化

解の分類
1）type-aの例

２）type-ｂの例

Q

Q
Q

Q

Q

Q

Q

Q
Q

Q

Q
Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

３）type-ｃの例
Q

Q
Q

Q

Q

Q
Q

Q

Q

Q
Q
Q

Q

type-a ： 対称性なしの解（回転や反転を行っても元の解と一致しない解）
type-b ： 180°回転対称解（180°回転すると元の解と一致する解）
type-c ：90°回転対称解（90°回転すると元の解と一致する解）

代 表 解 ： 解グループの中から 1 つを選んで代表解とする。代表の選び方は任意
unique 解 ＝ A
全数解+B+C＝ 8*A + 4*B+2*C（代表解の総和）（すべての解をカウント）

ただし、A,B,C は、それぞれ type-a，type-b，type-c の代表解の数

ボードの分割
チェスボードを縦、横にそれぞれ 2 分割。

ｎｎｎ

Ａ

Ｂｎ

時計回りに A,B,C,D とする

A～D のクイーンの数#(A) = #(C) = m#(B) = #(D) = n – mｎ

Ｄ

Ｃｎｎｎ

ただし、m = 0～n の整数⇒ A のクイーンの数が決まると、B,C,D のクイーンの数も決まる

特性値XＱＱU ＱYＱＱVX 特性値 : 各列(X 方向)のクイーンの配置を表す指標

X=101101

Y 特性値 : 各行(Y 方向)のクイーンの配置を表す指標

Y=110101

U 特性値 : ななめ方向(U 方向)のクイーンの配置を表す指標

U=00110001010

V 特性値 : ななめ方向(V 方向)のクイーンの配置を表す指標。 V=00110010100

部分解の配置とフレーム
P , Q , R , S ： 部分解の要素
A, B, C, D, a, b, c, d :

ABdＰ

Ｓa

（P, Q, R, S は、時計まわりに 90 度回転した配置）

フレーム値

cＱ

Ｒb

A ：rBit(P の X 特性値)

B ：rBit(P の Y 特性値)

C ：rBit(R の X 特性値)

D ：rBit(R の Y 特性値)

a ：rBit(S の Y 特性値)

b ：rBit(Q の X 特性値)

c ：rBit(Q の Y 特性値)

d ：rBit(S の X 特性値)

a = ～A,d = ～D という関係が成立

D
b = ～B,c = ～C,

C

フレーム値は、全体解を分割して処理するために導入した概念
補足：初版ではフレーム値＝特性値としていたが、性能面で有利なため変更

部分解合成法(PAA)の概要
QJoin
HJoin

PGen

A

B

A

B

1/4 部分解DC

D

C

解の生成は unique 解のみに限定
高速化のポイント 結合処理の高速化（特に、キャッシュミスの削減）
 代表解の判定条件による集合積演算の軽減

A

B

DC

QJoin（ 2 つの 1/4 解から 1/2 解を生成 ）
Xa

Yb
UaＱ

結合条件

VbＱ

YaXb
Va

① Ya = ～Xb② (Ua >> n) & rBit(Vb >> n) = 0Ub③ Ub & (Va >> n) == 0
XaYb

結果
Ya

U1

① U1 = Ua | (rBit(Vb>>n) << n)
U2Xb② U2 = Ub | (Va >> n)~: ビット反転
ｒBit（） : ビットの上下反転

QJoin の例
A

B
Q

Q

Q

Q

Q
Q

Q

Ya=001010
Xb=110101
Ua=00110000000 Ub=01101000001
Va=00100100000 Vb=00010111000

AB
Q
Q

Q
Q

条件①，②，③は成立
U1=01110000000
U2=01101000101

Q

HJoin （2 つの 1/2 解から全体解を生成 ）
Xa

Yb

Xa

Yb

結合条件
Ya

U1

U2Xb

Ya

U１

U２Xb

① Yb = ～Xc
Yd = ～Xa② U1 & rBit(U3) = 0③ U2 & rBit(U4) = 0

Xd

Xd

U4

U3

U4Yc
Yd

Yd

Xc

U3Xc

Yc

~: ビット反転ｒBit（） : ビットの上下反転

HJoin の例
Q
Q
Q
Q

Q
Q
Q

Q
Q

Q

Q
Q
Q

Q
Q

Q
Q

Q
Q
Xa=110000
Yb=100111
U1=01110000000
U2=01101000101

Q
Q
Xc=011000
Yd=001111
U3=01101000000
U4=01011100000

Q

Q
Q
条件①，②，③はすべて成立するので解として適切である

代表解の判定条件(unique 解の選択方法)
考え方：

①
②
③

クイーンの数の比較
フレーム値の比較
pid の比較

代表解の条件：条件 0～条件 8 をすべて満足すること
ただし、条件 4～条件 8 は、#(P) = #(Q)のときのみ
基本形

V軸反転

X軸反転

AB

ccｄ

∔90度回転

AQdB

QB

bAab

BaAQd

Daｃ

CCb

U軸反転
DQ
Dd

DC

180度回転bC

CCa

D

Y軸反転aa

Cbc

Ddd

DcAb

B

B

bA

B

DC

Q
Q

dc

-90度回転

Q
acca

Q
A

A

ｃ

B

d

条件 0 ：Q 条件

クイーンの数の比較#(P) ≦ #(Q)条件 1 ： V 条件

(B, D) or(A, C) =(B, D) and<（p’, r’）B

pdｃqｂsrDaC

１８０°

U 軸反転解との比較(A, B) <(D, C) or(A, B) =(D, C) and

条件 3 ：R180 条件

pＵ軸A

V 軸反転解との比較(A, C) <条件 2 ： U 条件

Ｖ軸p< r’180 度回転解との比較(A, B) <(C, D) or(A, B) =(C, D) and (p, q) ≦ (r, s)

A, B, C, D : フレーム値
a, b, c, d : フレーム値
p, q , r , s : p i d

以下の条件 4～条件 8 は、#(P) = #(Q)のときのみ
条件 4 ： X 条件

X 軸反転解との比較(A, B) <条件 5 ： Y 条件

Ｘ軸(c, b)
Y 軸反転解との比較

A < a

Ｙ軸 B

条件 6 ：R+90 条件 +90 度回転解との比較(A, B)<(b, c) or(A, B)=(b, c) and

条件 7 ：R-90 条件(d, a) or(A, B) =(d, a)ｃpqｂsrDaC＋９０°－９０°dp ≦ q-90 度回転解との比較(A, B) <Aand p ≦ s

A, B, C, D : フレーム値
a, b, c, d : フレーム値
p, q , r , s : p i d

条件 8 ：(A,B) = (b,c) and (A,B) = (d,a)の場合の特殊条件(i.e A=Cand B=D

case 1 : p = q

andA=~B のとき)

case1:pid3個が一致した場合

AaaｐｐAAｐｒaa

Aand p = s の場合

p = r ならtype-cp≠ｒならtype-acase2:pid2個が一致した場合

case 2 : p = q

and p ≠ s の場合

p≠ｒ and r
case 3 : p ≠ q< saaｐｐAAｓｒaaAand p = s の場合

p≠ｒ and q ≦ rcase 4 : p ≠ q

Aand p ≠ s の場合(p, q) ≦case3:pid2個が一致した場合

Aaaｐｑ

AAｐｒaaA(r, s)

解区分の判定 条件 3 で等号が成立する場合は、180 度回転対称解である（type-b）

 さらに条件 8 の case1 で等号で成り立つ場合は、90 度回転対称解である（type-c） 上記以外は、回転対称解ではない（type-a）

QJH-even 版の実装
for M = (1～n/2）//Ｑ条件よりPGen(M)PGen(n-M)
for frame.A = (１～Bit[n]-1）//ＭはサブボードＡのＱｕｅｅｎの数//部分解の作成//部分解の作成

for frame.C = (frame.A～Bit[n]-1） //R180条件より
QJoin(A,B)
QJoin(C,D)// A x B --> AB// C x D --> CD

HJoin()// AB x CD --> ABCD 代表解の判定条件は、なるべく早期に適用（絞り込み）
ほとんどは、フレーム値までの判定で決定
 フレーム A,C による解の分割処理  部分解のメモリ常駐化

PGen（1/4 部分解の生成） 基本アルゴリズムは、Jeff Somers 氏のビット演算方式を採用
 部分解は、特性値（x,y）をキーとするインデクスで管理(x,y)のインデクス・ ・ ・ ・ ・

データ(個々の部分解）は、（ｘ、ｙ）の順に並べる
部分解の構成要素： { U, V, p, r } １２B
p : 自身のpidr : 自身のV軸反転解のpid

QJoin(A,B)のインデクス・ ・ ・ ・ ・AｃBｂC

U,Vの結合条件の判定

A, C は, フレーム値で固定
B（b） は, 可変要素 A～Bit(n)-1の範囲（A, B) は、連続エリア（ｂ,ｃ) は、とびとびのエリア(b, c)と（c, ｂ）の対称性を利用して、(c,b) の連続エリアをアクセス(b,c)のインデクス

H Join
全要素同士の集合積からの絞り込みは、性能面で不可  Hash Join
Hash Key の生成
U1

U2

rBit(U3)

rBit(U4)

Hash Join の結合条件
h k e y 1 & h k e y 2 = 0 …… 条件 1

hkey1

jkey1

hkey2

jkey2

j k e y 1 & j k e y 2 = 0 …… 条件 2

hkey1: Ｕ１，Ｕ２の一部を抽出
jkey1: Ｕ１，Ｕ２からｈkey１を除いた残りのビット
hkey2: Ｕ3，Ｕ4の一部を抽出
jkey2: Ｕ3，Ｕ4からｈkey１を除いた残りのビット① hkey1 より、hkey2 をビット演算（条件１）により算出
hkey1=01011



hkey2= x0x00 = { 00000,00100,10000,10100 }② ハッシュキーのインデクスを検索して、hkey1  jkey1, hkey2  jkey2 を得る③ jkey1,jkey2の集合積より条件 2 を満たすものを選択④ 解区分が未定の場合：代表解の判定条件のチェック

ソフト Cache メモリアクセスのキャッシュミス削減
 結合条件の判定に必要な jkey2 のみを抽出 ( 22B  ４B )Jkey1の昇順
ＡＢの構成要素データ

CPU
１次cache数クロック結合条件の判定

二次cache
数百クロック
UcacheMain Memoryjkey2のみを抽出
ＣＤの構成要素データ

ＣＤの構成要素データ ： 22B{ X,Y,X2,sym,hkey,jkey,p,q,r }(C,D)のhkey2インデクス

QJH-odd 版（概略）type Ⅰ
Ａ

Ｂ

typeⅠの留意点：クイーンが中央に１つ配置された形①代表解の判定条件は even 版と同様

Ｑ

②結合処理では、U 特性値、V 特性値が 1 ビットずれている考慮が必要③サブボードのクイーンの数は、even 版と同様

ＤＣ

この場合、even 版とほとんど同じ処理となる

type Ⅱ
typeⅡの留意点：２つのクイーンが配置されている形

ＡQ

Ｂ

0≦I < J < n とする。また、typeⅡでは回転対象解は存在しない（type-a ）②結合処理では、U 特性値、V 特性値が 1 ビットずれている考慮が必要

QＤ①代表解の判定条件は、２つのクイーン（n, I）、（J, n）の位置関係は、③サブボードのクイーンの数は、以下のようになるＣ#(A) = m - 1#(B) = #(D) = n – m#(C) = m

ただし、1≦m≦n とする

部分解 nq(n,n)からの抽出条件
IU 特性値QJV 特性値

Q

typeⅠの場合

typeⅡの場合

A

B

C

D

U特性値 U(n)=0U(n)=0U(n)=0U(n)=0

X特性値 X(I)=0
Y特性値 ＆Y(J)=0X(J)=0

U特性値
V特性値＆U(I-1)=0Y(I)=0＆U(I-1)=0U(2n-I-1)=0＆U(2n-I-1)=0＆U(2n-J-1)=0 ＆U(J-1)=0＆U(J-1)=0＆U(2n-J-1)=0＆V(I)=0＆V(J)=0＆V(J)=0＆V(I)=０

実測結果
測定環境（ 使用 PC：FMV-BIBLO NF/B50 ）C P U： Intel Core2 DUO processor T8100 2.1GHz
キャッシュ： 3MB
メ モ リ： 4GB
O
S： Windows VistaＮ
1819202122takaken版
電通大版(qn24b)
実測値
相対比
実測値 相対比
3:48.23 1.0
7:00.717 1.84
29:22.0 1.0
57:16.602 1.95
3:54:10.34 1.0
7:19:24.765 1.88
33:14:19.48 1.0

QJH版
実測値
相対比
25.37 0.111
03:17.6 0.112
24:07.4 0.103
3:05:28.2 0.093
27:08:40.5

 takaken 版は、電通大版(qn24b)の約 2 倍
 QJH は、takaken 版の約 10 倍
 QJH の相対比は、徐々に向上

QJH の開発経過(N=18 の探索時間）
 シンプルな HJ 版で基本構造の確立
 徐々に性能改善を織り込む
600.0

500.0

①：初版（HJ 版）
578.0②：PGen の１パス化

QJH 版

HJ 版

③：Hash Key のチューニング

458.8④：loop 処理の改善

400.0

300.0

200.0

⑤：U,U2 のソフト cache 化⑥：Hash288.7

takaken 版(228.23sec)
214.1

0.0

⑦：フレームのビット反転
フレーム A≦B の絞り込み

186.1
147.0

100.0

Key の変更

119.9⑧：U,U2 の判定順序入れ替え
97.8

83.4

57.0

⑨：U,U2 を hkey,
41.3

25.4

jkey 分割⑩：QJH 版(1/4Parts 生成)⑪：Qcache 追加⑫：最新版(SymCheck-pid 化)

QJH-odd 版の処理時間詳細

PGen
typeⅠ
typeⅡ
Total

170.187
0.250
6.645
7.082

19211.513
14.0878.830
486.860
186.498 10,599.576
196.841 11,100.523

構成比（N=21）
0%4%
Pgen
typeⅠ
typeⅡ
96%

 typeⅡの処理時間が殆ど(typeI は、全体の約 1/20)

伸び率
Pgen
typeⅠ

 伸び率(21/19)では、typeⅠ,typeⅡとも大差なし
しかし、typeⅡの伸び率が急増。

21/19

typeⅡ

19/17

Total
0.0

20.0

40.0

60.0

まとめ成果

既存 Solver の約 10 倍の性能向上



inner join（＝結合）の問題であれば、さらに強力な効果が期待できる

反面、プログラムが複雑になることが難点→しかし、効果は大。適用例を増やして検証

課題
QJH の並列化（メモリを多用する構造であるため、並列化した場合の効果が未知数)

ソース 公開 (準備中)
http://deepgreen.game.coocan.jp参考文献
1) Eight queens puzzle , http://en.wikipedia.org/wiki/Eight_Queens_puzzle
2)

Number of ways of placing n nonattacking queens on n X n board.,
http://www.research.att.com/~njas/sequences/A000170

3) N-QUEENS の世界記録樹立，6 年分の計算を並列処理により 22 日に短縮
http://www.arch.cs.titech.ac.jp/~kise/nq/press-2004-10-05.txt
4)

ProActive Parallel Siute, http://proactive.inria.fr/index.php?page=nqueen25 (2010.04.24)

5)

Queens@TUD, http://Queens.inf.tu-dresden.de/

6)

Queens@TUD, RESULTS, http://Queens.inf.tu-dresden.de/?l=en&n=r

7) The N Queens Problem, http://www.jsomers.com/nqueen_demo/nqueens.html
8) N-queens Homepage in Japanese , http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm
9) ＮQueen 問題（解の個数を求める）, http://www.ic-net.or.jp/home/takaken/nt/queen/index.html

ご清聴ありがとうございました。