java - 简单数独解法

Question

---

Note: this problem has been solved, the actual problem is NOT in this method but the other, so if you're searching for something about Sudoku and finally get into this page, you can absolutely use my method below, it works.

---

好吧，忘掉所有用于解决数独的复杂算法。我正在用 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 种可能性，这是不可能完成循环的。

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

Answer 1

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

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

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

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