如何在找到第一個解決方案後終止回溯遞歸

我正在嘗試查找回溯nQueen算法的第一個解決方案。我想在找到第一個解決方案後終止代碼的執行。但程序一直運行直到找到所有的解決方案。如何在找到第一個解決方案後終止回溯遞歸

這裏是我的代碼：

def nQueenBackTrack_first_solution(self, row, n): 
     i = 0 
     while i < n: 
     if self.isTheQueenSafe(row , i): 
      self.board[row][i] = "Q" 
      if row == n - 1: 
      self.print_the_board() 
      break 
      else: 
      self.nQueenBackTrack(row + 1, n) 
      self.board[row][i] = "." 
     i += 1

這樣可以使打印所有的解決方案。我只需要第一個解決方案。你也可以看看這個程序中使用的其他方法。

def isTheQueenSafe(self, row,col): 
     for i in range(self.N): 
        # check horizontal Queens 
        if self.does_board_has_a_queen_at(row,i) or self.does_board_has_a_queen_at(i, col): 
         return False 
        # check diagonal Queens 
        s = row + col 
        k = row - col 
        for x in range(self.N): 
         for y in range(self.N): 
          if x + y == s and self.board[x][y] == "Q": 
           return False 
          if x - y == k and self.board[x][y] == "Q": 
           return False   
     return True 

def does_board_has_a_queen_at(self,row,col): 
    return self.board[row][col] == 'Q' 


def print_the_board(self): 
    print("solution:") 
    for val in self.board: 
     print (val, "\n")

但是我面臨的主要問題是我需要在第一個解決方案執行後終止。如果有人能幫我解決這個問題，那就太好了。放鬆從任意深度堆棧

來源

2017-02-19 Shadid

使用全局變量並在找到第一個解決方案時將其設置爲True。或者通過你的所有函數傳遞這個布爾值。 – ShreevatsaR

的一種方式是使用一個例外：

自定義異常：

class DoneEarly(Exception): 
    """An exception to unwind the stack"""

頂級方法：

def nQueenBackTrack(self, row, n): 
    try: 
     self._nQueenBackTrack(row, n) 
    except DoneEarly: 
     pass

上一頁頂級方法：

遞歸方法現在是私人的，並在完成時引發的自定義異常：

def _nQueenBackTrack(self, row, n): 
    i = 0 
    while i < n: 
     if self.isTheQueenSafe(row, i): 
      self.board[row][i] = "Q" 
      if row == n - 1: 
       self.print_the_board() 
       raise DoneEarly 
      self._nQueenBackTrack(row + 1, n) 
      self.board[row][i] = "." 
     i += 1

注：我沒有辦法進行測試。

來源

2017-02-19 04:03:19

如何在找到第一個解決方案後終止回溯遞歸

回答

相關問題