스도쿠 해결 알고리즘이 예상대로 작동하지 않습니다.

Question

스도쿠스를 해결하는 프로그램을 작성하려고합니다. 퍼즐을 푸는데 역 추적을 사용하고 있습니다.

필자가 볼 수있는 한, 제 코드는 작동해야하지만 외관상으로는 그렇지 않습니다. 코드에서 다른 단계의 퍼즐을 보았지만 전혀 변하지 않았습니다. 나는 무엇을해야할지 모른다. 여기에 코드

: 내가 볼 수

public class main { 

    public static int[][] originalGrid; 

    public static void main(String[] args){ 
     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}}; 
     originalGrid = grid; 
     solveSudoku(grid, 0, 0); 
     System.out.println("Done!"); 
    } 

    public static boolean solveSudoku(int[][] grid, int row, int col) { 

     //base case 
     if (noUnassignedLocation(grid)){ 
      printGrid(grid); 
      return true; 
     } 

     for (int i = 0; i < 9; i++) { 
      if (noConflict(grid)) { 

       if (originalGrid[row][col] == 0) 
        grid[row][col] = i; 

       printGrid(grid); 

       col++; 
       if (col == 9) { 
        col = 0; 
        if (row != 8) 
         row++; 
       } 
       if (solveSudoku(grid, row, col)) 
        return true; 
       grid[row][col] = 0; 
       col--; 
       if (col == 0) { 
        col = 9; 
        row--; 
       } 
      } 
     } 
     printGrid(grid); 
     return false; 
    } 

    public static boolean noConflict(int[][] grid) { 
     for (int i = 0; i < 9; i++) { 
      for (int j = 0 ; j < 9; j++) { 
       int current = grid[i][j]; 

       //System.out.println("i: " + i + " j: " + j); 

       for (int k = 0; k < 9; k++) { 
        if (current == grid[k][j] && k != i && current != 0 && grid[k][j] != 0) { 
         return false; 
        } 
       } 
       for (int k = 0; k < 9; k++) { 
        if (current == grid[i][k] && k != j && current != 0 && grid[i][k] != 0) { 
         return false; 
        } 
       } 
       //check block 
      } 
     } 
     return true; 
    } 

    public static boolean noUnassignedLocation(int[][] grid) { 
     for (int i = 0; i < 9; i++) { 
      for (int j = 0; j < 9; j++) { 
       if (grid[i][j] == 0) { 
        return false; 
       } 
      } 
     } 
     return true; 
    } 

    private static void printGrid(int[][] grid) { 
     System.out.println("###########"); 
     for (int i = 0; i < 9; i++) { 
      String line = new String(); 
      for (int j = 0; j < 9; j++) { 
       line = line + grid[i][j]; 
      } 
      System.out.println("#" + line + "#"); 
     } 
     System.out.println("###########"); 
    } 
} 

Answer 1

하나의 문제는 당신이 grid 및 originalGrid 서로 다른 2 차원 배열 인 가정 것으로 보인다

if (originalGrid[row][col] == 0) 
    grid[row][col] = i; 

여기에 있다는 것입니다. 사실, 그것들은 초기화하는 방식 때문에 같은 배열입니다. 이것 :

originalGrid = grid; 

은 간단한 참조 지정입니다. grid 배열의 복사본을 만들지 않습니다.

Answer 2

희망이 당신이나 미래의 사람을 도와주세요!

프로그램에 많은 버그가있었습니다. solveSudoku()를 다시 작성하고 noConflict() 메소드를 완료했습니다.

public class Sudoku { 
public static void main(String[] args) { 
    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 } 
     }; 

    //originalGrid = grid; 
    solveSudoku(grid); 
    System.out.println("Done!"); 
    printGrid(grid); 
} 

public static boolean solveSudoku(int[][] grid) { 

    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      if (grid[i][j] != 0) { 
       continue; 
      } 
      for (int num = 1; num <= 9; num++) { 
       if (noConflict(grid)) { 
        grid[i][j] = num; 
        if (solveSudoku(grid)) { 
         return true; 
        } else { 
         grid[i][j] = 0; 
        } 
       } 
      } 
      return false; 
     } 
    } 
    return true; 
} 

/** 
* Checks row, column and box have unique values. 
* 
* @param grid 
* @return 
*/ 
public static boolean noConflict(int[][] grid) { 
    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      //int current = grid[i][j]; 

      // check row unique 
      for (int k = 0; k < 9; k++) { 
       if (grid[i][j] == grid[k][j] && k != i && grid[i][j] != 0 
         && grid[k][j] != 0) { 
        return false; 
       } 
      } 

      //check column unique 
      for (int k = 0; k < 9; k++) { 
       if (grid[i][j] == grid[i][k] && k != j && grid[i][j] != 0 
         && grid[i][k] != 0) { 
        return false; 
       } 
      } 

      // check block 
      for (int row = (i/3)*3; row < (i/3)*3+3; row++) { 
       for (int col = (j/3)*3; col < (j/3)*3+3; col++) { 
        if(row != i && col!=j && grid[row][col]==grid[i][j] && grid[i][j] != 0) { 
         return false; 
        } 
       } 
      } 

     } 
    } 
    return true; 
} 

public static boolean noUnassignedLocation(int[][] grid) { 
    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      if (grid[i][j] == 0) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

private static void printGrid(int[][] grid) { 
    System.out.println(); 
    for (int i = 0; i < 9; i++) { 
     String line = new String(); 
     for (int j = 0; j < 9; j++) { 
      line = line + grid[i][j]; 
     } 
     System.out.println(line); 
    } 
    System.out.println(); 
} 
}