在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; 
     } 
    }