Решатель судоку с возвратом не всегда может обнаружить несколько решений - PullRequest
Новая
       56

Решатель судоку с возвратом не всегда может обнаружить несколько решений

0 голосов
/ 19 апреля 2020

Это код, который я написал, чтобы проверить, есть ли несколько решений головоломки KenKen (аналогично судоку). Технически это должно вернуть true, если есть 2 решения, но это, кажется, не работает из-за ошибки logi c в алгоритме.

Кажется, я не могу найти ошибку, и, потратив целый день на пошаговую отладку всего процесса, я чувствую, что никогда не пойму, в чем дело.

Код может решить головоломку без каких-либо проблем, но он не всегда обнаруживает наличие нескольких решений, что просто странно. 

    boolean solutionFlag = false;    

    static boolean backtrackingUniqueSolution(int startIndex) {
        for (int i=1; i<=sudokuGridElements.length; i++){
            sudokuGridCells[startIndex] = i;
            if(checkConditons()){
                if(endOfBounds || backtrackingUniqueSolution(startIndex + 1))){
                    if(!solutionFlag){ //Used to "count to 1"
                        solutionFlag = true;
                    } else {
                        return true; //Should return true only after it finds the second solution
                    }
                }
            }
            sudokuGridCells[startIndex] = null;
        }
        return false;
    }

1 Ответ

0 голосов
/ 19 апреля 2020

Когда вы находите первое решение, вы устанавливаете флаг, но возвращаете false, чтобы вы не знали, было ли решение найдено дальше по стеку рекурсии. Флаг говорит вам об этом, но вы все равно должны искать второе решение, чтобы получить ответ.

Вы должны различать guish между фактическим поиском решения, когда достигнута последняя ячейка, и сокращением рекурсии когда вы уже нашли второе решение. В первом случае выполните отсроченный отсчет с помощью флага. Во втором случае просто верните true, если было найдено второе решение, то есть когда рекурсивная функция вернула true. 

boolean solutionFlag = false;    

static boolean multiSolution(int startIndex) {

    for (int i = 1; i <= sudokuGridElements.length; i++) {
        sudokuGridCells[startIndex] = i;

        if(checkConditons()) {
            if (endOfBounds) {
                if (solutionFlag) return true;

                solutionFlag = true;
            } else {
                if (multiSolution(startIndex + 1)) return true;
            }
        }

        sudokuGridCells[startIndex] = null;
    }

    return false;
}

(Вы можете избавиться от нелокального флага состояния, если вы сделали функция возвращает целочисленное или перечисляемое значение, которое сообщает вам, были ли найдены одно или несколько решений.)

...