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

Question

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

但是我面临的主要问题是我需要在第一个解决方案执行后终止。如果有人能帮我解决这个问题那就太好了。

Answer 1

从任意深度展开堆栈的一种方法是使用异常：

自定义异常：

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

NOTE: I had no way to test this.

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

How to terminate backtracing recursion after first solution is found

algorithm

recursion

n-queens

python-3.x