Рекурсивное программирование на С#: переход на предыдущий шаг в коде
Мне дали задание написать программу судоку, которая решает пример судоку из Википедии. Метод решения головоломки судоку должен быть рекурсивным. Сначала он проверяет, действительна ли доска судоку (правила судоку: нет дважды встречающихся чисел в одной строке, столбце и поле), затем получает первое пустое поле, в которое он может записать, и записывает первое значение (число 1) в поле. После этого метод снова вызывает сам себя (рекурсия).
Мой метод выглядит так:
private bool SolveSudoku(int[,] board)
{
// if board not valid, return false
if (!CheckBoardValid(board))
{
return false;
}
// if board full, return true
var nextField = GetFirstEmpty(board);
if (nextField is null)
{
return true;
}
for (int value = 1; value < 10; value++)
{
board[nextField.Value.X, nextField.Value.Y] = value;
var solved = SolveSudoku(board);
// if solved, do nothing
// if not solved, undo this step and try writing next number (value++) in field
}
return false;
}
Как я могу отменить последний шаг, если он недействителен?
Я рекомендую проверить: youtube.com/watch?v=G_UYXzGuqvM
на мой взгляд, вы хотели бы записать текущую позицию перед вызовом доски [nextfield.value.x,...], а затем вернуться к этой позиции, а затем увеличить значение
Каково ваше представление о «пустом поле»? 0? -1?
0 представляет пустые поля в моем двумерном массиве 9x9 int[,] sudokuBoard();
Он начинается с 1 и проверяет, допустима ли 1 в этой позиции. Если оно допустимо, оно переходит к следующему пустому полю (0) и снова начинается с числа 1. Если оно неверно в этой позиции, значение должно увеличиваться на единицу с использованием рекурсии. На следующее свободное поле: он пробует 1, затем 2, 3... и если ни одно значение не является допустимым, метод должен вернуться на один шаг назад и изменить значение предыдущего свободного поля. Надеюсь доступно объяснил свою проблему.
Если вы посмотрите ссылку, опубликованную @ughStackExchange, она должна ответить на ваш вопрос. По сути, просто сбросьте board[nextField.Value.X, nextField.Value.Y] = 0 и продолжайте.
Ответы 1
Вырезаем соответствующую часть:
for (int value = 1; value < 10; value++)
{
board[nextField.Value.X, nextField.Value.Y] = value;
if (SolveSudoku(board)) return true;
// ^^ Stop if solved,
// iteration will increase value if not.
}
// reset and return false if no value for this field leads to a solution.
board[nextField.Value.X, nextField.Value.Y] = 0;
return false;
Запомнить предыдущее значение и установить его обратно?