Issues with recursive backtracking

Question

I am trying to implement a backtracking algorithm in Java, to solve a sudoku problem.

I'm 95% sure the problem is in solve method, but I included the two accesory methods in case.

Some of the strange-ish things I'm doing are just due to requirements/convenience, like the hard-coded initial values for the puzzle. I'm sure the issue lies near the bottom of my solve method, but I cannot figure it out...

My current problem is this: after working on the first row, and finding a potentially valid permutation of values, my program simply gives up. If I uncomment the line that prints "ROW IS DONE," it'll print that after ONE row, and no more output is given. Why is it giving up after the first row? Is there anything else about my implementation I should be worried about

EDIT: I made a lot of changes. It is getting very close. If I print when EXHAUST is true, I get a puzzle that has every row solved except the last one. It looks like it is undoing everything after it's solved/nearly solved it. I get the feeling that it might already reach point where the puzzle is fully solved, but I'm not passing back TRUE at the right time... What am I doing wrong now?

import java.util.ArrayList;

class Model
{
    ArrayList<View> views = new ArrayList<View>();
    int[][] grid = 
            {
              {5,3,0,0,7,0,0,0,0},
              {6,0,0,1,9,5,0,0,0},
              {0,9,8,0,0,0,0,6,0},
              {8,0,0,0,6,0,0,0,3},
              {4,0,0,8,0,3,0,0,1},
              {7,0,0,0,2,0,0,0,6},
              {0,6,0,0,0,0,2,8,0},
              {0,0,0,4,1,9,0,0,5},
              {0,0,0,0,8,0,0,7,9}
            };

    /**
     * Method solve
     * 
     * Uses a backtracking algorithm to solve the puzzle.
     */
    public boolean solve(int row, int col) //mutator
    {   
        if(exhaust(row,col)) {printGrid(); return true;}
        int rownext = row;
        int colnext = col+1;
        if(colnext>8)
        {
            colnext = 0;
            rownext++;
        }           
        if(grid[row][col] != 0) solve(rownext,colnext);
        else //is == 0
        {
            for(int num = 1; num <= 9; num++)
            {   
                if(!conflict(row,col,num)) //try a non-conflicting number   
                {
                    grid[row][col] = num;
                    if(solve(rownext,colnext)) return true;                     
                    grid[row][col] = 0;
                }
            }
        }
        return false;       

    }
    /**
     * Method exhaust
     * 
     * Iteratively searches the rest of the puzzle for empty space
     * using the parameters as the starting point.
     *
     * @return true if no 0's are found
     * @return false if a 0 is found
     */
    public boolean exhaust(int row, int col)
    {
        for(int i = row; i <= 8; i++)
        {
            for(int j = col; j <= 8; j++)
            {
                if(grid[i][j] == 0) return false;
            }
        }
        System.out.printf("Exhausted.\n");
        return true;
    }

    /**
     * Method conflict
     * 
     * Checks if the choice in question is valid by looking to see
     * if the choice has already been made in the same row or col,
     * or block. 
     *
     * @return true if there IS a conflict
     * @return false if there is NOT a conflict
     */
    public boolean conflict(int row, int col, int num)
    {
        for(int j = 0; j <= 8; j++)
        {
            if(grid[row][j] == num) {
                return true;
            }
        }   
        for(int i = 0; i <= 8; i++)
        {
            if(grid[i][col] == num) {
                return true;
            }
        }           

        int rowstart = 0;
        if(row>=3) rowstart = 3;
        if(row>=6) rowstart = 6;

        int colstart = 0;
        if(col>=3) colstart = 3;
        if(col>=6) colstart = 6;                    

        for(int r = rowstart; r <= (rowstart + 2); r++)
        {
            for(int c = colstart; c <= (colstart + 2); c++)
            {
                if(grid[r][c] == num) {
                    return true;
                }   
            }   
        }       
        return false;
    }
}

Answer 1

Imagine you're moving forward smoothly, row by row, and haven't backtracked. Your next position is solve(1,1);. Pay attention to rownext as you trace through your code. You should see the problem quickly. If you aren't backtracking, rownext should hold its value of at least 1.