Computer Science‎ > ‎

C Program: Sudoku Solver



C Program source code to solve a Sudoku


/*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 sudoku
void 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 not
int column;
for(column=0;column<9;column++)
    if(sudoku[row][column]==num)
        return 0 ;//If the number is found already present at certain location we return zero
return 1;//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 not
int row;
for(row=0;row<9;row++)
    if(sudoku[row][column]==num)
        return 0;//If the number is found already present at certain location we return zero
return 1;//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)
            return 0;//If the number is found already present at certain location we return zero
return 1;//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 cell
if(column<8)
        solvesudoku(row,column+1);
    else
       solvesudoku(row+1,0);
}
void display()
{//The function to display the solved Sudoku
int 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 further
    else
    {
        int ctr;//This is a counter to check numbers from 1 to 9 whether the number can be filled in the cell or not
        for(ctr=1;ctr<=9;ctr++)
        {//We check row,column and the grid
        if((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.
    }
    
}
int main()
{
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 9
0 5 6 0 8 9 0 2 3
0 8 9 1 0 3 4 0 6
2 1 4 0 6 5 0 9 7
3 0 0 8 0 7 0 1 4
8 0 7 0 1 4 0 6 5
0 3 1 0 4 0 9 7 8
6 4 0 9 7 0 5 3 1
0 7 8 0 0 1 0 4 2
THE SOLVED SUDOKU
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2
*/








 















C Program to Reverse A String

C Program: Building an Expression Evaluator
C Program: Check for Armstrong Numbers
C Program: Check whether a string is a Palindrome or not
C Program: Common Operations on Sets - Union, Intersection, Difference, Cardinal Product
C Program: Computing exp(x), sin(x), cos(x), tan(x) using series expansions
C Program: Computing the Area of a Circle
C Program: Computing the Upper Triangular Matrix and Lower Triangular Matrix
C Program: Demonstrating File Handling Functions
C Program: Demonstrating Operations on Matrices - Addition, Subtraction, Multiplication, Inversion, Finding Determinants
C Program: Demonstrating the use of Bitwise Operators
C Program: Displaying a Histogram of word frequencies (unigram)
C Program: Distance Vector Routing Algorithm using Bellman Ford's Algorithm
C Program: Numerical Computing - The Gaussian Elimination Method
C Program: Numerical Computing - Implementing the Newton Raphson Method
C Program: Numerical Computing - the Bisection Method
C Program: Numerical Computing - The Gaussian Elimination Technique from Linear Algebra
C Program: Numerical Computing - the Jacobi Method
C Program: Printing the Pascal Triangle
C Program: Reversing the order of words in a sentence
C Program: Solving Simultaneous Equations in Two Variables
C Program: Source Code for computing the GCD(HFC) of two numbers
C Program: Source Code for Solving Quadratic Equations
C Program: Source code to solve the Josephus Problem
C Program: Sudoku Solver
C Program: The Usage of Command Line Arguments
C Program: Using the Sieve of Eratosthenes to print Prime Numbers