Sudoku | Backtracking | Java program for above approach ; N is the size of the 2D matrix N * N ; A utility function to print grid ; Check whether it will be legal to assign num to the given row , col ; Check if we find the same num in the similar row , we return false ; Check if we find the same num in the similar column , we return false ; Check if we find the same num in the particular 3 * 3 matrix , we return false ; Takes a partially filled - in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution ( non - duplication across rows , columns , and boxes ) ; if we have reached the 8 th row and 9 th column ( 0 indexed matrix ) , we are returning true to avoid further backtracking ; Check if column value becomes 9 , we move to next row and column start from 0 ; Check if the current position of the grid already contains value > 0 , we iterate for next column ; Check if it is safe to place the num ( 1 - 9 ) in the given row , col -> we move to next column ; assigning the num in the current ( row , col ) position of the grid and assuming our assigned num in the position is correct ; Checking for next possibility with next column ; removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value ; Driver Code ; 0 means unassigned cells
public class Suduko { static int N = 9 ; static void print ( int [ ] [ ] grid ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) System . out . print ( grid [ i ] [ j ] + " ▁ " ) ; System . out . println ( ) ; } } static boolean isSafe ( int [ ] [ ] grid , int row , int col , int num ) { for ( int x = 0 ; x <= 8 ; x ++ ) if ( grid [ row ] [ x ] == num ) return false ; for ( int x = 0 ; x <= 8 ; x ++ ) if ( grid [ x ] [ col ] == num ) return false ; int startRow = row - row % 3 , startCol = col - col % 3 ; for ( int i = 0 ; i < 3 ; i ++ ) for ( int j = 0 ; j < 3 ; j ++ ) if ( grid [ i + startRow ] [ j + startCol ] == num ) return false ; return true ; } static boolean solveSuduko ( int grid [ ] [ ] , int row , int col ) { if ( row == N - 1 && col == N ) return true ; if ( col == N ) { row ++ ; col = 0 ; } if ( grid [ row ] [ col ] != 0 ) return solveSuduko ( grid , row , col + 1 ) ; for ( int num = 1 ; num < 10 ; num ++ ) { if ( isSafe ( grid , row , col , num ) ) { grid [ row ] [ col ] = num ; if ( solveSuduko ( grid , row , col + 1 ) ) return true ; } grid [ row ] [ col ] = 0 ; } return false ; } public static void main ( String [ ] args ) { int grid [ ] [ ] = { { 3 , 0 , 6 , 5 , 0 , 8 , 4 , 0 , 0 } , { 5 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } , { 0 , 8 , 7 , 0 , 0 , 0 , 0 , 3 , 1 } , { 0 , 0 , 3 , 0 , 1 , 0 , 0 , 8 , 0 } , { 9 , 0 , 0 , 8 , 6 , 3 , 0 , 0 , 5 } , { 0 , 5 , 0 , 0 , 9 , 0 , 6 , 0 , 0 } , { 1 , 3 , 0 , 0 , 0 , 0 , 2 , 5 , 0 } , { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 7 , 4 } , { 0 , 0 , 5 , 2 , 0 , 6 , 3 , 0 , 0 } } ; if ( solveSuduko ( grid , 0 , 0 ) ) print ( grid ) ; else System . out . println ( " No ▁ Solution ▁ exists " ) ; } }