最初の解が見つかった後にバックトレース再帰を終了する方法

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

任意の深さのスタックをアンワインドする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 

注：私はこれをテストする方法がありませんでした。