8皇后拼圖 - 使用python遞歸

Question

我試圖解決8-queens puzzle，也被稱爲n皇后算法。

我的函數應該計算在NxN板上放置N個皇后有多少種合法的方法。

我差點拿到了，但不得不做一些醜陋的補丁來使它工作。 你能幫我解決嗎？

對我做了什麼簡介： 試圖找出法律途徑究竟有多少集合N皇后在N×N的表， 我試圖用一個（N-1）XN情況下遞歸來解決（去除第一列） 至於沒有兩個女王被允許在同一列，我使用的列表長度爲N. 每個單元格代表一列，並在每列中設置皇后設置的行號。

例如，

[0, 4, 7, 5, 2, 6, 1, 3] 

就是說：

• 列0 - 王后置於行0
• 列1 - 王后放置在第4行
• 柱2 - 王后放置在第7行
• 第3列 - 皇后放在第5行
• 柱4 - 王后放置在第2行
• 柱5 - 王后放置在第6行
• 柱6 - 王后放置在第1行
• 柱7 - 王后放在行3

事情困擾我的是我不知道如何忽略非法女王的擺放。 所以爲了使它工作，我使用了一個名爲sum的全局變量，只有在遞歸達到完全放置的皇后合法位置時纔會增加它。

def is_available(n, table, column, N): 
    return not any(t in (n, n - i, n + i) 
        for t, i in zip(table, range(column, 0, -1))) 

def queens_sum(N): 
    table = [0]*N 
    global sum 
    sum = 0 
    solve(N, table, 0, len(table)) 
    return sum 

def solve(N, table, column, end): 

    global sum 

    if column == end: 
     sum += 1 
     return None 

    for n in range(N): 
     # if no other queen can attack here, place a queen in this row 
     if is_available(n, table, column, N): 
      table[column] = n 
      # Omit the current column at the start 
      solve(N, table, column+1, end) 
     #else: we can't place queen here, we should abort this direction 
      # do nothing 

對於N = 8我得到sum = 92 ..所以我知道它的工作原理，但我想避免這種全局計數器。

你能幫忙嗎？

Answer 1

您可以使用解決的返回值來跟蹤總和：

def queens_sum(N): 
    return solve(N, [0]*N, 0, N) 

def solve(N, table, column, end): 
    if column == end: 
     return 1 

    sum = 0 
    for n in range(N): 
     # if no other queen can attack here, place a queen in this row 
     if is_available(n, table, column, N): 
      table[column] = n 
      # Omit the current column at the start 
      sum += solve(N, table, column+1, end) 
     #else: we can't place queen here, we should abort this direction 
      # do nothing 

    return sum