Определите, имеет ли судоку единственное решение

Я борюсь с алгоритмом возврата, чтобы определить, имеет ли судоку уникальное решение или несколько решений. Вот код возврата, который я использую:

    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 <= 9; ++val) {
for (int val = 9; val >= 1; val--) {

я получаю два разных алгоритма решения, которые должны находить разные решения (если существуют разные решения). Проблема с этим подходом заключается в том, что алгоритм не завершается, хотя это всего лишь небольшое изменение, и я не знаю, почему.

Второй подход: сбросить, чтобы вернуться и продолжить поиск решения. Если я попробую это, это тоже не сработает.

Я пытался найти пример Java, но могу найти только такую ​​информацию, как «сбросить при возврате и продолжить поиск второго решения».

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

OR

Может кто-нибудь объяснить мне, почему мой первый подход не заканчивается?

Спасибо!


java algorithm backtracking sudoku
person user4758246    schedule 21.06.2014    source источник
comment
Что означает Legal()'? Я пытаюсь перевести этот код на C..   -  person Wizzardzz    schedule 09.09.2018
comment
Он возвращает true, если val разрешено в позиции i, j, и false, если такое же значение присутствует в соответствующей строке, столбце или сетке 3x3.   -  person user4758246    schedule 10.09.2018

Ответы (2)


arrow_upward
10
arrow_downward

Если вы возвращаете число вместо логического значения, вы можете различать случаи, когда существует 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;
}
person fabian    schedule 21.06.2014
comment
Зачем использовать байт? Вы ожидаете максимум 127 решений? Кроме того, AFAIK byte занимает ту же память, что и int, так что на самом деле разницы нет. - person kajacx; 21.06.2014
comment
@kajacx: ​​нужно найти только 2 решения, чтобы сказать, если решение уникально, так что почему бы и нет? - person fabian; 21.06.2014
comment
Но я нигде не вижу, чтобы было проверено количество решений, поэтому, если у судоку будет 256 решений, ваш метод вернет 0. - person kajacx; 21.06.2014
comment
@kajacx: ​​посмотрите на условие в цикле for. Вы думали, что я делаю DFS для всех решений? - person fabian; 21.06.2014
comment
@kajacx: ​​Кстати: даже int будет переполняться, если ни одно из полей не заполнено, поскольку существует более (9!)^3 > 2^55 решений (должно быть возможно независимое заполнение полей 3x3 по одной диагонали). - person fabian; 21.06.2014
comment
Спасибо, это именно то, что я пытался сделать. Я никогда раньше не использовал Backtracking, поэтому мне было довольно трудно понять и изменить алгоритм. - person user4758246; 21.06.2014
comment
Ааа, count < 2, извините, не заметил. Я имел в виду отсутствие пламени, я просто действительно не видел, как это будет работать. Тогда все в порядке. - person kajacx; 22.06.2014

arrow_upward
4
arrow_downward

Сброс должен быть внутри цикла 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
        }
    }
person CMPS    schedule 21.06.2014
comment
Спасибо, теперь алгоритм завершается, даже если цикл for ведет отсчет вниз, а не вверх. - person user4758246; 21.06.2014
comment
Оба ответа верны, к сожалению, я могу принять только один. - person user4758246; 21.06.2014
comment
@user3158988 user3158988 спасибо, вы должны проголосовать за правильный ответ :) Я только хотел знать, почему человек проголосовал за мой ответ. но надеюсь, что он/она напишет комментарий - person CMPS; 21.06.2014