判断一个数独是否具有独特的解决方案 [英] Determine whether a Sudoku has a unique solution

问题描述

我挣扎了回溯算法来确定羯羊数独具有独特的解决方案，或者如果它有多个解决方案。这里的回溯code我使用：

I'm struggling with a backtracking algorithm to determine wether a Sudoku has a unique solution or if it has multiple Solutions. Here's the backtracking code i use:

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

第一种方法： 如果我更改

First approach: If i change

for (int val = 1; val <= 9; ++val) {
for (int val = 9; val >= 1; val--) {

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

i get two different solving-algorithmns which should find different solutions (if different solutions exist). The problem with this approach is, that the algorithm doesn't terminate even though its just a slight change and i don't know why.

第二条本办法： 复位原路返回，继续寻找解决的办法。如果我试试这个，这也不行。

Second approach: Reset to backtrack and continue searching for a solution. If i try this, it doesn't work either.

我试图找到一个Java的例子，但我只能找到像重置原路返回，继续寻找第二个解决办法的信息。

I tried to find a Java example, but i can only find information like "reset on backtrack and continue searching for a second solution".

可能有人请提供一个例子，如何改变算法，因此它告诉我，如果有多个解决方案存在（确切的数字是没有必要）

Could someone please provide a example how to change the algorithm so it tells me if multiple solutions exists (the exact number is not needed)

或

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

Could someone please explain to me why my first approach doesn't terminate?

谢谢！

推荐答案

如果您返回，而不是一个boolean一个数字，你可以在这里有0，1，涨幅超过1溶液（S）情况之间destinguish。

If you return a number instead of a boolean, you can destinguish between cases where there are 0, 1, or more than 1 solution(s).

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

这篇关于判断一个数独是否具有独特的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！