逻辑求解算法（适用于 Java 中的数独）

Logic Solving Algorithm (for Sudoku in Java)

提问by SkylineAddict

I'm having issues with my logic solving algorithm. It solves puzzles with a large number of hints very well, it just has issues with puzzles that have less than 45 clues.

我的逻辑求解算法有问题。它很好地解决了大量提示的谜题，它只是在少于 45 条线索的谜题中存在问题。

This is the algorithm for solving. Immutable is a boolean that determines whether or not that value can be changed. cell[row][col].possibleValues is a LinkedList within a class called SudokuCell that stores the values that are possible for that grid element. grid.sGrid is the main int[][] array of the puzzle. removeFromCells() is a method that removes values from the row, column, and quadrant of the grid. That code is provided further down.

这是求解的算法。Immutable 是一个布尔值，用于确定该值是否可以更改。cell[row][col].possibleValues 是名为 SudokuCell 的类中的 LinkedList，用于存储该网格元素的可能值。grid.sGrid 是拼图的主要 int[][] 数组。removeFromCells() 是一种从网格的行、列和象限中删除值的方法。该代码进一步提供。

The second for loop is just for checking for a single solution. I decided to avoid recursion because I really can't get my head around it. This method seems to be working well enough for now.

第二个 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;
    }
}

This is the code for removeFromCells()

这是 removeFromCells() 的代码

I think most of the code is pretty self-explanatory. The first for loop removes the value from the row and column of (x, y), and the second loop removes the value from the quadrant.

我认为大部分代码都是不言自明的。第一个 for 循环从 (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);
        }
    }
}

Another problem spot could be where the possible values are constructed. This is the method I have for that:

另一个问题点可能是构造可能值的位置。这是我的方法：

The first for loop creates new SudokuCells to avoid the dreaded null pointer exception.

第一个 for 循环创建新的数独细胞以避免可怕的空指针异常。

Any null values in sGrid are represented as 0, so the for loop skips those.

sGrid 中的任何空值都表示为 0，因此 for 循环会跳过这些值。

The constructor for SudokuBoard calls this method so I know it's being called.

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;
            }
        }
    }
}

I would post the entire file, but there are a lot of unnecessary methods in there. I posted what I think is causing my problems.

我会发布整个文件，但是里面有很多不必要的方法。我发布了我认为导致我的问题的内容。

回答by Mihai Toader

You seem to have built only a simple constraint based solved for now. You need a full backtracking one in order to solve puzzles with less hints. There are some cases that you can't really solve without backtracking.

您现在似乎只构建了一个基于已解决的简单约束。你需要一个完整的回溯，以便用更少的提示解决难题。有些情况如果不回溯就无法真正解决。

Alternatively you should try to implement Knuth's algorithm (Dancing Links) for solving this type of problems. It's more complicated to understand and implement than a backtracking algorithm but it's running way better :). See here: http://en.wikipedia.org/wiki/Dancing_Links

或者，您应该尝试实施 Knuth 算法（Dancing Links）来解决此类问题。它比回溯算法更难理解和实现，但它运行得更好:)。请参阅此处：http: //en.wikipedia.org/wiki/Dancing_Links

It's also an algorithm for a more general problem and it was applied to solving sudoku quite successfully.

它也是一种用于更一般问题的算法，并且非常成功地应用于解决数独问题。

On wikipedia there is a link to an article detailing what type of instances are possible to solve using constraints programming: http://4c.ucc.ie/~hsimonis/sudoku.pdf(found from here: http://en.wikipedia.org/wiki/Sudoku_algorithms). The Table 4 is really interesting :).

在维基百科上，有一篇文章的链接，详细说明使用约束编程可以解决什么类型的实例：http: //4c.ucc.ie/~hsimonis/sudoku.pdf（从这里找到：http://en.wikipedia .org/wiki/Sudoku_algorithms）。表 4 真的很有趣:)。

回答by Kevin Coulombe

I used many such rules to develop my sudoku solver. Yet I always ended up forced to use backtracking for very hard sudokus. According to wikipedia, some sudokus are effectively impossible to solve by using only rules.

我使用了许多这样的规则来开发我的数独求解器。然而，我总是被迫在非常困难的数独中使用回溯。根据维基百科，仅使用规则实际上无法解决一些数独。

I implemented a total of 6 rules.

我一共实施了6条规则。

1. No other value is allowed..
2. A certain value is allowed in no other square in the same section.
3. A certain value is allowed in no other square in the same row or column.
4. A certain value is allowed only on one column or row inside a section, thus we can eliminate this value from that row or column in the other sections.
5. Naked pairs
6. Lines

1. 不允许有其他值..
2. 同一部分的其他方格中不允许有某个值。
3. 同一行或同一列的其他方格中不允许有某个值。
4. 某个值只允许出现在一个部分内的一列或一行上，因此我们可以从其他部分的该行或列中消除这个值。
5. 裸对
6. 线

I described the whole algorithm and gave the code in these two blog posts (the initial version only used the first 4 rules).

我在这两篇博文中描述了整个算法并给出了代码（初始版本只使用了前4条规则）。

http://www.byteauthor.com/2010/08/sudoku-solver/

http://www.byteauthor.com/2010/08/sudoku-solver/

http://www.byteauthor.com/2010/08/sudoku-solver-update/

http://www.byteauthor.com/2010/08/sudoku-solver-update/

PS. My algorithm was geered towards performance so it automatically balances backtracking with these rules even though it could sometimes do without any guessing.

附注。我的算法以性能为导向，因此它会自动平衡回溯与这些规则，即使它有时可以不做任何猜测。