재귀 백 트랙킹 관련 문제

Question

스도쿠 문제를 해결하기 위해 Java에서 백 트랙킹 알고리즘을 구현하려고합니다.

나는 문제가 해결 방법에 있다고 확신하지만, 두 가지 방법을 포함했다.

내가하고있는 이상한 일들 중 일부는 퍼즐의 하드 코딩 된 초기 값과 같은 요구 사항/편의성 때문일뿐입니다. 문제는 내 해결 방법의 바닥 근처에 있다고 확신하지만, 그것을 이해할 수 없다 ...

내 현재 문제는 : 첫 번째 행에서 작업 한 후 값의 잠재적 인 유효 순열을 찾은 후, 내 프로그램은 단순히 포기합니다. "ROW IS DONE"을 인쇄하는 줄의 주석 처리를 제거하면 하나의 줄 다음에 출력되고 출력은 더 이상 출력되지 않습니다. 첫 번째 행 이후에 포기하는 이유는 무엇입니까? 내 구현에 대해 다른 것이 있습니까 걱정해야합니다

편집 : 많이 변경했습니다. 아주 가까워지고 있습니다. EXHAUST가 참일 때 인쇄하면, 마지막 행을 제외한 모든 행이 풀린 퍼즐을 얻습니다. 그것은 그것이 해결되었거나 거의 해결 된 후에 모든 것을 취소하고있는 것처럼 보입니다. 나는 퍼즐이 완전히 풀린 지점에 이미 도달했을 것 같은 느낌을 갖지만 적절한 시간에 TRUE를 되돌려주지는 않습니다 ... 지금 내가 뭘 잘못하고 있니?

import java.util.ArrayList; 

class Model 
{ 
    ArrayList<View> views = new ArrayList<View>(); 
    int[][] grid = 
      { 
       {5,3,0,0,7,0,0,0,0}, 
       {6,0,0,1,9,5,0,0,0}, 
       {0,9,8,0,0,0,0,6,0}, 
       {8,0,0,0,6,0,0,0,3}, 
       {4,0,0,8,0,3,0,0,1}, 
       {7,0,0,0,2,0,0,0,6}, 
       {0,6,0,0,0,0,2,8,0}, 
       {0,0,0,4,1,9,0,0,5}, 
       {0,0,0,0,8,0,0,7,9} 
      }; 

    /** 
    * Method solve 
    * 
    * Uses a backtracking algorithm to solve the puzzle. 
    */ 
    public boolean solve(int row, int col) //mutator 
    { 
     if(exhaust(row,col)) {printGrid(); return true;} 
     int rownext = row; 
     int colnext = col+1; 
     if(colnext>8) 
     { 
      colnext = 0; 
      rownext++; 
     }   
     if(grid[row][col] != 0) solve(rownext,colnext); 
     else //is == 0 
     { 
      for(int num = 1; num <= 9; num++) 
      { 
       if(!conflict(row,col,num)) //try a non-conflicting number 
       { 
        grid[row][col] = num; 
        if(solve(rownext,colnext)) return true;      
        grid[row][col] = 0; 
       } 
      } 
     } 
     return false;  

    } 
    /** 
    * Method exhaust 
    * 
    * Iteratively searches the rest of the puzzle for empty space 
    * using the parameters as the starting point. 
    * 
    * @return true if no 0's are found 
    * @return false if a 0 is found 
    */ 
    public boolean exhaust(int row, int col) 
    { 
     for(int i = row; i <= 8; i++) 
     { 
      for(int j = col; j <= 8; j++) 
      { 
       if(grid[i][j] == 0) return false; 
      } 
     } 
     System.out.printf("Exhausted.\n"); 
     return true; 
    } 

    /** 
    * Method conflict 
    * 
    * Checks if the choice in question is valid by looking to see 
    * if the choice has already been made in the same row or col, 
    * or block. 
    * 
    * @return true if there IS a conflict 
    * @return false if there is NOT a conflict 
    */ 
    public boolean conflict(int row, int col, int num) 
    { 
     for(int j = 0; j <= 8; j++) 
     { 
      if(grid[row][j] == num) { 
       return true; 
      } 
     } 
     for(int i = 0; i <= 8; i++) 
     { 
      if(grid[i][col] == num) { 
       return true; 
      } 
     }   

     int rowstart = 0; 
     if(row>=3) rowstart = 3; 
     if(row>=6) rowstart = 6; 

     int colstart = 0; 
     if(col>=3) colstart = 3; 
     if(col>=6) colstart = 6;      

     for(int r = rowstart; r <= (rowstart + 2); r++) 
     { 
      for(int c = colstart; c <= (colstart + 2); c++) 
      { 
       if(grid[r][c] == num) { 
        return true; 
       } 
      } 
     }  
     return false; 
    } 
} 

Answer 1

앞으로 부드럽게, 행 단위로 이동하고 되돌아 가지 않았다고 가정 해보십시오. 귀하의 다음 직책은 solve(1,1);입니다. 코드를 추적 할 때 rownext에주의하십시오. 문제가 빨리 보일 것입니다. 역 추적을하지 않으면 rownext는 적어도 1의 값을 유지해야합니다.