text: Sudoku | Backtracking |  ; N is the size of the 2D matrix N * N ; A utility function to print grid ; Checks 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 0 ; Check if we find the same num in the similar column , we return 0 ; Check if we find the same num in the particular 3 * 3 matrix , we return 0 ; 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 ) ; Check 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 assined 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
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE #define N  9 NEW_LINE void print ( int arr [ N ] [ N ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) printf ( " % d ▁ " , arr [ i ] [ j ] ) ; printf ( " STRNEWLINE " ) ; } } int isSafe ( int grid [ N ] [ N ] , int row , int col , int num ) { for ( int x = 0 ; x <= 8 ; x ++ ) if ( grid [ row ] [ x ] == num ) return 0 ; for ( int x = 0 ; x <= 8 ; x ++ ) if ( grid [ x ] [ col ] == num ) return 0 ; 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 0 ; return 1 ; } int solveSuduko ( int grid [ N ] [ N ] , int row , int col ) { if ( row == N - 1 && col == N ) return 1 ; if ( col == N ) { row ++ ; col = 0 ; } if ( grid [ row ] [ col ] > 0 ) return solveSuduko ( grid , row , col + 1 ) ; for ( int num = 1 ; num <= N ; num ++ ) { if ( isSafe ( grid , row , col , num ) == 1 ) { grid [ row ] [ col ] = num ; if ( solveSuduko ( grid , row , col + 1 ) == 1 ) return 1 ; } grid [ row ] [ col ] = 0 ; } return 0 ; } int main ( ) { int grid [ N ] [ N ] = { { 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 ) == 1 ) print ( grid ) ; else printf ( " No ▁ solution ▁ exists " ) ; return 0 ; }