数独回溯算法（Java）

Question

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

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

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

一旦我知道某个解决方案是不允许的，我如何知道要返回（和更改）哪个前一个节点？我应该简单地返回到前一个节点并循环浏览所有可能性吗？（然后如果这没有产生正确的答案，则返回到之前的值，等等。）这似乎是一种可行的方法，但效率也很低。这是实现回溯方法的正确方法吗？还是有更好的方法可以实现它？

提前感谢。

可以在此处找到有关回溯的更多信息：http://en.wikipedia.org/wiki/Backtracking

Answer 1

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

并且返回类型应该是布尔值，这决定了移动是否有效（这意味着此移动是否有任何有效的解决方案）。

因此，状态转换是逐列、逐行的：x，y到x，（y 1）或x，y到（x 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）。

Answer 2

生成随机数独的一种简单方法是，生成一个随机完成的数独，即生成随机数独，无方块为空
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;
}

Answer 3

数独难题可以归结为图着色问题，可以使用简单的回溯（如为节点（1-9）指定颜色）来解决，直到所有直接连接的节点没有相同的颜色为止。

从数独构造图形：-

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

回溯：-

1. 为节点指定一种颜色（1-9）
2. 检查是否没有其他颜色相同的直接连接节点
3. 如果颜色有效，请移动到下一个节点
4. 否则更改颜色并重新检查
5. 如果所有颜色耗尽，则返回到上一个节点
6. 执行递归，直到所有节点都是彩色的

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