如何在找到第一个解决方案后终止回溯递归

我正在尝试查找回溯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

如何在找到第一个解决方案后终止回溯递归

回答

相关问题