在N皇后迭代解決方案中避免重複（不允許遞歸）

Question

我正在用迭代解決N皇后問題（無遞歸）。我現在面臨的問題是重複的解決方案。例如4×4板有2種解決方案我打印4種解決方案，所以說我找到兩次相同的解決方案。

讓我進入代碼爲更好地概覽：

def solution(self): 
     queen_on_board = 0 
     for row in range(self.N): 
      for col in range(self.N): 
       self.board[row][col] = 'Q' 
       queen_on_board = queen_on_board + 1 
       print ("(row,col) : ", row, col) 
       squares_list = self.get_posible_safe_squares(row,col) 
       for square in squares_list: 
        for x,y in square.items(): 
         if self.isTheQueenSafe(x,y): 
          self.board[x][y] = 'Q' 
          queen_on_board = queen_on_board + 1 
       print ("Queen on board", queen_on_board) 
       if queen_on_board == 4: 
        self.print_the_board() 
       self.reset_the_board() 
       queen_on_board = 0 

所以你可以看到我會在每一個行列數。這個特定的實現給了我4個解決方案2是相同的。

(row,col) : 0 1 
Queen on board 4 
['.', 'Q', '.', '.'] 

['.', '.', '.', 'Q'] 

['Q', '.', '.', '.'] 

['.', '.', 'Q', '.'] 

(row,col) : 0 2 
Queen on board 4 
['.', '.', 'Q', '.'] 

['Q', '.', '.', '.'] 

['.', '.', '.', 'Q'] 

['.', 'Q', '.', '.'] 

(row,col) : 1 0 
Queen on board 4 
['.', '.', 'Q', '.'] 

['Q', '.', '.', '.'] 

['.', '.', '.', 'Q'] 

['.', 'Q', '.', '.'] 

(row,col) : 2 0 
Queen on board 4 
['.', 'Q', '.', '.'] 

['.', '.', '.', 'Q'] 

['Q', '.', '.', '.'] 

['.', '.', 'Q', '.'] 

我想避免重複。如果有人能指引我走向正確的方向，那將會很棒。

get_posible_safe_squares（）方法在女王可能安全的電路板中查找可能的方塊。

def get_posible_safe_squares(self, row, col): 
     ret = [] 
     for i in range(self.N): 
      for j in range(self.N): 
       if i != row and j !=col: 
        if i + j != row + col and i - j != row - col: 
         d = { i:j } 
         ret.append(d) 
     return ret 

Answer 1

你得到重複的原因是你也把皇后放在你放置第一個皇后的位置之前。所以你的第一個女王將在每個方格上得到它的位置，但是其他女王可以在一個正方形的位置上進行，在這個方形的第一個女王已經放置了。這意味着兩名女王被「交換」，但實質上是朝着相同的解決方案構建的。

我試圖重寫你的解決方案，但後來決定也改變了以下幾個方面：

• 可惜的是，對於將第一個女王的代碼是不一樣的用於放置其他王后。應該可以重複使用相同的代碼。
• 我不會使用單個字典來表示一個正方形。元組(i, j)似乎比{ i:j }更自然。
• 當你需要的唯一信息是棋盤大小和皇后被放置時皇后的位置時，存儲整個棋盤可能是過量的。由於在同一行上不能有兩個皇后，所以你可以將它作爲列索引列表。因此queens[2] == 3表示在第2行和第3列有一個皇后。一旦擁有此列表，您不需要queens_on_board，因爲len(queens)將返回該值。根據該信息，print_the_board可以輕鬆生成點和「Q」。
• 由於您具有功能isTheQueenSafe，您並不需要get_posible_safe_squares。放置第一個女王之後，你稱它爲已經非常武斷，但在放置任何其他女王后不會。
• 你混合了兩個命名約定：camelCase和下劃線，所以我會選擇後者並使用is_queen_safe。

看到它在repl.it

運行下面是代碼：

class Board: 
    def __init__(self, size): 
     self.N = size 
     self.queens = [] # list of columns, where the index represents the row 

    def is_queen_safe(self, row, col): 
     for r, c in enumerate(self.queens): 
      if r == row or c == col or abs(row - r) == abs(col - c): 
       return False 
     return True 

    def print_the_board(self): 
     print ("solution:") 
     for row in range(self.N): 
      line = ['.'] * self.N 
      if row < len(self.queens): 
       line[self.queens[row]] = 'Q' 
      print(''.join(line)) 

    def solution(self): 
     self.queens = [] 
     col = row = 0 
     while True: 
      while col < self.N and not self.is_queen_safe(row, col): 
       col += 1 
      if col < self.N: 
       self.queens.append(col) 
       if row + 1 >= self.N: 
        self.print_the_board() 
        self.queens.pop() 
        col = self.N 
       else: 
        row += 1 
        col = 0 
      if col >= self.N: 
       # not possible to place a queen in this row anymore 
       if row == 0: 
        return # all combinations were tried 
       col = self.queens.pop() + 1 
       row -= 1 

q = Board(5) 
q.solution() 

Answer 2

你的算法錯過幾起案件和糾正重複的方式是相當複雜的。相反，我建議你效仿遞歸。

開始與一個簡單的遞歸函數：

def is_safe(board, x, y, c): 
    for p in [board[i] for i in range(0, c)]: 
     if p[0] == x or p[1] == y or x + y == p[0] + p[1] or x - y == p[0] - p[1]: 
      return False 

    return True 


def nqueen_rec(board, n, c): 
    if c == n: 
     print(board) 
    else: 
     for x in range(0, n): 
      if is_safe(board, x, c, c): 
       board[c] = (x, c) 
       nqueen_rec(board, n, c + 1) 

同時，積極加強深入遞歸是c改變的唯一參數，所以我們可以很容易改變的行爲是遞歸的：

def nqueen_nrec(n): 
    c = 0 
    step = [0 for x in range(0, n + 1)] 
    board = [(x, x) for x in range(0, n)] 

    while c != -1: 
     if c == n: 
      print(board) 
      c -= 1 
      step[c] += 1 
     elif step[c] == n: 
      c -= 1 
      step[c] += 1 
     elif is_safe(board, step[c], c, c): 
      board[c] = (step[c], c) 
      c += 1 
      step[c] = 0 
     else: 
      step[c] += 1 

該算法跟蹤當前的部分解決方案和下一個可能的解決方案，並通過啓動新循環而不是遞歸函數調用來模擬遞歸深度。