Sudoku 솔버의 구현은 상태를 저장하지 않고 어떻게 작동합니까?

Question

This 링크에는 Sudoku Solver 알고리즘의 Backtracking 구현이 있습니다. 처음에 할당 된 값이 유효한 출력을 제공하지 않을 경우 행 번호 42가 셀에 처음 할당 된 값을 다른 값으로 되돌려 놓는 것에 유의하십시오.

그러나 셀의 값을 변경하는 것만으로 얼마나 효과가 있는지 이해할 수 없습니다. 이 호출은 배열 (행렬)이 메모리 (참조)에 의해 전달 되었기 때문에 많은 다른 호출을 트리거 할 수 있었고 일 수 있었으며 재귀 적 호출을 할 때마다 행렬 (grid [N] [N])의 복사본을 보관하지 않습니다. 함수이므로 재귀의 기본 경우가 반환 될 때까지 재귀의 첫 번째 프레임에도 반영됩니다.

나에 따르면, 재귀 함수를 호출하기 전에 grid [N] [N]의 임시 복사본을 만들고 호출이 반환되고 즉시 같은 프레임의 다음 함수가 실행되기 전에 복원해야합니다. 라는.

for (int num = 1; num <= N; num++) 
    { 
     // if looks promising 
     if (isSafe(grid, row, col, num)) 
     { 
      //save grid state 
      int[][] temp = new int[N][N]; 
      save(temp,grid); //copy all values from grid to temp    

      // make tentative assignment 
      grid[row][col] = num; 

      // return, if success, yay! 
      if (SolveSudoku(grid)) 
       return true; 

      //restore grid state   
      restore(temp,grid); //copy all values from temp back to grid 

      // failure, unmake & try again 
      grid[row][col] = UNASSIGNED; 
     } 
    } 

날이 세부 사항을 이해하는 데 도움이됩니다 같은

는

뭔가.

Answer 1

은입니다. 저장 상태 : 각 재귀 호출은 호출 스택에 상태를 저장합니다.

그리드의 할당되지 않은 부분은 유효한 해결책이 발견 될 때까지 수정됩니다. 일단 스택 된 함수 호출은 모두 종료되고 (38 및 39 행), grid[][]은 해결 된 상태로 남습니다. 그렇지 않으면 현재 셀을 UNASSIGNED 값으로 복원하고 다음 가능한 값을 시도합니다.

이것은 무차별 대항력 해결사입니다. 당신도 그 주위에 구글 싶지 수도 있습니다.

희망이 도움이됩니다.