n_queenでの再帰の仕組みPython

Question

Pythonで古典的なn個のクイーン問題を解決しようとしています。残念ながら、私の期待とはかなり異なる結果でした。私はバックトラッキングアルゴリズムを理解していましたが、再帰を書く際にどこでミスをする可能性があるのか​​明確ではないかもしれません。私は1.print可能な解決策を試みた。 2.可能なすべてのソリューションを印刷します。

def n_queen_find1(n): 
    answer = [-1] * n 
    def dfs(depth,answer): 
     if depth == n: 
      print ("cur valid answer is ",answer) 
      return answer 
     else: 
      for colNum in range(n): # check every col at cur depth 
       if is_safe(depth,colNum,answer): 
        answer[depth] = colNum 
        print ("now the answer is ", answer) 
        print ("now depth move to ", depth + 1) 
        dfs(depth + 1,answer) 

    def is_safe(i,j,answer_cur): 
     # given current queen placement , could we place the ith queen (at row i) at the col j 
     for prerow in range(i): 
      if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j): 
       return False 
     return True 

    return dfs(0,answer) 

Iは4素子の出力にn_queen_find1リストを期待しています（ここで私の解決策は、リストの値は、[i]はi番目の行の選択された列であるNのリストとして示されました） [1、3、0、2]のようなn == 4のとき。私の再帰プロセスでは、修正された答えが生成されました（プリントに見られるように）。ただし、関数は何も返しませんでした。デバッグに役立つプリントラインを追加しました。なぜ、dfsが最初の正解が作成されたときに停止して復帰しないのか分かりませんでしたか？

