确定数独是否具有唯一解决方案

我正在努力使用回溯算法来确定数独有一个独特的解决方案，或者它是否有多个解决方案。 这是我使用的回溯代码：

static boolean solve(int i, int j, int[][] cells) { if (i == 9) { i = 0; if (++j == 9) return true; } if (cells[i][j] != 0) // skip filled cells return solve(i+1,j,cells); for (int val = 1; val <= 9; ++val) { if (legal(i,j,val,cells)) { cells[i][j] = val; if (solve(i+1,j,cells)) return true; } } cells[i][j] = 0; // reset on backtrack return false; } 

第一种方法：如果我改变

 for (int val = 1; val = 1; val--) { 

我得到两个不同的求解算法，应该找到不同的解决方案（如果存在不同的解决方案）。 这种方法的问题是，算法不会终止，即使它只是稍微改变，我不知道为什么。

第二种方法：重置为回溯并继续搜索解决方案。 如果我试试这个，它也不起作用。

我试图找到一个Java示例，但我只能找到“重新启动回溯并继续搜索第二个解决方案”等信息。

有人可以提供一个如何更改算法的示例，以便它告诉我是否存在多个解决方案（不需要确切的数字）

要么

有人可以向我解释为什么我的第一种方法不会终止？

谢谢！

Answer 1

如果返回数字而不是布尔值，则可以区分存在0,1或1个以上解决方案的情况。

 // returns 0, 1 or more than 1 depending on whether 0, 1 or more than 1 solutions are found static byte solve(int i, int j, int[][] cells, byte count /*initailly called with 0*/) { if (i == 9) { i = 0; if (++j == 9) return 1+count; } if (cells[i][j] != 0) // skip filled cells return solve(i+1,j,cells, count); // search for 2 solutions instead of 1 // break, if 2 solutions are found for (int val = 1; val <= 9 && count < 2; ++val) { if (legal(i,j,val,cells)) { cells[i][j] = val; // add additional solutions count = solve(i+1,j,cells, count)); } } cells[i][j] = 0; // reset on backtrack return count; } 

Answer 2

复位必须在for循环内和if solve条件之后

  for (int val = 1; val <= 9; ++val) { if (legal(i,j,val,cells)) { cells[i][j] = val; if (solve(i+1,j,cells)) return true; cells[i][j] = 0; // reset on backtrack } }