-
Notifications
You must be signed in to change notification settings - Fork 1
/
py04_nqueen.py
353 lines (350 loc) · 15.3 KB
/
py04_nqueen.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
#!/usr/bin/env python
# -*- coding: utf-8 -*-
""" py04_nqueen.py """
from datetime import datetime
# /**
# Pythonで学ぶアルゴリズムとデータ構造
# ステップバイステップでＮ−クイーン問題を最適化
# 一般社団法人 共同通信社 情報技術局 鈴木 維一郎(suzuki.iichiro@kyodonews.jp)
#
# 実行
# $ python py04_nqueen.py
#
# ４．バックトラック＋対称解除法
#
# 一つの解には、盤面を９０度、１８０度、２７０度回転、及びそれらの鏡像の合計
# ８個の対称解が存在する。対照的な解を除去し、ユニーク解から解を求める手法。
#
# ■ユニーク解の判定方法
# 全探索によって得られたある１つの解が、回転・反転などによる本質的に変わること
# のない変換によって他の解と同型となるものが存在する場合、それを別の解とはしない
# とする解の数え方で得られる解を「ユニーク解」といいます。つまり、ユニーク解とは、
# 全解の中から回転・反転などによる変換によって同型になるもの同士をグループ化する
# ことを意味しています。
#
# 従って、ユニーク解はその「個数のみ」に着目され、この解はユニーク解であり、こ
# の解はユニーク解ではないという定まった判定方法はありません。ユニーク解であるか
# どうかの判断はユニーク解の個数を数える目的の為だけに各個人が自由に定義すること
# になります。もちろん、どのような定義をしたとしてもユニーク解の個数それ自体は変
# わりません。
#
# さて、Ｎクイーン問題は正方形のボードで形成されるので回転・反転による変換パター
# ンはぜんぶで８通りあります。だからといって「全解数＝ユニーク解数×８」と単純には
# いきません。ひとつのグループの要素数が必ず８個あるとは限らないのです。Ｎ＝５の
# 下の例では要素数が２個のものと８個のものがあります。
#
#
# Ｎ＝５の全解は１０、ユニーク解は２なのです。
#
# グループ１: ユニーク解１つ目
# - - - Q - - Q - - -
# Q - - - - - - - - Q
# - - Q - - - - Q - -
# - - - - Q Q - - - -
# - Q - - - - - - Q -
#
# グループ２: ユニーク解２つ目
# - - - - Q Q - - - - - - Q - - - - Q - - - - - Q - - Q - - - Q - - - - - - - - Q
# - - Q - - - - Q - - Q - - - - - - - - Q - Q - - - - - - Q - - - - Q - - Q - - -
# Q - - - - - - - - Q - - - Q - - Q - - - - - - - Q Q - - - - - Q - - - - - - Q -
# - - - Q - - Q - - - - Q - - - - - - Q - - - Q - - - - Q - - - - - - Q Q - - - -
# - Q - - - - - - Q - - - - - Q Q - - - - Q - - - - - - - - Q - - Q - - - - Q - -
#
#
# それでは、ユニーク解を判定するための定義付けを行いますが、次のように定義する
# ことにします。各行のクイーンが右から何番目にあるかを調べて、最上段の行から下
# の行へ順番に列挙します。そしてそれをＮ桁の数値として見た場合に最小値になるもの
# をユニーク解として数えることにします。尚、このＮ桁の数を以後は「ユニーク判定値」
# と呼ぶことにします。
#
# - - - - Q 0
# - - Q - - 2
# Q - - - - 4 ---> 0 2 4 1 3 (ユニーク判定値)
# - - - Q - 1
# - Q - - - 3
#
#
# 探索によって得られたある１つの解(オリジナル)がユニーク解であるかどうかを判定
# するには「８通りの変換を試み、その中でオリジナルのユニーク判定値が最小であるか
# を調べる」ことになります。しかし結論から先にいえば、ユニーク解とは成り得ないこ
# とが明確なパターンを探索中に切り捨てるある枝刈りを組み込むことにより、３通りの
# 変換を試みるだけでユニーク解の判定が可能になります。
#
#
# ■ユニーク解の個数を求める
# 先ず最上段の行のクイーンの位置に着目します。その位置が左半分の領域にあればユ
# ニーク解には成り得ません。何故なら左右反転によって得られるパターンのユニーク判
# 定値の方が確実に小さくなるからです。また、Ｎが奇数の場合に中央にあった場合はど
# うでしょう。これもユニーク解には成り得ません。何故なら仮に中央にあった場合、そ
# れがユニーク解であるためには少なくとも他の外側の３辺におけるクイーンの位置も中
# 央になければならず、それは互いの効き筋にあたるので有り得ません。
#
# ***********************************************************************
# 最上段の行のクイーンの位置は中央を除く右側の領域に限定されます。(ただし、N ≧ 2)
# ***********************************************************************
#
# 次にその中でも一番右端(右上の角)にクイーンがある場合を考えてみます。他の３つ
# の角にクイーンを置くことはできないので(効き筋だから）、ユニーク解であるかどうか
# を判定するには、右上角から左下角を通る斜軸で反転させたパターンとの比較だけになり
# ます。突き詰めれば、
#
# [上から２行目のクイーンの位置が右から何番目にあるか]
# [右から２列目のクイーンの位置が上から何番目にあるか]
#
#
# を比較するだけで判定することができます。この２つの値が同じになることはないからです。
#
# 3 0
# ↓↓
# - - - - Q ←0
# - Q - - - ←3
# - - - - - 上から２行目のクイーンの位置が右から４番目にある。
# - - - Q - 右から２列目のクイーンの位置が上から４番目にある。
# - - - - - しかし、互いの効き筋にあたるのでこれは有り得ない。
#
# 結局、再帰探索中において下図の X への配置を禁止する枝刈りを入れておけば、得
# られる解は総てユニーク解であることが保証されます。
#
# - - - - X Q
# - Q - - X -
# - - - - X -
# - - - - X -
# - - - - - -
# - - - - - -
#
# 次に右端以外にクイーンがある場合を考えてみます。オリジナルがユニーク解である
# ためには先ず下図の X への配置は禁止されます。よって、その枝刈りを先ず入れておき
# ます。
#
# X X - - - Q X X
# X - - - - - - X
# - - - - - - - -
# - - - - - - - -
# - - - - - - - -
# - - - - - - - -
# X - - - - - - X
# X X - - - - X X
#
# 次にクイーンの利き筋を辿っていくと、結局、オリジナルがユニーク解ではない可能
# 性があるのは、下図の A, B, C の位置のどこかにクイーンがある場合に限られます。従っ
# て、90度回転、180度回転、270度回転の３通りの変換パターンだけを調べれはよいこと
# になります。
#
# X X x x x Q X X
# X - - - x x x X
# C - - x - x - x
# - - x - - x - -
# - x - - - x - -
# x - - - - x - A
# X - - - - x - X
# X X B - - x X X
#
#
# ■ユニーク解から全解への展開
# これまでの考察はユニーク解の個数を求めるためのものでした。全解数を求めるには
# ユニーク解を求めるための枝刈りを取り除いて全探索する必要があります。したがって
# 探索時間を犠牲にしてしまうことになります。そこで「ユニーク解の個数から全解数を
# 導いてしまおう」という試みが考えられます。これは、左右反転によるパターンの探索
# を省略して最後に結果を２倍するというアイデアの拡張版といえるものです。そしてそ
# れを実現させるには「あるユニーク解が属するグループの要素数はいくつあるのか」と
# いう考察が必要になってきます。
#
# 最初に、クイーンが右上角にあるユニーク解を考えます。斜軸で反転したパターンが
# オリジナルと同型になることは有り得ないことと(×２)、右上角のクイーンを他の３つの
# 角に写像させることができるので(×４)、このユニーク解が属するグループの要素数は必
# ず８個(＝２×４)になります。
#
# 次に、クイーンが右上角以外にある場合は少し複雑になりますが、考察を簡潔にする
# ために次の事柄を確認します。
#
# TOTAL = (COUNT8 * 8) + (COUNT4 * 4) + (COUNT2 * 2)
# (1) 90度回転させてオリジナルと同型になる場合、さらに90度回転(オリジナ
# ルから180度回転)させても、さらに90度回転(オリジナルから270度回転)させ
# てもオリジナルと同型になる。
#
# COUNT2 * 2
#
# (2) 90度回転させてオリジナルと異なる場合は、270度回転させても必ずオリジナ
# ルとは異なる。ただし、180度回転させた場合はオリジナルと同型になること
# も有り得る。
#
# COUNT4 * 4
#
# (3) (1) に該当するユニーク解が属するグループの要素数は、左右反転させたパターンを
# 加えて２個しかありません。(2)に該当するユニーク解が属するグループの要素数は、
# 180度回転させて同型になる場合は４個(左右反転×縦横回転)、そして180度回転させても
# オリジナルと異なる場合は８個になります。(左右反転×縦横回転×上下反転)
#
# COUNT8 *
#
# 以上のことから、ひとつひとつのユニーク解が上のどの種類に該当するのかを調べる
# ことにより全解数を計算で導き出すことができます。探索時間を短縮させてくれる枝刈
# りを外す必要がなくなったというわけです。
#
# UNIQUE COUNT2 + COUNT4 + COUNT8
# TOTAL (COUNT2 * 2) + (COUNT4 * 4) + (COUNT8 * 8)
#
# これらを実現すると、前回のnqueen3()よりも実行速度が遅くなります。
# なぜなら、対称・反転・斜軸を反転するための処理が加わっているからです。
# ですが、今回の処理を行うことによって、さらにnqueen5()では、処理スピードが飛
# 躍的に高速化されます。そのためにも今回のアルゴリズム実装は必要なのです。
#
#
# 実行結果
# N: Total Unique hh:mm:ss.ms
# 4: 2 1 0:00:00.000
# 5: 10 2 0:00:00.000
# 6: 4 1 0:00:00.000
# 7: 40 6 0:00:00.001
# 8: 92 12 0:00:00.005
# 9: 352 46 0:00:00.020
# 10: 724 92 0:00:00.089
# 11: 2680 341 0:00:00.429
# 12: 14200 1787 0:00:02.235
# 13: 73712 9233 0:00:12.962
# 14: 365596 45752 0:01:17.622
# 15: 2279184 285053 0:08:21.847
#
# */
#
# グローバル変数
MAX = 16 # N = 15
TOTAL = 0
UNIQUE = 0
ABOARD = [0 for i in range(MAX)]
FA = [0 for i in range(2*MAX-1)] #縦列にクイーンを一つだけ配置
FB = [0 for i in range(2*MAX-1)] #斜め列にクイーンを一つだけ配置
FC = [0 for i in range(2*MAX-1)] #斜め列にクイーンを一つだけ配置
AT = [0 for i in range(MAX)] #AT:ATrial[]
AS = [0 for i in range(MAX)] #AS:AScrath[]
#
# 回転
def rotate(chk, scr, _n, neg):
""" rotate() """
incr = 0
k = 0 if neg else _n-1
incr = 1 if neg else -1
for i in range(_n):
scr[i] = chk[k]
k += incr
k = _n-1 if neg else 0
for i in range(_n):
chk[scr[i]] = k
k -= incr
#
# 反転
def vmirror(chk, neg):
""" vMirror() """
for i in range(neg):
chk[i] = (neg-1)-chk[i]
#
#
def intncmp(_lt, _rt, neg):
""" intncmp() """
rtn = 0
for i in range(neg):
rtn = _lt[i]-_rt[i]
if rtn != 0:
break
return rtn
#
# 対称解除法
def symmetryops(size): # pylint: disable=R0911,R0912
""" symmetryOps() """
global AT # pylint: disable=W0603
global AS # pylint: disable=W0603
nquiev = 0
# 回転・反転・対称チェックのためにboard配列をコピー
for i in range(size):
AT[i] = ABOARD[i]
# 時計回りに90度回転
rotate(AT, AS, size, 0)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0 # pylint: disable=R0915
if k == 0:
nquiev = 1
else:
# 時計回りに180度回転
rotate(AT, AS, size, 0)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0 # pylint: disable=R0915
if k == 0:
nquiev = 2
else:
# 時計回りに270度回転
rotate(AT, AS, size, 0)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0
nquiev = 4
# 回転・反転・対称チェックのためにboard配列をコピー
for i in range(size):
AT[i] = ABOARD[i]
# 垂直反転
vmirror(AT, size)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0
# -90度回転 対角鏡と同等
if nquiev > 1:
rotate(AT, AS, size, 1)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0
# -180度回転 水平鏡像と同等
if nquiev > 2:
rotate(AT, AS, size, 1)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0
# -270度回転 反対角鏡と同等
rotate(AT, AS, size, 1)
k = intncmp(ABOARD, AT, size)
if k > 0:
return 0
return nquiev*2
#
def nqueen(row, size):
"""nqueen()"""
global ABOARD # pylint: disable=W0603
global TOTAL # pylint: disable=W0603
global UNIQUE # pylint: disable=W0603
global FA # pylint: disable=W0603
global FB # pylint: disable=W0603
global FC # pylint: disable=W0603
if row == size:
stotal = symmetryops(size) # 対称解除法の導入
if stotal != 0:
UNIQUE += 1 # ユニーク解を加算
TOTAL += stotal # 対称解除で得られた解数を加算
else:
for i in range(size):
ABOARD[row] = i
if FA[i] == 0 and FB[row-i+(size-1)] == 0 and FC[row+i] == 0:
FA[i] = FB[row-i+(size-1)] = FC[row+i] = 1
nqueen(row+1, size) #再帰
FA[i] = FB[row-i+(size-1)] = FC[row+i] = 0
#
def main():
"""main()"""
global TOTAL # pylint: disable=W0603
global UNIQUE # pylint: disable=W0603
global ABOARD # pylint: disable=W0603
nmin = 4 # Nの最小値（スタートの値）を格納
print(" N: Total Unique hh:mm:ss.ms")
for i in range(nmin, MAX):
TOTAL = 0
UNIQUE = 0 # 初期化
for j in range(i):
ABOARD[j] = j # 盤を初期化
start_time = datetime.now()
nqueen(0, i)
time_elapsed = datetime.now()-start_time
_text = '{}'.format(time_elapsed)
text = _text[:-3]
print("%2d:%13d%13d%20s" % (i, TOTAL, UNIQUE, text)) # 出力
#
main()
#