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

Я пытаюсь закодировать решатель судоку с рекурсией и возвратом. Но есть некоторые проблемы с моим кодом, он всегда возвращает false. Я попытался отладить, он вызывает метод next (int row, int col) до второй строки, шестого столбца, а затем останавливается и начинается обратное отслеживание. Проблема в том, что возврат продолжается до первой ячейки в моей игре судоку, а затем возвращается false. Он не заменяет номера ячеек другими.

вот мой код ... я что-нибудь пропустил?

/** Calls solve for the next cell */
private boolean next(int row, int col) {
    if (col < 8)
        return solve(row, col + 1);
    else
        return solve(row + 1, 0);
}

public boolean solve(int row, int col) {
    if (row > 8) {
        return true;
    }
    if (model[row][col] != 0) {
        if (isSafe(row, col, model[row][col]))
            return next(row, col);
    }
    for (int value = 1; value < 10; value++) {
        if (isSafe(row, col, value)) {
            model[row][col] = value;
            return next(row, col);
        }
    }
    return false;
}

java recursion backtracking
person Ama    schedule 20.08.2015    source источник
comment
вы нигде не сбрасываете значения, как вы могли когда-нибудь вернуться?   -  person BeyelerStudios    schedule 20.08.2015

Ответы (2)


arrow_upward
1
arrow_downward

Попробуйте добавить model[row][col] = 0; перед возвратом false;

person gyurix    schedule 20.08.2015
comment
Большое тебе спасибо! Это была одна из вещей, которую я упустил в своем коде. - person Ama; 20.08.2015

arrow_upward
1
arrow_downward 

return next(row, col);

должно быть

if (next(row, col)) {
    return true;
}

И if with == 0, похоже, не имеет смысла.

Готово

Непроверено, но с правильным обратным отслеживанием: снова установите для ячейки значение 0, чтобы ее можно было снова заполнить.

public boolean solve(int row, int col) {
    if (row > 8) {
        return true;
    }
    if (model[row][col] != 0) {
        // isSafe may be assumed on correct puzzles.
        return isSafe(row, col, model[row][col]))
            && next(row, col);
    }

    for (int value = 1; value < 10; value++) {
        if (isSafe(row, col, value)) {
            model[row][col] = value;
            if (next(row, col)) {
                return true;
            }
        }
    }
    model[row][col] = 0;
    return false;
}
person Joop Eggen    schedule 20.08.2015
comment
спасибо за комментарий ... У меня все еще та же проблема ... он все еще возвращает false ... Я изменил == 0 на! = 0 ... так как в программе есть вводимые пользователем данные для проверки слишком. - person Ama; 20.08.2015
comment
Большое спасибо! это было очень полезно, теперь мой код работает! - person Ama; 20.08.2015