数独回溯算法(Java)

Question

我已经创建了一个数独解算器，它将像人类一样解决数独-通过检查与被检查的方块对应的方块中的可能性+确定值。

(来源：http://pastebin.com/KVrXUDBF)

然而，我想创建一个随机数独生成器(从一个空白网格)，所以我决定使用回溯算法。我理解回溯的概念，但对一件事感到困惑：

一旦我知道某个解决方案是不允许的，我如何知道返回(和更改)前一个节点？我是否应该简单地返回到上一个节点并循环所有的可能性？(然后，如果没有得到正确的答案，则返回到之前的值，依此类推)。这似乎是一种可行的方法，但效率也很低。这是实现回溯方法的正确方法，还是有更好的方法呢？

提前谢谢。

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

Answer 1

数独难题可以归结为图着色问题，该问题可以通过简单的回溯来解决，比如给节点(1-9)分配颜色，直到没有违反所有直接连接的节点都没有相同的颜色。

基于数独的构建图：

如果两个网格点在同一行、同一列或同一正方形中，则它们之间有一条直接边。

回溯 :-

1. 将一种颜色(1-9)分配给节点
2. 检查是否没有其他具有相同颜色的直接连接节点
3. 是否有效颜色移动到下一个节点。否则，
4. 更改颜色并重新检查。

<代码>H117如果所有颜色耗尽，则回溯到上一个节点。<代码>H218<代码>H119进行递归，直到所有节点都着色。<代码>H220<代码>G221

一旦你完成了它，你可以开始随机地从网格中删除数字，直到你认为如果删除更多的数字这个问题是无法解决的。

Answer 2

生成随机数独的一种简单方法是

1)生成随机补全数独，即生成随机数独，无平方为空。

2)从1的平方中删除数字。

3)求解2)中的数独。如果有许多解决方案，则在2)处添加一个删除的数字。

If there are still many solutions, then repeat 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;
}

Answer 3

对于回溯解决方案，第一步是定义状态。所以对于这个问题，我认为最直接的方法是(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)。