Java 问题中的暴力数独求解器算法

除了求解方法之外，算法中的一切似乎都运行良好。当它使用可解数独板执行程序时，它会说无法解决。我已经尝试了解决方法中我能想到的一切。我尝试过调试，但在测试第一行后失败。有什么建议么？这是到目前为止的完整代码：

    public class SudokuSolver {

 public static void initializeGrid(int[][] grid, int[][] puzzle) {

  for (int r = 0; r < puzzle.length; r++) {
  for (int c = 0; c < puzzle[0].length; c++) {
  grid [r][c] = puzzle [r][c];
   }
  } 
 }

 public static void displayGrid(int[][] grid) {

  for (int r = 0; r < grid.length; r++) {
   if (r % 3 == 0) {
   System.out.println("+---+---+---+");
   }
   for (int c = 0; c < grid[r].length; c++) {
if (c % 3 == 0) {
 System.out.print("|");
}
displayDigits(r, c, grid);

} System.out.print("|"); System.out.println(); } System.out.println("+---+---+---+"); }

if (网格[r][c] == 0) { System.out.print(' '); } 别的 { System.out.print(grid[r][c]); } } 公共静态 int getEmptyCells(int[][] grid, int[][] emptyCells) { 整数 i = 0; int numEmptyCells = 0; for (int r = 0; r

私有静态布尔 hasNoDuplicates(int[]digitsList) { for (int j = 0; j

私有静态布尔 checkCurrentRow(int[][] grid, int currentRow) {
int[]digitsList = new int[grid.length]; for (int c = 0; c

私有静态布尔 checkCurrentCol(int[][] grid, int currentCol) { int[]digitsList = new int[grid.length]; for (int i = 0; i

私有静态布尔 checkCurrentRegion(int[][] grid, int currentRow, int currentCol) {
int[]digitsList = new int[grid.length]; 当前行 = (当前行 / 3) * 3; 当前列 = (当前列 / 3) * 3; 整数 i = 0; for (int r = 0; r

公共静态布尔 isConsistent(int[][] grid, int currentRow, int currentCol) { if (checkCurrentRow(网格, currentRow) && checkCurrentCol(网格, currentCol) && checkCurrentRegion(网格, currentRow, currentCol)) { 返回真； } 返回假； }

公共静态布尔solvePuzzle（int [] []网格，int [] []emptyCells，int numEmptyCells）{ 整数 i = 0; 整数 j = 0; int currentCellDigit = grid[emptyCells[i][0]][emptyCells[i][1]]; while (j

返回真；
}

公共静态无效主（字符串[] args）{

最终 int 大小 = 9; int[][] 谜题 = { {0,2,9,0,0,3,0,0,5}, {5,0,7,0,0,0,0,9,0}, {6,0,0,0,0,9,4,2,0}, {3,0,2,0,0,4,0,0,0}, {0,0,5,0,3,0,7,0,0}, {0,0,0,5,0,0,6,0,2}, {0,9,8,4,0,0,0,0,3}, {0,3,0,0,0,0,1,0,6}, {2,0,0,3,0,0,9,4,0} };

int[][] grid = new int[SIZE][SIZE]; int[][]emptyCellsList = new int[SIZE*SIZE][2]; int numEmptyCells = 0;

initializeGrid(grid, puzzle); numEmptyCells = getEmptyCells(grid, emptyCellsList); System.out.println("The puzzle:"); displayGrid(puzzle); if (solvePuzzle(grid, emptyCellsList, numEmptyCells)) { System.out.println("has been solved:"); displayGrid(grid); } else { System.out.println("cannot be solved!"); } } }

你的initializeGrid是错误的。恕我直言，应该是：

for (int c = 0; c < puzzle[r].length; c++)

代替

for (int c = 0; c < puzzle[0].length; c++)

编辑：我的回答如下

它已正确缩进（第 1 课）并相应地排列了花括号（第 2 课）。学习逐行理解您想要执行的操作，当您陷入特定行或方法调用时，请寻求帮助（第 3 课）。下面的代码可以编译，但还不能解决这个难题。为我阅读并替换solvePuzzle 中的注释（第4 课）。做一些思考和分析，因为这是你的作业；）祝你好运！

public class SudokuSolver {
  public static void initializeGrid(int[][] grid, int[][] puzzle) {
   for (int r = 0; r < puzzle.length; r++) {
     for (int c = 0; c < puzzle[0].length; c++) {
       grid [r][c] = puzzle [r][c];
     }
   } 
  }
  
  public static void displayDigits(int r, int c, int[][] grid) {
    if (grid[r][c] == 0) {
      System.out.print('0');
    } else {
      System.out.print(grid[r][c]);
    }
  }

  public static void displayGrid(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
      if (r % 3 == 0) {
        System.out.println("+---+---+---+");
      }
      for (int c = 0; c < grid[r].length; c++) {
        if (c % 3 == 0) {
          System.out.print("|");
        }
      displayDigits(r, c, grid);
      }
      System.out.print("|");
      System.out.println();
    }
    System.out.println("+---+---+---+");
  }
 
  public static int getEmptyCells(int[][] grid, int[][] emptyCells) {
    int i = 0;
    int numEmptyCells = 0;
    for (int r = 0; r < grid.length; r++) {
       for (int c = 0; c < grid[r].length; c++) {
         if (grid[r][c] == 0) {
           emptyCells[i][0] = r;
           emptyCells[i][1] = c;
           numEmptyCells++;
           i++;
         }
       }
    }
    return numEmptyCells;
  }
  
  private static boolean hasNoDuplicates(int[] digitsList) {
    for (int j = 0; j < digitsList.length; j++) {
      for (int k = j + 1; k < digitsList.length; k++) {
        if (digitsList[j] == digitsList[k] && digitsList[j] != 0)
          return false;
      }
    }
    return true;
  }

  private static boolean checkCurrentRow(int[][] grid, int currentRow) {
    int[] digitsList = new int[grid.length];
    for (int c = 0; c < digitsList.length; c++) {
      digitsList[c] = grid[currentRow][c];
    }
    if (hasNoDuplicates(digitsList)) {
      return true;
    }
    return false;
  }

  private static boolean checkCurrentCol(int[][] grid, int currentCol) {
    int[] digitsList = new int[grid.length];
    for (int i = 0; i < digitsList.length;  i++) {
      digitsList[i] = grid[i][currentCol];
    }
    if (hasNoDuplicates(digitsList)) {
      return true;
    }
    return false;
  }

  private static boolean checkCurrentRegion(int[][] grid, int currentRow,
       int currentCol) {
    int[] digitsList = new int[grid.length];
    currentRow = (currentRow / 3) * 3;
    currentCol = (currentCol / 3) * 3;
    int i = 0;
    for (int r = 0; r < 3; r++) {
      for (int c = 0; c < 3; c++) {
        digitsList[i] = grid[currentRow + r][currentCol + c];
        i++;
      }
    }
    if (hasNoDuplicates(digitsList)) {
      return true;
    }
    return false;
  }

  public static boolean isConsistent(int[][] grid, int currentRow,
       int currentCol) {
    boolean checkRow = checkCurrentRow(grid, currentRow);
    boolean checkCol = checkCurrentCol(grid, currentCol);
    boolean checkReg = checkCurrentRegion(grid, currentRow, currentCol);
    System.out.println("r: " + checkRow + " c: " + checkCol + " r: " + checkReg);
    if (checkRow && checkCol && checkReg) {
      return true;
    }
    return false;
  }

  public static boolean solvePuzzle(int[][] grid, int[][] emptyCells,
      int numEmptyCells) {
    int i = 0;
    int currentCellDigit = 0;
    while (i < numEmptyCells) {
      if (currentCellDigit != 9) {
        // increment cell value
        currentCellDigit++;
        // assign to current cell the current cell value
        //<var> = currentCellDigit;
        System.out.println("Solving---------------------- :" +
            currentCellDigit + " R: " +
            emptyCells[i][0] + " C: " + emptyCells[i][1]);
        // check if value is valid
        if (isConsistent(grid, emptyCells[i][0], emptyCells[i][1])) {
          // reset after setting
          i++;
          currentCellDigit = 0;
        } else {
          // reset cell to zero instead of decrementing it since we're backtracking!
          //grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit - 1;
          //<var> = 0;
        }
      } else {
        // reset current cell to 0
        //<var> = 0;
        // go to previous cell
        i--;
        // exit if theres no cell to backtrack to
        if (i < 0) {
          return false;
        }
        // set previous' cell value as current cell value
        //<var> = grid[emptyCells[i][0]][emptyCells[i][1]];
      }
    }
    return true;
  }
  
  public static void main(String[] args) {
    final int SIZE = 9;
    int[][] puzzle  = { {0,2,9,0,0,3,0,0,5},
                        {5,0,7,0,0,0,0,9,0},
                        {6,0,0,0,0,9,4,2,0},
                        {3,0,2,0,0,4,0,0,0},
                        {0,0,5,0,3,0,7,0,0},
                        {0,0,0,5,0,0,6,0,2},
                        {0,9,8,4,0,0,0,0,3},
                        {0,3,0,0,0,0,1,0,6},
                        {2,0,0,3,0,0,9,4,0}
                    };

    int[][] grid = new int[SIZE][SIZE];
    int[][] emptyCellsList = new int[SIZE*SIZE][2];
    int numEmptyCells = 0;

    initializeGrid(grid, puzzle);
    numEmptyCells = getEmptyCells(grid, emptyCellsList);
    System.out.println("The puzzle:");  
    displayGrid(puzzle);
    if (solvePuzzle(grid, emptyCellsList, numEmptyCells)) {
      System.out.println("has been solved:");
      displayGrid(grid);
    } else {
      System.out.println("cannot be solved!");
    }
  }
}

附：如果您用正确的代码替换了上面的注释，这将进行回溯。