파이썬에서 스도쿠의 반복 솔루션

Question

def answer_solve_sudoku(__grid): 

    res = check_sudoku(__grid) 
    if res is None or res is False: 
     return res 

    grid = copy.deepcopy(__grid) 

    # find the first 0 element and change it to each of 1..9, 
    # recursively calling this function on the result 
    for row in xrange(9): 
     for col in xrange(9): 
      if grid[row][col] == 0: 
       for n in xrange(1, 10): 
        grid[row][col] = n 
        new = answer_solve_sudoku(grid) 
        if new is not False: 
         return new 
       # backtrack 
       return False 

    # if we get here, we found no zeros and so we're finished 
    return grid 

여기 코드가 있으며 check_sudoku(grid)은 유효한 스도쿠인지 아닌지를 반환 할 수 있습니다.

난 그냥 재귀 부분을 이해할 수 없다, 나는 종이에 프로세스를 적어 봤지만 매번 실패했다, 어떻게 backtraking 작동합니까? new은 무엇입니까? answer_solve_sudoku(grid)이 유효하면?

매번 0에서 1..9까지를 설정하고 그것이 유효한 그리드인지 아닌지를 확인하지만, 전체 프로세스를 종이에 그릴 수는 없습니다. 그리고 백 트랙이 어떻게 작동하는지 이해할 수 없습니다.

btw, 재귀 코드 이해에 대한 조언이 있습니까?

최고 감사합니다,

쉥 윤

편집

나는 또 다시 코드를 읽고, 지금은 어떤 이해를 가지고 있지만, 이것에 대해 확인 그냥 해요, 누군가가 나에게 약간의 의견을 주면 그것은 친절 할 것이다.

# backtrack 
return False 

가 호출 될 때

, 상기 솔버는 솔루션을 발견 할 때

1, return new에만 호출 될 것이다 , 이는 오른쪽 return grid

2 후에 호출 될 것인가? 다음 해결 방법이 올바르지 않으면 check_sudoku(__grid)은 False을 반환하고 다음 해결 방법이 맞으면 올바른 해결책을 얻을 때까지 answer_solve_sudoku(grid)을 다시 호출하고 올바른 해결 방법을 얻으면 return grid, return new이됩니다. 따라서 언제입니까 :

# backtrack 
return False 

Answer 1

종이에이 글을 쓰는 것이 아니라 더 나은 권장 사항이 있습니다. 논리가 수행하는 작업을 시각적으로 표현하기 위해 코드를 형식화하십시오.

def print_counter(val, msg): 
    print "%s[%d] %s" % (" "*val, val, msg) 

def answer_solve_sudoku(__grid, counter=0): 

    res = check_sudoku(__grid) 
    if res is None or res is False: 
     return res 

    grid = copy.deepcopy(__grid) 

    for row in xrange(9): 
     for col in xrange(9): 
      if grid[row][col] == 0: 
       for n in xrange(1, 10): 
        grid[row][col] = n 
        print_counter(counter,"test: (row %d, col %d) = %d" % (row,col,n)) 
        new = answer_solve_sudoku(grid, counter+1) 
        if new is not False: 
         print_counter(counter, "answer_solve_sudoku() solved: returning") 
         return new 
       # backtrack 
       print_counter(counter, "backtrack") 
       return False 

    print_counter(counter, "**SOLVED! Returning back up to top**") 
    return grid 

from pprint import pprint 
solution = answer_solve_sudoku(easy_grid) 
pprint(solution) 

것은 내가 한 것은 번호를 인쇄하고 많은 공백으로 메시지를 들여하는 작은 프린터 기능을 작성했다 : 여기에 있다고 할 수있는 방법입니다. 그런 다음 answer_solve_sudoku에서 기본 카운터 값을 0으로 지정하고 항상 각 재귀 호출에 카운터 + 1을 전달합니다. 깊이가 커지면 그렇게 될 것입니다. 그리고 프린터 기능을 시각적으로 설명하는 방법을 따라 진행합니다. 당신이 볼 무엇

이 같은 것입니다 :

[0] test: (row 0, col 2) = 1 
[0] test: (row 0, col 2) = 2 
[0] test: (row 0, col 2) = 3 
[0] test: (row 0, col 2) = 4 
[1] test: (row 0, col 3) = 1 
    [2] test: (row 0, col 4) = 1 
    [2] test: (row 0, col 4) = 2 
    [2] test: (row 0, col 4) = 3 
    ... 
     [45] test: (row 7, col 7) = 8 
     [45] test: (row 7, col 7) = 9 
     [45] backtrack 
     [44] test: (row 7, col 5) = 6 
     [44] test: (row 7, col 5) = 7 
    ... 
       [51] test: (row 8, col 6) = 6 
       [51] test: (row 8, col 6) = 7 
       [52] **SOLVED! Returning back up to top** 
       [51] answer_solve_sudoku() solved: returning 
       [50] answer_solve_sudoku() solved: returning 
      [49] answer_solve_sudoku() solved: returning 
    ... 
    [2] answer_solve_sudoku() solved: returning 
[1] answer_solve_sudoku() solved: returning 
[0] answer_solve_sudoku() solved: returning 

새로운 수익이 바로 반환 그리드 후 솔버는 솔루션, 을 발견했을 때에만 호출하고이 호출됩니다

예, answer_solve_sudoku에 대한 호출이 실패없이 전체 루프를 통과하여 하단에 도달하면 성공하여 그리드를 반환합니다.그러면 호출자는 해당 모눈을 결과로 new = answer_solve_sudoku(grid)으로 가져 와서 반환합니다. 그리드는 스택에서 돌아 오는 각 호출을 백업합니다.

언제 역 추적합니까?

각 반복에서 모눈 복사본을 만들므로 해당 단계에서 솔루션을 찾지 못하면 해당 모눈에 대한 변경 사항이 무시됩니다. 한 번 단계로 돌아 오면 다시 돌아옵니다. 이전 그리드 상태. 그것은 9의 값을 지나칠 때까지 가능한 한 멀리 그 솔루션으로 갈려고합니다.

Answer 2

당신은 이것을 체크 아웃해야합니다 answer. 재귀 적 역 추적을위한 의사 코드와 실제 코드가 있습니다. 이 코드는 Java로 작성되었지만 Python과 동일한 생각 프로세스입니다.