在Java中使用回溯法的數獨求解器

Question

我想在java中製作一個數獨求解器，但它不像預期的那樣工作，我找不出原因。我在評論中添加了以下代碼，希望有人能夠找出問題所在。出於某種原因，它在中間停頓。我懷疑這是一個無限循環，沒有錯誤，但我無法識別它。有更多的代碼，但沒有必要，因爲它只是印刷板和填充板。

private static int row2 = 0; 
private static int col2 = 0; 
private static boolean isEnd = false; 

public static void backTrack(String[][] puzzle) { 
    int[][] puzzle2 = new int[9][9]; 
    for (int i = 0; i < 9; i++) { 
     for (int i2 = 0; i2 < 9; i2++) { 
      puzzle2[i][i2] = Integer.parseInt(puzzle[i][i2]); //Takes the String puzzle and turns it into integers and adds it to puzzle2 
     } 
    } 
    int[][] puzzle3 = new int[9][9]; 
    puzzle3 = puzzle2; //Initiates puzzle3 so that I can have a fresh copy that I can use to reference to later 
    while (isEnd == false) { //isEnd is defined in nextCell and determines whether or not the solution has been found or not 
     if (puzzle3[row2][col2] != 0) { 
      nextCell(); //if the cell was originally already set (that is why I use puzzle3), then it should just go to the next cell 
     } else if (puzzle3[row2][col2] == 0) { //0 being empty. So if the cell was not originally filled 
      while (puzzle2[row2][col2] <= 9) { 
       puzzle2[row2][col2] = puzzle2[row2][col2] + 1; //Add 1 to the current number in the cell 
       if (puzzle2[row2][col2] == 10) { //If it is 10, since it can, then it means that none of the numbers have worked in that cell, so it should go back a cell 
        puzzle2[row2][col2] = 0;//Sets it to 0 before going back one cell 
        backCell(); //method to go back a cell 
        while(true){ 
         if(puzzle3[row2][col2]!=0){ 
          backCell(); //if the cell it goes back onto was originally set, then it should keep going back until it finds one that it can change 
         } 
         else{ 
          break; //breaks out of the infinite while loop , so that it can carry on checking solutions from the cell it just went onto. 
         } 
        } 
        break; //breaks out of the second while loop 
       } 
       if (isValid(row2, col2, puzzle2[row2][col2], puzzle2)) { 
        nextCell(); //if the new number is valid, then it should go to the next cell and try out solutions from there 
        break; 
       } 
      } 
     } 
    } 

    printBoard2(puzzle2); // method to print the board(which is meant to be solved at this point 
} 
public static void backCell() { 
    col2--; 
    if (col2 < 0) { 
     col2 = 8; 
     row2--; 
    } 
    if (row2 < 0) { 
     row2 = 0; 
     col2 = 0; 
    } 
} 

public static void nextCell() { 
    col2++; 
    if (col2 > 8) { 
     col2 = 0; 
     row2++; 
    } 
    if (row2 > 8) { 
     isEnd = true; //if it manages to reach the end of the puzzle, it can be assumed that the solution has been found 
    } 
} 
public static boolean isValid(int row, int col, int value, int[][]puzzle) {  
    boolean check = true; 
    for (int i3 = 0; i3 < 9; i3++) { 
     if (i3 != col) { 
      if (puzzle[row][i3] == (value)) { 
       check = false; 
       break; 

      }//checks whether the values are repeated in the same row 
     } 

    } 
    for (int i3 = 0; i3 < 9; i3++) { 
     if (i3 != row) { 
      if (puzzle[i3][col] == (value)) { 
       check = false; 
       break; 
      } 
     }//checks whether the values are repeated in the same column 

    } 

    int initRow = 0; 
    int initCol = 0; 
    if (row <= 2) { 
     initRow = 0; 
    } else if (row <= 5 && row > 2) { 
     initRow = 3; 
    } else if (row <= 8 && row > 5) { 
     initRow = 6; 
    } 
    if (col <= 2) { 
     initCol = 0; 
    } else if (col <= 5 && col > 2) { 
     initCol = 3; 
    } else if (col <= 8 && col > 5) { 
     initCol = 6; 
    }//finds the top left coordinates of the box that it is in 

    if (puzzle[initRow][initCol] == value 
      && (initRow != row || initCol != col)) { 
     check = false; //checks whether the value is in the box. The second part of each if statement checks whether the coordinates are the same as the value entered(since the value is already added before validation) 
    } 
    if (puzzle[initRow + 1][initCol] == value 
      && ((initRow + 1) != row || initCol != col)) { 
     check = false; 
    } 
    if (puzzle[initRow + 2][initCol] == value 
      && ((initRow + 2) != row || initCol != col)) { 
     check = false; 
    } 
    if (puzzle[initRow][initCol + 1] == value 
      && (initRow != row || (initCol + 1) != col)) { 
     check = false; 
    } 
    if (puzzle[initRow][initCol + 2] == value 
      && (initRow != row || (initCol + 2) != col)) { 
     check = false; 
    } 
    if (puzzle[initRow + 1][initCol + 1] == value 
      && ((initRow + 1) != row || (initCol + 1) != col)) { 
     check = false; 
    } 
    if (puzzle[initRow + 2][initCol + 1] == value 
      && ((initRow + 2) != row || (initCol + 1) != col)) { 
     check = false; 
    } 
    if (puzzle[initRow + 1][initCol + 2] == value 
      && ((initRow + 1) != row || (initCol + 2) != col)) { 
     check = false; 
    } 
    if (puzzle[initRow + 2][initCol + 2] == value 
      && ((initRow + 2) != row || (initCol + 2) != col)) { 
     check = false; 
    } 

    if (check == true) { 
     return true; 
    } else { 
     return false; 
    } 

} 
public static void main(String[]args){ 
    String[][] puzzle = new String[9][9]; 
    fillBoard(puzzle); 
    backTrack(puzzle); 
} 

Answer 1

此行不 「進行復印」 你的陣列的

puzzle3 = puzzle2 

您可以在同一時間puzzle2初始化puzzle3：

int[][] puzzle2 = new int[9][9]; 
    int[][] puzzle3 = new int[9][9]; 
    for (int i = 0; i < 9; i++) { 
     for (int i2 = 0; i2 < 9; i2++) { 
      int v = Integer.parseInt(puzzle[i][i2]); 
      puzzle2[i][i2] = v; //Takes the String puzzle and turns it into integers and adds it to puzzle2 
      puzzle3[i][i2] = v; 
     } 
    }