[Backtracking]Sudoku Solver

1. Example

row : there exists only 1-9, no duplicate
column: there exists only 1-9, no duplicate
block : there exists only 1-9, no duplicate



2. Implementation

 // NOTE :empty already checked

 if ( board[m][n]== board[i][j] && (m!=i || n != j) ) return false;


// NOTE :empty already checked and cell present itself well

 if ( board[k][j] == board[i][j] && K!= i ) return false;
// NOTE: no way to below 0 and

 if ( j >= 9) return helper(board, i+1, 0);

// NOTE: make sure empty then try diff values

 if ( board[i][j] == '.') { 

     for (int v =1 ; v <= 9 ; v++) {

         board[i][j] = ((char) v+'0');

public void solveSudoku( char[][] board )
{
    

     //validate the input
     if ( board == null || board.length == 0 || board[0].length == 0) 
         return;


  
     helper(board, 0,0);
     


}
//private void helper(char[][] board, int i, int j)
private boolean helper(char[][] board, int i, int j)
{




     //validate the input
     //if (board == null || i< 0|| i>=board.length || j <0 data-blogger-escaped-j="">board[0].length)
     //   return;
     //if (j== board[0].length)
     //    i++;



     // NOTE: no way to below 0 and 
     if ( j >= 9)
         return helper(board, i+1, 0);
     if (i == board.length)
         return true;





     // NOTE: make sure empty then try diff values
     if ( board[i][j] == '.') 
     {
          for (int v =1 ; v <= 9 ; v++)
          {
        
              //if ( board[i][j] == '.' && isValid(board,i,j,v)  )
              // NOTE: board[][] should check first, otherwise we will lose a number to check
              //{      
                


                board[i][j] = ((char) v+'0');
                



                if ( isValid(board, i ,j)  )
                {
                   if (  helper(board, i, j+1) )
                      return true;
                }     



                //helper(board, i, j+1);
                board[i][j] = '.';




               //}
           }
     }
     else 
     {

        helper(board, i,j+1);
     }



     return false;


}
//private boolean isValid(char[][] board, int i , int j, int target)
// NOTE: board cell present its value, not the parameter target
private boolean isValid(char[][] board, int i, int j)
{



     // check row
     for (int k = 0 ; k < board[0].length; k++ )
     {
           //if (board[i][k]!='.'  && ((int)(board[i][k]-'0')) == target && k != j)
           // NOTE :empty already checked and cell present itself well
           if ( board[i][k] == board[i][j] && k!= j  )
                return false;
     }




     // check column
     for ( int k = 0 ; k < board.length; k++ )
     {
           //if (board[k][j] !='.' && ((int)(board[k][j] -'0')) == target && k!= i )
           // NOTE :empty already checked and cell present itself well
           if ( board[k][j] == board[i][j] && K!= i )
                return false;
     }




     // check block
     for (int m =( i/3 )*3; m < ( i/3 )*3 +3 ;m++ )
     {
        for (int n = (j/3)*3; n < (j/3)*3 + 3;n++ )
        {
            //if (board[m][n] != '.' && (int)(board[m][n]-'0') == target && m!= i && n != j)
            // NOTE :empty already checked and  cell present itself well
            if (  board[m][n]== board[i][j]  && (m!=i || n != j) )
                 return false;
        }
     }


     return true;


}

3. Similar Ones
Valid sudoku