/*The following program is an implementation of a Sudoku Solver in C.Sudoku is a 9*9 grid in which each row,each column and each 3*3 grid contains all numbers from 1 to 9 only once.The program uses backtracking approach to solve the sudoku. There is a recursive function to solve the sudoku.*/#include<stdio.h>int sudoku[9][9];//The array which stores entries for the sudokuvoid solvesudoku(int,int);int checkrow(int row,int num){//This function checks whether we can put the number(num) in the row(row) of the Sudoku or notint column;for(column=0;column<9;column++)if(sudoku[row][column]==num)return0;//If the number is found already present at certain location we return zeroreturn1;//If the number is not found anywhere we return 1}int checkcolumn(int column,int num){//This function checks whether we can put the number(num) in the column(column) of the Sudoku or notint row;for(row=0;row<9;row++)if(sudoku[row][column]==num)return0;//If the number is found already present at certain location we return zeroreturn1;//If the number is not found anywhere we return 1}int checkgrid(int row,int column,int num){//This function checks whether we can put the number(num) in the 3*3 grid or not//We get the starting row and column for the 3*3 grid
row=(row/3)*3;
column=(column/3)*3;int r,c;for(r=0;r<3;r++)for(c=0;c<3;c++)if(sudoku[row+r][column+c]==num)return0;//If the number is found already present at certain location we return zeroreturn1;//If the number is not found anywhere we return 1}void navigate(int row,int column){//Function to move to the next cell in case we have filled one cellif(column<8)
solvesudoku(row,column+1);else
solvesudoku(row+1,0);}void display(){//The function to display the solved Sudokuint row,column;printf("THE SOLVED SUDOKU \n");for(row=0;row<9;row++){for(column=0;column<9;column++)printf("%d",sudoku[row][column]);printf("\n");}
getch();}void solvesudoku(int row,int column){if(row>8)//If the row number is greater than 8 than we have filled all cells hence we have solved the sudoku
display();if(sudoku[row][column]!=0)
navigate(row,column);//If the value filled at a cell is not zero than it is filled with some value from 0 to 9 hence we move furtherelse{int ctr;//This is a counter to check numbers from 1 to 9 whether the number can be filled in the cell or notfor(ctr=1;ctr<=9;ctr++){//We check row,column and the gridif((checkrow(row,ctr)==1)&&(checkcolumn(column,ctr)==1)&&(checkgrid(row,column,ctr)==1)){
sudoku[row][column]=ctr;
navigate(row,column);}}
sudoku[row][column]=0;//No valid number was found so we clean up and return to the caller.}}intmain(){int row,column;printf("Enter the desired sudoku and enter 0 for unknown entries\n");for(row=0;row<9;row++)for(column=0;column<9;column++)scanf("%d",&sudoku[row][column]);
solvesudoku(0,0);//We start solving the sudoku.}/*A sample run of the program was carried out and the results were as follows:-1 0 3 4 0 0 7 0 90 5 6 0 8 9 0 2 30 8 9 1 0 3 4 0 62 1 4 0 6 5 0 9 73 0 0 8 0 7 0 1 48 0 7 0 1 4 0 6 50 3 1 0 4 0 9 7 86 4 0 9 7 0 5 3 10 7 8 0 0 1 0 4 2THE SOLVED SUDOKU1 2 3 4 5 6 7 8 94 5 6 7 8 9 1 2 37 8 9 1 2 3 4 5 62 1 4 3 6 5 8 9 73 6 5 8 9 7 2 1 48 9 7 2 1 4 3 6 55 3 1 6 4 2 9 7 86 4 2 9 7 8 5 3 19 7 8 5 3 1 6 4 2*/