Проблема с пониманием того, как рекурсия работает с этим решателем Sudoku

Question

Я рассматриваю этот блок кода часами и не могу понять, как это работает. Может кто-то, пожалуйста, дать подробное объяснение того, как рекурсия работает с этими функциями? Имейте в виду, что я очень новичок в программировании.

Часть, которая меня сбивает с толку, - как многократно разрешается решение()? Разве он не остановится после достижения головоломки [row] [col] = 0?

Это, кстати, рабочий код.

EDIT: Благодарим за ответ! Но я не вижу, где он возвращается.

void solve(int row, int col) throws Exception 
{ 
    if(row > 8) 
    { 
     throw new Exception("Solution found") ; 
    } 

    if(puzzle[row][col] != 0) 
    { 
     next(row, col); 
    } 
    else 
    { 
     for(int num = 1; num < 10; num++) 
     { 
      if(checkHorizontal(row,num) && checkVertical(col,num) && checkBox(row,col,num)) 
      { 
       puzzle[row][col] = num ; 
       next(row, col) ; 
      } 
     } 
     puzzle[row][col] = 0 ; 
    } 
} 

public void next(int row, int col) throws Exception 
{ 
     if(col < 8) 
     { 
      solve(row, col + 1) ; 
     } 
     else 
     { 
      solve(row + 1, 0) ; 
     } 

} 

Answer 1

next функция может быть описан как функция, которая находит первое свободное поле, и запускает процесс решения из этой области.

Фактическая рекурсия - это простой обратный отсчет (http://en.wikipedia.org/wiki/Backtracking). Общая схема может быть легче понять с каким-то псевдокодом:

Solution findSolution(Board board) { 
    if (board.isSolved()) return solutionFor(board); 


    // An "action" here refers to placing any number 
    // on any free field 
    for (each possible action) { 

     do the action // That is: place a number on a free field 

     // The recursion: 
     Solution solution = findSolution(board); 
     if (solution != null) return solution; 

     // No solution found 
     UNdo the action // That is: remove the number from the field 

     // Now the loop continues, and tries the 
     // next action... 
    } 

    // Tried all possible actions, none did lead to a solution 
    return null; 
} 

Обычно, можно было бы определить эти «действия» с двумя вложенными в обмен на петли:

for (each free field f) 
{ 
    for (each number n in 1..9) 
    { 
     place 'n' on 'f' 
     try to find solution 
     remove 'n' from 'f' 
    } 
} 

Внешний цикл в этом случае несколько «скрытый» в функции next.

В этом случае для судоку эта конкретная реализация обратного отслеживания может работать не очень хорошо. Это может занять несколько триллионов лет, пока не найдет решение, потому что есть так много возможностей. Но это в основном зависит от того, насколько «умны» методы check*. Важно быстро определить случаи, когда (частичное) решение уже недействительно. То есть, есть ли у вас ситуация, когда решение не может быть найдено в любом случае. Например, ситуация уже «недействительна», когда две ячейки одного из 3x3-sqares содержат одинаковое число. Этого можно избежать, например, путем явного хранения номеров, которые все еще доступны, но тогда код, конечно, станет более сложным.