三种不同算法求解八皇后问题：排列组合、回溯法+递归、生成器+递归

知道同学

排列组合确实慢

Jensona

牛逼嗷

你在说些什么

学习学习

为之奈何

想知道

java2python

学习

java2python

达人的代码太精简了，里面的yield就不懂，用了他的conflict函数，写了一个非递归的：

1. def conflict(cur_row, row_ptr):
   
2.         for i in range(cur_row):
   
3.                 if abs(row_ptr[i] - row_ptr[cur_row]) in (0, cur_row - i):
   
4.                         return True
   
5.         return False
   
6. 
   
7. def solve(QUEEN_SUM):
   
8.     row_ptr = [0]*QUEEN_SUM
   
9.     cur_row = 0
   
10.     while(True) :
    
11.         while(row_ptr[cur_row] == QUEEN_SUM or conflict(cur_row,row_ptr)):
    
12.             if(row_ptr[cur_row] == QUEEN_SUM):
    
13.                 cur_row -= 1
    
14.             if(cur_row < 0 ):
    
15.                 return
    
16.             row_ptr[cur_row] += 1
    
17.         if(cur_row ==QUEEN_SUM-1) :
    
18.             chest = [[0]*QUEEN_SUM for i in range(QUEEN_SUM)]
    
19.             for i in range(QUEEN_SUM):
    
20.                     chest[i][row_ptr[i]] = 1
    
21.                     print (chest[i])
    
22.             print ()
    
23.             row_ptr[cur_row] += 1
    
24.         else:
    
25.             cur_row += 1
    
26.             row_ptr[cur_row] = 0
    
27. 
    
28. solve(8)
    

复制代码

yield看了网上的知识，还是半懂不懂，有点超出理解范围，做了一个没有yield的版本，对比代码，总算大致知道意思，yield是同一层的结果扔到turple后再return：

1. def conflict(state, nextX):
   
2.     nextY = len(state)
   
3.     for i in range(nextY):
   
4.         if abs(state[i] - nextX) in (0, nextY - i):
   
5.             return True
   
6.     return False
   
7. 
   
8. def queens(num = 3, state = (),cfloor=0):
   
9.     res = None        #这里要res要初始化
   
10.     for pos in range(num):
    
11.         if not conflict(state, pos):
    
12.             #if len(state) == num - 1:
    
13.             #        yield (pos,)
    
14.             if len(state) == num - 1:
    
15.                 return ((pos,),)
    
16.             else:
    
17.                 #for result in queens(num, state + (pos,)):
    
18.                 #        yield (pos,) + result
    
19.                 result = queens(num, state + (pos,),cfloor+1)
    
20.                 if result == None:       #这里要None判别
    
21.                     continue
    
22.                 for ren in result:
    
23.                     if res == None:      #这里要None判别
    
24.                         res = (((pos,) + ren),)
    
25.                     else:
    
26.                         res =  (((pos,) + ren),) + res
    
27.     return res
    
28. c = 0
    
29. result = queens(6,(),0)
    
30. for res in result:
    
31.         c+=1
    
32.         print ('Solution %d: ' % c)
    
33.         chest = [[0]*len(res) for i in range(len(res))]
    
34.         for i in range(len(res)):
    
35.                 chest[i][res[i]] = 1
    
36.                 print (chest[i])
    
37.         print ()        

复制代码

java2python

八皇后全排列做法（一共是16777216组合，如果找到第一个布局就跳出，就10秒，全部的话3分多钟）：

1. pows = [pow(8,0),pow(8,1),pow(8,2),pow(8,3),pow(8,4),pow(8,5),pow(8,6),pow(8,7),pow(8,8)]
   
2. 
   
3. def check(rows):
   
4.     for row in range(1,8):
   
5.         for i in range(row):
   
6.             if abs(rows[i] - rows[row]) in (0, row - i):
   
7.                 return True
   
8.     return False
   
9. 
   
10. rows = [0]*8
    
11. for sts in range(0,pow(8,8)):
    
12.     for bit in range(0,8):
    
13.         rows[bit]=(sts%pows[bit+1])//pows[bit]
    
14.     if check(rows) == False:
    
15.         chest = [[0]*8 for i in range(8)]
    
16.         for i in range(8):
    
17.             chest[i][rows[i]] = 1
    
18.             print (chest[i])
    
19.         print ()
    
20.         #break

复制代码

当然全排列太慢了，不过可以稍作改进，就和快速搜索是一样速度了（当然每一位用pows取余数再除，会多一点时间，不过没有数量级的区别）,就是检测局面的时候，哪一行出问题（check函数返回true，false改为行号，如果是0，就是原来的false），那么就直接进入这一行的下一个选项（这一行已经出问题，后面的排列搜索全是无用功，实际逻辑和快速搜索一样，不过全排列的程序是最容易理解的）：

1. pows = [pow(8,8),pow(8,7),pow(8,6),pow(8,5),pow(8,4),pow(8,3),pow(8,2),pow(8,1),pow(8,0)]
   
2. 
   
3. def check(rows):
   
4.     for row in range(1,8):
   
5.         for i in range(row):
   
6.             if abs(rows[i] - rows[row]) in (0, row - i):
   
7.                 return row
   
8.     return 0
   
9. 
   
10. rows = [0]*8
    
11. sts = 0
    
12. while sts < pow(8,8):
    
13.     for bit in range(0,8):
    
14.         rows[bit]=(sts%pows[bit])//pows[bit+1]
    
15.     err_row = check(rows)
    
16.     if err_row == 0:
    
17.         chest = [[0]*8 for i in range(8)]
    
18.         for i in range(8):
    
19.             chest[i][rows[i]] = 1
    
20.             print (chest[i])
    
21.         print ()
    
22.         sts += 1
    
23.     else:
    
24.         sts += pows[err_row+1]

复制代码

口木呆

那份开始开始疯狂

zjc999

随宇

嗷嗷嗷

罗密欧与梁山伯

谢谢

2002122

要看

Minecraft程序猿

3255536441

666

sjh110

666

DefSw0rd

布耶特呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

山有扶苏|溪潺

1