Trouble understanding how recursion works with this Sudoku Solver

Question

I have been looking at this block of code for hours now and I can't figure out how it works. Can someone please give a detailed explanation for how recursion is working with these functions? Keep in mind I am very new at programming.

The part that is confusing me the most is how does solve() get repeatedly called? Wouldn't it just stop after it reaches puzzle[row][col] = 0?

This is working code by the way.

EDIT: Thank you for the answer! But I don't see where it is backtracking.

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

The next function can be described as a function that finds the first free field, and starts the solving process from this field.

The actual recursion is then a simple Backtracking ( http://en.wikipedia.org/wiki/Backtracking ). The general scheme may be easier to grasp with some pseudocode:

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;
 }

Usually, one would determine these "actions" with two nested for-loops:

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

The outer loop is in this case somewhat "hidden" in the next function.

In this case, for a sudoku, this particular implementation of the backtracking might not work very well. It might take a few trillion years until it finds a solution, because there are just so many possibilities. But this basically depends on how "clever" the check* methods are implemented. It's important to quickly detect the cases where a (partial) solution is already invalid. That is, whether you have a situation where no solution can be found anyhow. E.g., a situation is already "invalid" when two cells of one of the 3x3-sqares contain the same number. This could, for example, be avoided by explicitly storing the numbers that are still available, but then the code would become more complex, of course.