logo标签列表

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

javaalgorithmsudoku
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 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("+---+---+---+"); }

如果 (grid[r][c] == 0) { System.out.print(' '); } else { System.out.print(grid[r][c]); } } 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++) { 如果 (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++) { 如果 (digitsList[j] == digitsList[k] && digitsList[j] != 0) 返回 false; } } 返回 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]; } 如果 (hasNoDuplicates(digitsList)) { 返回 true; } 返回 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]; } 如果 (hasNoDuplicates(digitsList)) { 返回 true; } 返回 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++; } } 如果 (hasNoDuplicates(digitsList)) { 返回 true; } 返回 false; }

public static boolean isConsistent(int[][] grid, int currentRow, int currentCol) { if (checkCurrentRow(grid, currentRow) && checkCurrentCol(grid, currentCol) && checkCurrentRegion(grid, currentRow, currentCol)) { return true; } return false; }

public static boolean solvePuzzle(int[][] grid, int[][] emptyCells, int numEmptyCells) { int i = 0; int j = 0; int currentCellDigit = grid[emptyCells[i][0]][emptyCells[i][1]]; while (j < numEmptyCells) { if (currentCellDigit != 9) { currentCellDigit++; grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit; if (isConsistent(grid, emptyCells[i][0], emptyCells[i][1])) { grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit; i++; j++; } else { grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit - 1; } } else { currentCellDigit = 0; currentCellDigit = grid[emptyCells[i][0]][emptyCells[i][1]]; i--; j--; if (j < 0) { return false; } } } 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; }

我目前看不出什么问题，但这似乎是一种过于复杂的方式，你为什么要采用蛮力法？ - Oliver
这是一项学校作业。我知道它过于复杂，但这是我们必须完成的方式。 - jesse
2
这个代码根本就无法编译。 - Sean Patrick Floyd
@SeanPatrickFloyd 我发现的主要问题是多了一个闭合括号。还有一个放错位置的 if...else，以及缺少了 displayDigits(int, int, int[][])。 - Kröw
3个回答
4

您的initializeGrid是有问题的。在我看来，它应该是这样的：

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

替代

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

编辑：以下是我的答案

它已经正确缩进（第一课），并相应地排列了花括号（第二课）。逐行理解您要做的事情，并在卡在特定行或方法调用时寻求帮助（第三课）。下面的代码将编译，但尚未解决难题。阅读并替换solvePuzzle中的注释（第四课）。进行一些思考和分析，因为这是您的家庭作业;) 祝你好运！

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!");
    }
  }
}

提示：如果您已经用正确的代码替换了上面的注释，则会执行回溯。

由于我只使用9x9的棋盘，所以'r'与'0'相比对初始化没有影响。算法的问题似乎出现在SOLVE方法中。 - jesse
1
非常感谢你的帮助。逐行执行确实有很大的帮助。 - jesse
0

在 solvePuzzle 中仔细思考你的代码。在 grid 和 currentCellDigit 之间有几个冗余的赋值。其中一个 i 和 j 是多余的，它们具有相同的值。

使用调试器来理解你的代码正在做什么。

更好的缩进将使你的代码更易读。

-2
public static boolean solvePuzzle(int[][] grid, int[][] emptyCells,
        int numEmptyCells) {
    int i = 0;
    int currentCellNum = 0;
    while (i < numEmptyCells) {
        currentCellNum = grid[emptyCells[i][0]][emptyCells[i][1]];
        if (currentCellNum != 9) {
            currentCellNum++;
            grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellNum;
            if (isConsistent(grid, emptyCells[i][0], emptyCells[i][1])) {
                i++;
            } 
        } else {
            currentCellNum = 0;
            grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellNum;
            i--;
            if (i < 0) {
                return false;
            }

        }
    }
    return true;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接