我创建了一个数独解算器，将解决数独由被检查对应于方形广场检查的可能性+限定值一个人可能─。
（来源： http://pastebin.com/KVrXUDBF ）
不过，我想创建一个随机数独发生器（从空的网格），所以决定用回溯算法。 我明白回溯的概念，但我感到困惑的一两件事：
我怎么知道它以前的节点返回到（和变化），一旦我知道了一定的解决方案是不允许的？ 我应该简单地返回到通过各种可能性的前一个节点和周期？ （然后，如果这会产生不正确的答案，才返回值等）。 这似乎是一个可行的方法，但也相当低效。 这是实现回溯方法的正确方式或是否有更好的方法去吗？
提前致谢。
更可以发现有关回溯这里： http://en.wikipedia.org/wiki/Backtracking
独益智能够减少曲线图，其可以使用简单的回溯等以节点（1-9）指定颜色，直到不存在冲突，所有直接相连的节点不具有相同的颜色来解决着色问题。
构建从数独图 ： -
还有，如果他们在同一行或列或直角两个格点之间的直接边缘。
回溯 ： -
- 分配一种颜色（1-9）到节点
- 检查是否有与同色系没有其他直接连接的节点
- 如果有效的色彩转移到下一个节点。
- 其他改变颜色，并重新检查。
- 如果所有的颜色用尽原路返回到前一个节点。
- 做递归直到所有节点的颜色。
一旦你用它做，你可以启动随机删除从网格数字，直到你觉得问题无法解决的是如果有更多的数字将被删除。
产生随机数独的简单方法是，
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;
}
用于回溯的解决方案，在第一步骤是定义的状态。 因此，对于这个问题，我觉得最直接的方法是(x,y, blank , num)与x , y是当前状态的位置， blank留为空白位置的号码， num是你想要的值填在该位置（从0到9和0表示空白）。
和返回类型应该是布尔值，它确定此举是否有效（这意味着是否有此举动的任何有效的解决方案）。
因此，状态转移是通过柱排列，由行：X，Y为x，（Y + 1）或X，Y到（x + 1），0。类似地，坯件将是从 - >一 - 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）。
