数独回溯算法（Java）-Java 学习之路

我已经创建了一个数独求解器，它可以解决数独作为人类的可能性 - 通过检查与被检查的方格相对应的方块中的可能值 .

但是，我想创建一个随机的Sudoku生成器（来自空白网格），因此决定使用回溯算法 . 我理解回溯的概念，但我对一件事感到困惑：

一旦我知道某个解决方案不被允许，我怎么知道返回（和更改）哪个先前节点？我应该简单地返回上一个节点并循环完成所有可能性吗？（然后，如果这不会产生正确答案，则返回之前的值，等等） . 这似乎是一种可行的方法，但效率也很低 . 这是实施回溯方法的正确方法还是有更好的方法去做？

提前致谢 .

关于回溯的更多信息可以在这里找到：http://en.wikipedia.org/wiki/Backtracking

3 回答

0

数独拼图可以简化为图形着色问题，可以使用简单的回溯来解决，例如将颜色分配给节点（1-9），直到没有违反所有直接连接的节点没有相同的颜色 .

Constructing Graph from Sudoku ： -

如果两个网格点位于同一行或列或方形中，则它们之间存在直接边缘 .

Backtracking ： -

将一种颜色（1-9）分配给节点检查是否没有其他具有相同颜色的直接连接节点如果有效颜色移动到下一个节点 . 否则改变颜色并重新检查 . 如果所有颜色都耗尽，则回溯到上一个节点 . 递归直到所有节点都是颜色 .

完成后，您可以随机开始从网格中删除数字，直到您认为如果删除了更多数字，问题无法解决 .

回复于 2024-04-23T16:00:49+08:00

生成随机数独的简单方法是
1）生成随机完成数独，即生成随机数独无方格为空 .
2）从1）的正方形中删除数字 .
3）解决2）的数独 . 如果有许多解决方案，则在2）处添加一个删除的数字 .
如果还有很多解决方案，那么重复3） .

1）示例源代码：

public int[][] generateRandomCompleteSudoku() {
  int[][] sudoku = new int[10];
  for(int i = 1; i <= 9; i++) {
    sudoku[i] = new int[10];
    Arrays.fill(sudoku[i], 0);
  }
  generateRandomCompleteSudoku(sudoku, 1, 1);
  return sudoku;
}
private boolean generateRandomCompleteSudoku(int[][] sudoku, int x, int y) {
  if(x > 9) {
    x = 1;
    y++;
  }
  //sudoku of the argument is completing sudoku.
  //so return true
  if(y > 9) {
    return true;
  }
  // enumerate the possible numbers of the pos(x,y). 
  List<Integer> possibleNumbers = new ArrayList<Integer>();
  for(int i = 1; i <= 9; i++) {
    boolean possible = true;
    //check i is a possible number.
    //check there isn't i in the raw of y .
    for(int j = 1; j <= x - 1; j++) {
      if(sudoku[j][y] == i) {
        possible = false;
        break;
      }
    }
    //check there isn't i in the column of x(omitted).
    //check there isn't i in the group of x,y(omitted).
    if(possible) {
      possibleNumbers.add(i);
    }
  }
  //sudoku is wrong so return false.(There is no solution of sudoku)
  if(possibleNumbers.size() <= 0) {
    return false;
  }
  Collections.shuffle(possibleNumbers);// This gives sudoku randomness.
  for(Integer possibleNumber : possibleNumbers) {
    sudoku[x][y] = possibleNumber;
    // a sudoku is generated, so return true
    if(generateRandomCompleteSudoku(sudoku, x + 1, y)) {
       return true;
    }
  }
  // No sudoku is generated, so return false
  return false;
}

回复于 2024-04-23T16:00:49+08:00

0
对于回溯解决方案，第一步是定义状态 . 所以对于这个问题，我认为最简单的方法是 (x,y, blank , num) ，其中 x , y 是当前状态的位置， blank 是剩下的空白位置数， num 是你想要填充该位置的值（从0到9和0表示空白） .

返回类型应该是boolean，它决定了移动是否有效（这意味着此移动有任何有效的解决方案） .

因此，状态转换是逐列，逐行：x，y到x，（y 1）或x，y到（x 1），0 . 同样，空白将来自 - > a - 1- > ... 0.我们在这里有一个解决方案：
```
public boolean move(int x, int y, int blank, int num, int[][]sudoku){
    sudoku[x][y] = num;
    //checking condition and return if x,y is the last position, code omitted
    if(y == sudoku[x].length){
            x++;
            y = 0;
    }else{
            y++;
    }
    for(int i = 1; i < 10; i++){
            if(move(x,y,blank,i,sudoku){//Backtrack here
                    return true;
            }
    }
    if(blank > 0){
            if(move(x,y,blank - 1, 0, sudoku){//Backtrack here
                    return true;
            }
    }
    return false;


}
```
因此，当从当前状态返回错误时，它将回溯到最后一个状态，并且最后一个状态将继续检查下一个 num ，直到找到正确的解决方案（或返回false） .
回复于 2024-04-23T16:00:49+08:00

数独回溯算法（Java）

3 回答

相关问题