来自欧洲的神秘力量总是能救助非酋的。
《人工智能–一种现代的方法》书里提过，之前九几年有一篇论文，实现了一分钟内解三百万皇后问题，于是就正好找出来。我的电脑上能在8秒内解出一百王皇后。
论文题目： Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem （1994）
我根据论文实现的代码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
104import random
import time
class Queen():
queen_array = [0,]
Uconfilct_array = [0,]
Dconfilct_array = [0,]
def __init__(self,num):
self.num = num
self.Uconfilct_array = [0]*(2*num+1)
self.Dconfilct_array = [0]*(2*num+1)
for i in range(1,num+1):
self.queen_array.append(i)
self.confilct = 0
# print(self.Uconfilct_array)
# print(x)
def N_update(self,col1,col2):
row1 = self.queen_array[col1]
row2 = self.queen_array[col2]
tDown = self.num+col1-self.queen_array[col1]
self.Dconfilct_array[tDown] = 0
# print(col1+row1)
self.Uconfilct_array[col1+row1] = 0
tDown = self.num+col2-self.queen_array[col2]
self.Dconfilct_array[tDown] = 0
# print(col1+row1)
self.Uconfilct_array[col2+row2] = 0
tmp = row1
self.queen_array[col1] = row2
self.queen_array[col2] = tmp
tDown = self.num+col1-self.queen_array[col1]
self.Dconfilct_array[tDown] += 1
self.Uconfilct_array[col1+self.queen_array[col1]] += 1
tDown = self.num+col2-self.queen_array[col2]
self.Dconfilct_array[tDown] += 1
self.Uconfilct_array[col2+self.queen_array[col2]] += 1
def N_Lconfilct(self,col1,col2):
row = self.queen_array[col2]
tDown = self.num+col1-row
num = self.Uconfilct_array[row+col1] + self.Dconfilct_array[tDown]
return num
def init_search(self):
j = 1
for i in range(1,int(3.08*(self.num))):
m = random.randint(j,self.num)
if(self.N_Lconfilct(j,m)==0):
# print("changed")
self.N_update(j,m)
j += 1
if(j==self.num):
return 0
# print(j)
for i in range(j,self.num+1):
m = random.randint(i,self.num)
self.N_update(i,m)
return self.num-j+1
def total_confilct(self,col):
sum = 0
row = self.queen_array[col]
tDown = self.num+col-row
sum = self.Uconfilct_array[col+row]+self.Dconfilct_array[tDown]
# print(sum)
return sum-2
def final_search(self,k):
tmp = 0
# print("final")
for i in range(self.num-k+1,self.num+1):
if(self.total_confilct(i)>0):
while(True):
j = random.randint(1,self.num)
self.N_update(i,j)
if((self.total_confilct(i)>0)|(self.total_confilct(j))):
self.N_update(i,j)
else:
break
st=time.time()
queen = Queen(1000000)
t = queen.init_search()
print(t)
ft=time.time()
print(ft-st)
queen.final_search(t)
et=time.time()
print(et-st)
我是拿python写的，理论上用c艹写可能会更快，但谁叫python写起来快呢 : P
论文的核心就在于，在开始对状态进行初始化的时候，就尽可能最小化冲突，例如在开始时，就将不同的皇后依次放在不同行，不同列，并尽量满足，前m个皇后是不冲突的。
然后统计对角线上的冲突是使用两个2n-1个数字，来储存每个皇后对应的两条攻击方向斜线的斜率，来减少计算冲突时的查表时间。