trial1 = n_queen_find1(4) 
print trial1 
('now the answer is ', [0, -1, -1, -1]) 
('now depth move to ', 1) 
('now the answer is ', [0, 2, -1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [0, 3, -1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [0, 3, 1, -1]) 
('now depth move to ', 3) 
('now the answer is ', [1, 3, 1, -1]) 
('now depth move to ', 1) 
('now the answer is ', [1, 3, 1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [1, 3, 0, -1]) 
('now depth move to ', 3) 
('now the answer is ', [1, 3, 0, 2]) 
('now depth move to ', 4) 
('cur valid answer is ', [1, 3, 0, 2]) 
('now the answer is ', [2, 3, 0, 2]) 
('now depth move to ', 1) 
('now the answer is ', [2, 0, 0, 2]) 
('now depth move to ', 2) 
('now the answer is ', [2, 0, 3, 2]) 
('now depth move to ', 3) 
('now the answer is ', [2, 0, 3, 1]) 
('now depth move to ', 4) 
('cur valid answer is ', [2, 0, 3, 1]) 
('now the answer is ', [3, 0, 3, 1]) 
('now depth move to ', 1) 
('now the answer is ', [3, 0, 3, 1]) 
('now depth move to ', 2) 
('now the answer is ', [3, 0, 2, 1]) 
('now depth move to ', 3) 
('now the answer is ', [3, 1, 2, 1]) 
('now depth move to ', 2) 
None 

私は少し、すべての可能な解決策を生成するn_queen_find1を変更し、私は、同様の出力を説明することができませんでした。ここで

def n_queen_findall(n): 
    answer = [-1] * n 
    finalAnswer = [] 
    def dfs(depth,answer,finalAnswer): 
     if depth == n: 
      print ("cur valid answer is ",answer)    
      finalAnswer.append(answer) 
      print ("after appending final answer is ", finalAnswer) 
      return 
     else: 
      for colNum in range(n): # check every col at cur depth 
       if is_safe(depth,colNum,answer): 
        answer[depth] = colNum 
        print ("now the answer is ", answer) 
        print ("now depth move to ", depth + 1) 
        dfs(depth + 1,answer,finalAnswer) 

    def is_safe(i,j,answer_cur): 
     # given current queen placement , could we place the ith queen (at row i) at the col j 
     for prerow in range(i): 
      if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j): 
       return False 
     return True 
    dfs(0,answer,finalAnswer) 
    return finalAnswer 

はn_queen_findall .ITのための私のテストがあまりにも正しくありませんでしたです。まず、深さがnに等しくない場合にfinalAnswersが結果を追加する理由は何ですか？次に、finalAnswerに重複があった理由は？この問題のlong.The原因はpythonでかなりsimple.I'mジュニアでもよく、特にPythonが正しくありませんでした参照してPythonの通過の私の理解をbackend.Maybe？という質問を作るため申し訳ありません

trial2 = n_queen_findall(4) 
print trial2 
('now the answer is ', [0, -1, -1, -1]) 
('now depth move to ', 1) 
('now the answer is ', [0, 2, -1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [0, 3, -1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [0, 3, 1, -1]) 
('now depth move to ', 3) 
('now the answer is ', [1, 3, 1, -1]) 
('now depth move to ', 1) 
('now the answer is ', [1, 3, 1, -1]) 
('now depth move to ', 2) 
('now the answer is ', [1, 3, 0, -1]) 
('now depth move to ', 3) 
('now the answer is ', [1, 3, 0, 2]) 
('now depth move to ', 4) 
('cur valid answer is ', [1, 3, 0, 2]) 
('now the final answer is ', []) 
('now the answer is ', [2, 3, 0, 2]) 
('now depth move to ', 1) 
('now the answer is ', [2, 0, 0, 2]) 
('now depth move to ', 2) 
('now the answer is ', [2, 0, 3, 2]) 
('now depth move to ', 3) 
('now the answer is ', [2, 0, 3, 1]) 
('now depth move to ', 4) 
('cur valid answer is ', [2, 0, 3, 1]) 
('now the final answer is ', [[2, 0, 3, 1]]) 
('now the answer is ', [3, 0, 3, 1]) 
('now depth move to ', 1) 
('now the answer is ', [3, 0, 3, 1]) 
('now depth move to ', 2) 
('now the answer is ', [3, 0, 2, 1]) 
('now depth move to ', 3) 
('now the answer is ', [3, 1, 2, 1]) 
('now depth move to ', 2) 
[[3, 1, 2, 1], [3, 1, 2, 1]] 

これに関するいくつかのガイダンスを本当に感謝します。非常に前もってありがとう。

Answer 1

dfsには、n == 4の場合にのみreturnがありますが、nが他のものでない場合はありません。だから、が4に返っても、それは親呼び出し先に吸収され、最後に何も返されません。 dfs再帰が成功を確認する前にあれば答えは（else内部ifでforループが失敗するため）、Noneを返すには、私たちが失敗した配置を知っているので、

だから、あなたの最初の問題を解決するために、我々は追加します。その場合は、answerを返します。これに

dfs(depth + 1,answer) 

：だからこの変更私たちは第二の問題に取り組む前に

if dfs(depth + 1,answer): #false i.e None for failed dfs 
    return answer 

を、私たちは5つのソリューションを持っている場合、我々は正しい、それらを格納するために5つのアレイを必要とする、のは、考えてみましょうか？いくつ持っていますか？ 1 answer。 finalAnswer.append(answer)では、配列を含む新しいソリューションを追加していないので、answerのの参照を追加するだけです。これは常に変更されており、追加しようとしているものはすべて失われています。

したがって、追加する前に新しい配列をコピーして作成する必要があります。また、上記のreturnも取り除く必要があります。

印刷し

def n_queen_find1(n): 
    answer = [-1] * n 
    finalAnswer = [] 
    def dfs(depth,answer): 
     if depth == n: 
      print ("cur valid answer is ",answer) 
      finalAnswer.append([i for i in answer]) #answer is copied 
      return answer 
     else: 
      for colNum in range(n): # check every col at cur depth 
       if is_safe(depth,colNum,answer): 
        answer[depth] = colNum 
        #print ("now the answer is ", answer) 
        #print ("now depth move to ", depth + 1) 
        dfs(depth + 1,answer) 


    def is_safe(i,j,answer_cur): 
     # given current queen placement , could we place the ith queen (at row i) at the col j 
     for prerow in range(i): 
      if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j): 
       return False 
     return True 

    dfs(0,answer) 
    return finalAnswer 

：コメントを

cur valid answer is [1, 3, 0, 2] 
cur valid answer is [2, 0, 3, 1] 
[[1, 3, 0, 2], [2, 0, 3, 1]]