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

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

上一个顶级方法:

递归方法现在是私有(private)的，并在完成时引发自定义异常:

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.