SUDOKUSolver

package backtracking;

public class SudokuSolver {

    public static boolean estaNaLinha(int [] [] tab, int linha, int num){
       for(int coluna = 0; coluna < 9; coluna++)
           if(tab[linha][coluna] == num){
               return false;
           }
       return true;
    }

    public static boolean estaNaColuna(int [] [] tab, int coluna, int num){
        for(int linha = 0; linha < 9; linha++)
            if(tab[linha][coluna] == num){
                return false;
            }
        return true;
    }

    public static boolean estaNaMatriz(int [] [] tab, int linha, int coluna, int num){
        linha = (linha/3) * 3;
        coluna = (coluna/3) * 3;

        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(tab[linha + i][coluna + j] == num)
                    return false;
        return true;
    }

    public static boolean naoEhCandidato(int [] [] tab, int linha, int coluna, int num){
        return estaNaLinha(tab,linha,num) && estaNaColuna(tab,coluna,num) && estaNaMatriz(tab,linha,coluna,num);
    }



    public static boolean solveSudoku(int [] [] tab, int linha, int coluna){
        if(linha == 9){
            linha = 0;
            if(++coluna == 9){
                return true;
            }
        }

        else if (tab[linha][coluna] != 0)
           return solveSudoku(tab,linha + 1,coluna);


        for(int num = 1; num < 10; num++){
            if(naoEhCandidato(tab,linha,coluna,num)){
                tab[linha][coluna] = num;
                if(solveSudoku(tab, linha + 1, coluna))
                    return true;
                }
            }

        tab[linha][coluna] = 0;
        return false;
    }

    public static void imprime(int [] [] tab){
        for(int i = 0; i < 9; i++){
            System.out.println(" ");
            for(int j = 0; j < 9; j++)
                System.out.print(tab[i][j] + " ");
        }
    }

    public static void main (String [] args){
        int model [] [] = new int[9][9];

      model[0][0] = 9 ;
      model[0][4] = 2 ;
      model[0][6] = 7 ;
      model[0][7] = 5 ;

      model[1][0] = 6 ;
      model[1][4] = 5 ;
      model[1][7] = 4 ;

      model[2][1] = 2 ;
      model[2][3] = 4 ;
      model[2][7] = 1 ;

      model[3][0] = 2 ;
      model[3][2] = 8 ;

      model[4][1] = 7 ;
      model[4][3] = 5 ;
      model[4][5] = 9 ;
      model[4][7] = 6 ;

      model[5][6] = 4 ;
      model[5][8] = 1 ;

      model[6][1] = 1 ;
      model[6][5] = 5 ;
      model[6][7] = 8 ;

      model[7][1] = 9 ;
      model[7][4] = 7 ;
      model[7][8] = 4 ;

      model[8][1] = 8 ;
      model[8][2] = 2 ;
      model[8][4] = 4 ;
      model[8][8] = 6 ;

      imprime(model);

      System.out.println(" ");

      solveSudoku(model,0,0);

      imprime(model);

    }
}