깊이 우선 스도쿠 해결하는 방법?

Question

저는 퍼즐을 풀기 위해 depth-first "brute-force"를 사용하는 파이썬에서 스도쿠 퍼즐 해답을 만들려고합니다. 그러나 여러 번 반복해서 기록한 후에도 같은 오류가 계속 발생합니다.

가능한 한 명확하게 문제를 설명하기 위해 최선을 다할 것입니다. 이것이 깊이 우선 검색과 관련된 첫 번째 문제이므로 분명하지 않은 내용 일 수 있습니다. 여기

는 (세부 사항이 필요하지 않은 곳에서 의사 코드와 혼합) 컷 다운 코드 : 나는 그것을 할 수 있기 때문에

def solvePuzzle(puzzle): 
    <while the puzzle is still not solved>: 
     <make a copy of the puzzle> 
     <go through each unsolved box>: 
      <try to find the value of the box> 
      <if the current solution is impossible, return to the parent branch> 
     <if the copy of the puzzle is exactly the same as the puzzle now, no changes have been made, so its time to start branching into different possibilities>:  
      <pick a random box to guess the number of> 
      <go through each possible value and run solvePuzzle() on that puzzle>: 
       <if a solution is returned, return it> 
       <else, try the next possible value> 
    <return the puzzle> 

로 줄일 ​​수있어 - 미안 경우는 아직 조금 읽기/혼란의.

어떤 이유로 든 퍼즐을 만든 각 복사본을 solvePuzzle()에 설정 한 후에도 모든 복사본이 불가능하다는 것을 알 수 있습니다 (불가능 함으로 인해 추측에 오류가 있음). 모든 숫자가 테스트되기 때문에 이것이 가능하지 않습니다!

Here's the full code (약 50 줄의 코드)으로 충분하지 않을 수 있습니다.

누구든지 도을 제안 할 수 있다면 왜 이런 식으로 작동하지 않는지, 나는 크게 감사 할 것입니다.

감사합니다.

편집 :As promised, here's the "isSolved()" method.

Answer 1

내가 강하게 문제는 여기에 의심 :

각 후보 값에 대한 clone 사본을 변이합니다, 그리고 반 해결 퍼즐의 상태로 복원하지 않습니다

# Go through each possibility in the branch until one solution is found 
clone = deepcopy(puzzle) 
values = clone[index/9][index % 9] 
for value in values: 
    clone[index/9][index % 9] = value 
    branch = solvePuzzle(clone) 
    # If a list is returned, it worked! Otherwise, try the next possibility 
    if isinstance(branch, list): 
     return branch 

모순을 발견했을 때. 이것을 시도하십시오 :

# Go through each possibility in the branch until one solution is found 
values = puzzle[index/9][index % 9] 
for value in values: 
    clone = deepcopy(puzzle) 
    clone[index/9][index % 9] = value 
    branch = solvePuzzle(clone) 
    # If a list is returned, it worked! Otherwise, try the next possibility 
    if isinstance(branch, list): 
     return branch