逻辑解算算法（适用于Java中的Sudoku）
我的逻辑解决算法有问题。 它很好地解决了大量提示的难题，它只有少于45条线索的难题。
这是解决问题的算法。 不可变是一个布尔值，决定了该值是否可以改变。 cell [row] [col] .possibleValues是名为SudokuCell的类中的LinkedList，它存储了该网格元素可能的值。 grid.sGrid是拼图的主要int [] []数组。 removeFromCells（）是一种从网格的行，列和象限中删除值的方法。 该代码将在下面提供。
第二个for循环仅用于检查单个解决方案。 我决定避免递归，因为我真的无法解决它。 目前这种方法似乎运行良好。
public boolean solve(){
for(int i = 0; i < 81; i++){
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
if(!immutable[row][col]){
if(cell[row][col].getSize() == 1){
int value = cell[row][col].possibleValues.get(0);
grid.sGrid[row][col] = value;
immutable[row][col] = true;
removeFromCells(row, col, value);
}
}
}
}
}
int i = 0;
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
if(grid.sGrid[row][col] == 0){
i++;
}
}
}
if(i != 0){
return false;
} else{
return true;
}
}
这是removeFromCells（）的代码
我认为大部分代码都是不言自明的。 第一个循环从（x，y）的行和列中移除值，第二个循环从象限移除该值。
public void removeFromCells(int x, int y, int value){
/*
* First thing to do, find the quadrant where cell[x][y] belong.
*/
int topLeftCornerRow = 3 * (x / 3) ;
int topLeftCornerCol = 3 * (y / 3) ;
/*
* Remove the values from each row and column including the one
* where the original value to be removed is.
*/
for(int i = 0; i < 9; i++){
cell[i][y].removeValue(value);
cell[x][i].removeValue(value);
}
for(int row = 0; row < 3; row++){
for(int col = 0; col < 3; col++){
cell[topLeftCornerRow + row][topLeftCornerCol + col].removeValue(value);
}
}
}
另一个问题点可能是构建可能值的地方。 这是我的方法：
第一个for循环创建新的SudokuCells以避免可怕的空指针异常。
sGrid中的任何空值都表示为0，因此for循环会跳过这些值。
SudokuBoard的构造函数调用这个方法，所以我知道它被调用。
public void constructBoard(){
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
cell[row][col] = new SudokuCell();
}
}
immutable = new boolean[9][9];
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
immutable[row][col] = false;
if(grid.sGrid[row][col] != 0){
removeFromCells(row, col, grid.sGrid[row][col]);
immutable[row][col] = true;
}
}
}
}
我会发布整个文件，但是那里有很多不必要的方法。 我发布了我认为会导致我的问题。
您似乎已经构建了一个基于现在解决的简单约束。 你需要一个完整的回溯，以便用较少的提示来解决难题。 有些情况下，如果没有回溯，你无法真正解决。
或者，您应该尝试实施Knuth的算法（跳舞链接）来解决这类问题。 理解和实现比回溯算法更复杂，但它的运行方式更好:)。 请参阅此处：http://en.wikipedia.org/wiki/Dancing_Links
这也是一个更普遍问题的算法，并且它被成功应用于解决数独问题。
在维基百科，有一篇文章的链接，详细介绍了使用约束编程可以解决什么类型的实例：http://4c.ucc.ie/~hsimonis/sudoku.pdf（可以在这里找到：http：//en.wikipedia .ORG /维基/ Sudoku_algorithms）。 表4非常有趣:)。
我用了很多这样的规则来开发我的数独求解器。 然而，我总是最终被迫使用回溯来寻找非常困难的数独。 根据维基百科，一些sudokus实际上不可能通过仅使用规则来解决。
我总共实施了6条规则。
我描述了整个算法，并在这两篇博文中给出了代码（最初的版本只使用前4条规则）。
http://www.byteauthor.com/2010/08/sudoku-solver/
http://www.byteauthor.com/2010/08/sudoku-solver-update/
PS。 我的算法专注于性能，因此它会自动平衡回溯与这些规则，即使它有时可以没有任何猜测。
链接地址: http://www.djcxy.com/p/96157.html