3

注意：这个问题已经解决了，实际问题不在这个方法上，而是在另一个方法上，所以如果你在搜索数独的东西，最后进入这个页面，你绝对可以使用我下面的方法，它有效。

好吧，忘记所有用于解决数独的复杂算法。我正在用 Java 编写一个简单的求解器来解决简单的数独游戏。这种方法的思路很普遍，所以我想大家都已经知道了。我也很惊讶我无法完成它。

方法是遍历板上的每个单元格，并填写所有只有一种可能性的单元格。重复直到每个单元格都被填满。很简单，下面是我的代码，return int 可以做填充数：

public int solveGame() {

/*
 variable possible contains 10 elements, the first element is true if there 
 is one or more possible value to fill in, false otherwise. The remaining 
 elements (1-9) are whether true or false depending on their indexes 
 e.g. possible[3] is true if 3 is a possibility.
*/
boolean[] possible; 

int[] save;
int count;
int numresolve = 0;

while (!isFinished()) {

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            possible = new boolean[10];
            possible = getPossible(i,j);
            if (possible[0]) {
                count = 0;
                save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                }
            }
        }
    }
}

return numresolve;

}

我的代码的问题是它永远无法完成循环，因为在填充了所有有 1 种可能性的单元格后，剩余的单元格将有超过 1 种可能性，这是不可能完成循环的。

我知道我错过了一些我想不到的东西。

4

5 回答 5

3

要检测到您无法使用这种方法解决更多问题，请执行以下操作：

 while (!isFinished()) {
   int prevResolved = numresolve;

   .... // your loop

   if (numresolve == prevResolved) {
     // did not find anything - out of luck, can't solve this board.
     return ...; // numresolve or something to indicate that it failed
   }
}

如果您的算法在一个循环中根本没有找到任何东西，那么它并没有改变电路板 - 所以下一次它不会找到任何其他东西。

或者，只需false在循环顶部设置一个布尔值，并true在您对电路板进行更改时将其设置为。使用它来检测您的算法是否找到了某些东西（如果没有，则退出）。

于 2011-05-21T09:22:17.817 回答
3

除了无法检测到您无法解决难题之外，我认为此代码没有任何问题。您将能够解决的数独的难度显然取决于您对 getPossible 的实现，该实现未发布。
请记住，即使“非常简单”的数独也可能包含您必须同时分析多个单元格的部分，如果您不能在 getPossible 中执行此操作，您将无法解决很多问题：

考虑单元格 1 == {a, b}，单元格 2 = {a, b}，单元格 3 = {a, b, c}

单元 3 是可解的，这种情况很可能发生在您将在书中找到的最简单的数独中，等等。

您可能想要做的是在您的算法不再能够解决更多单元格之后查看电路板，然后找出使您的算法能够解决更多单元格的缺失逻辑是什么。

于 2011-05-21T10:06:23.960 回答
2

如果您填写一个单元格（通过调用setCell），您会减少同一行/列/块中所有其他单元格的可能性数量。检查您的例程是否getPossibile考虑了这些变化。

另请注意，使用您的简单策略无法解决某些难题。在某些情况下，每个打开的单元格都允许多个值，但总有一个唯一的解决方案。

于 2011-05-21T09:19:17.230 回答
2

您应该使用递归函数，只有当所有单元格都被填满时才会完成。

会发生没有单元格只有一种可能性的情况，因此您的代码应该通过再次调用函数本身来分叉两种（或更多）可能性中的每一种，直到网格完全填满。

于 2011-05-21T09:26:14.940 回答
1 
int numresolve = 0;

// this variable will be used to track # of changed cells in each loop
// init to -1 to run loop at least once
// loop can be more elegant if you put the condition at the end
int changed = -1;

// stop loop if no cell changed
while (!isFinished() && changed != 0) {

    // initialize # of changed cells in this loop    
    changed = 0;

    for (int i = 0; i < GAMESIZE; i++) {
        for (int j = 0; j < GAMESIZE; j++) {
            boolean[] possible = getPossible(i,j);
            if (possible[0]) {
                int count = 0;
                int[] save = new int[9];
                for (int k = 1; k < 10; k++) {
                    if (possible[k]) {
                        count++;
                        save[count] = k;
                    }
                }
                if (count == 1) {
                    setCell(i,j,save[count]);
                    numresolve++;
                    changed++;
                }
            }
        }
    }
}
于 2011-05-21T09:29:24.243 回答