python 八皇后问题

import random
def confict(state,nextX):
    nextY=len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0,nextY-i):
            return True
def queens(num=8,state=()):
    for pos in range(num):
        if not confict(state,pos):
            if len(state)==num-1:
                yield(pos,)--------------------------------------------------前面三个为（1，3，0），最后一个符合条件的为2，  yield(pos,）执行这一步就终止了，单独返回（2，）怎么会把2合入到元组中，变成（1，3，0，2）？
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,) + result

如果沒有錯，你這題應該是由西洋棋棋手馬克斯·貝瑟爾（Max Bezzel）於1848年提出的八皇后問題吧?

八皇后問題：
如何能夠在8×8的西洋棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處於同一條橫行、縱行或斜線上。

以下為我的代碼，不夠完善，基本只能隨機生成答案，但不能計算一共多少種答案（維基百科：已知曉92個有效答案，扣除獨立答案為12）

1. # Author: 傻眼貓咪
   
2. # 2021.08.08
   
3. 
   
4. import random
   
5. 
   
6. def randomValidBoard(N): # 函數：隨機生成有效棋盤
   
7.     board = None
   
8. 
   
9.     def randomSeed(N) -> 'random seed': # 隨機生成 N 個位置
   
10.         position = [i for i in range(N)]
    
11.         board = []
    
12.         for i in range(N):
    
13.             while True:
    
14.                 temp = random.choice(position)
    
15.                 if temp in board:
    
16.                     continue
    
17.                 else:
    
18.                     board.append(temp)
    
19.                     break
    
20.         return board
    
21. 
    
22.     def diagonallyCheck(brd: 'board', val: 'value') -> bool: # 函數：檢查位置是否有效，符合條件？
    
23.         r1 = r2 = l1 = l2 = val # 值
    
24.         R = L = brd.index(val) # 指針
    
25.         while True:
    
26.             if R+1 <= 7:
    
27.                 R += 1 # 值
    
28.                 r1 += 1 # 指針
    
29.                 r2 -= 1
    
30.                 if brd[R] == r1 or brd[R] == r2:
    
31.                     return False
    
32.                 else:
    
33.                     continue
    
34.             if L-1 >= 0:
    
35.                 L -= 1
    
36.                 l1 += 1
    
37.                 l2 -= 1
    
38.                 if brd[L] == l1 or brd[L] == l2:
    
39.                     return False
    
40.                 else:
    
41.                     continue
    
42.             if R+1 > 7 and L-1 < 0:
    
43.                 break
    
44.         return True
    
45. 
    
46.     def allValid(brd: 'board') -> bool: # 函數：確定棋盤全部有效
    
47.         for i in brd:
    
48.             if diagonallyCheck(brd, i) == False:
    
49.                 return False
    
50.         return True
    
51.    
    
52.     while True: # 重複生成無數個棋盤，直至某個有效棋盤為止
    
53.         board = randomSeed(N)
    
54.         if allValid(board) == True:
    
55.             break
    
56. 
    
57.     return board # 最終回傳有效棋盤
    
58. 
    
59. def showingBoard(brd: 'borad', N) -> print(): # 列印函數：列印出有效棋盤的擺放位置
    
60.     flag = []
    
61.     for i in range(N):
    
62.         temp = []
    
63.         queen = False
    
64.         for j in range(N):
    
65.             for k in range(N):
    
66.                 if i == k and brd[k] == j:
    
67.                     queen = True
    
68.             if queen == True:
    
69.                 temp.append('♕')
    
70.                 queen = False
    
71.             else:
    
72.                 temp.append('▢')
    
73.         flag.append(temp)
    
74.     for i in flag:
    
75.         for count, j in enumerate(i):
    
76.             if count < 7:
    
77.                 print(j, end = ' ')
    
78.             else:
    
79.                 print(j)
    
80. 
    
81. def main(): # 主函數
    
82.     N = 8
    
83.     showingBoard(randomValidBoard(N), N)
    
84. 
    
85. if __name__ == '__main__':
    
86.     main()

复制代码

隨機得出有效結果（目前已知92種答案正確）：

1. ▢ ▢ ♕ ▢ ▢ ▢ ▢ ▢
   
2. ▢ ▢ ▢ ▢ ▢ ♕ ▢ ▢
   
3. ▢ ▢ ▢ ▢ ▢ ▢ ▢ ♕
   
4. ▢ ♕ ▢ ▢ ▢ ▢ ▢ ▢
   
5. ▢ ▢ ▢ ♕ ▢ ▢ ▢ ▢
   
6. ♕ ▢ ▢ ▢ ▢ ▢ ▢ ▢
   
7. ▢ ▢ ▢ ▢ ▢ ▢ ♕ ▢
   
8. ▢ ▢ ▢ ▢ ♕ ▢ ▢ ▢

复制代码