Причина, по которой я создаю эту новую тему вместо того, чтобы просто читать ответы на этот конкретный вопрос, которые были даны ранее, заключается в том, что я чувствую, что просто не до конца понимаю всю идею, лежащую в ее основе. Кажется, я не могу уяснить себе всю концепцию возврата. Поэтому мне нужно полностью понять возврат назад, а затем решить конкретную задачу судоку.
На данный момент я понимаю, что возврат назад — это метод возврата назад, например, в рекурсивном потоке, если обнаруживается, что решения, принятые до текущего состояния, привели в тупик. Итак, вы возвращаетесь, пробуете что-то еще и продолжаете снова.
Итак, в моем примере судоку я выбираю первую пустую ячейку и пытаюсь заполнить натуральное число из {1...9}, которое не противоречит хорошо известным правилам судоку. Теперь я делаю то же самое со следующей пустой ячейкой, пока не дойду до точки, в которой невозможно вставить допустимое число без конфликтов. Насколько я понимаю, это должен быть момент, когда в игру вступает возврат. Но как? Если я использую рекурсию, чтобы вернуться к последней записанной ячейке, алгоритм снова заполнит число, продолжит работу и застрянет в бесконечном цикле.
Поэтому я поискал в Интернете подсказки и обнаружил, что это довольно хорошо документированная и часто решаемая проблема. Тем не менее, многие решения утверждают, что используют возврат с возвратом. Я не понимаю, как и где они это делают, даже если у меня есть исходный код прямо передо мной.
Примеры: решатель судоку на Java, использующий возврат и рекурсию или http://www.heimetli.ch/ffh/simplifiedsudoku.html
Вот мой (не работающий) исходный код:
private boolean isSolvable( Sudoku sudoku, int row, int col ){
//if the method is called for a row > 8 the sudoku is solved
if(row > 8)
return true;
//calculate the next cell, jump one row if at last column
int[] nextCell = (col < 8) ? new int[]{row,col+1} : new int[]{row+1,0};
//check if the current cell isWritable() that is if it is not a given cell by the puzzle
//continue recursively with the next cell if not writable
if(!sudoku.isWritable(row, col))
isSolvable(sudoku, nextCell[0], nextCell[1]);
else{
//set the current cell to the lowest possible not conflicting number
for(int i=1; i< 10; i++){
if(!conflictAt(sudoku, row, col, i)){
sudoku.setValue(row, col, i);
//continue recursively with the next cell
isSolvable(sudoku, nextCell[0], nextCell[1]);
}
}
}
return false;
}
Теперь я не знаю, как продолжить. Как реализовать возврат или я уже это сделал? Это кажется глупым вопросом, но я действительно не вижу большего возврата в исходных кодах, упомянутых в ссылках выше.
РЕДАКТИРОВАТЬ: Окончательная (рабочая) версия:
private boolean isSolvable( Sudoku sudoku, int row, int col ){
//if the method is called for a row > 8 the Sudoku is solved
if(row > 8)
return true;
//if the cell is not writable, get the next writable cell recursively
if(!sudoku.isWritable(row,col))
return isSolvable(sudoku, (col
