Sudoku Solver C PROJECT

#include<stdio.h>
#include<stdbool.h>

// This below function responsible for checking is assumed input satisfying
// 3 conditions ?
bool IsValid(char board[9][9],int row, int col, char c)
{
    for(int i=0 ; i<9 ; i++)
    {
        // if any row contains the assumed number then return false
        if(board[row][i] == c)
        {
            return false;
        }
        // if any column contains the assumed number then return false
        if(board[i][col] == c)
        {
            return false;
        }
        // if any 3*3 grid or house[3*3] contains the assumed
        // number then we should return false
        if(board[3* (row/3) + i/3][3*(col/3) + i%3] == c)
        {
            return false;
        }
    }

    // if we comes to this part means assumed number obeying 3 conditions
    // and we can insert the same into the sudoku to check it more in further recursion calls
    return true;
}

// This is a recursilve function will be called until all cells will filled obeying 3 conditions
bool solve(char board[9][9])
{
    // visiting every cell in 9X9 matrix or two dimensional array by using two loops
    for(int i=0; i< 9 ; i++)
    {
        for(int j=0 ; j < 9 ; j ++)
        {

            // obviously we won't check if cell is filled with any number
            // Or in sudoku term hint is given
            if(board[i][j] == '.')
            {

                // here we are checking each number from 1..9
                // if any one of them satisfy we can pass true
                // and go to next recusion call
                for(char c='1' ; c<='9' ; c++)
                {

                    /* IsValid function check if assume number will satisfy
                        following three condition :-

                        1. All the rows should be filled with numbers(1 – 9) exactly once.

                        2. All the columns should be filled with numbers(1 – 9) exactly once.

                        3. Each 3×3 submatrix should be filled with numbers(1 – 9) exactly once.
                    */
                    if(IsValid(board,i,j,c) == true)
                    {
                        board[i][j] = c;

                        /* if we got true from IsValid fn that means current value is true
                           for provided hint in sudoku it may get wrong in further recursion calls

                           that's why we calling solve function recusilvely for next empty cell while checking
                           value previous filled cells
                        */
                        if(solve(board) == true)
                        {
                            return true;
                        }
                        /* If filled cell got true and then later found it is not suitable with other emply cells
                           than after coming by taking false from solve fn we'll re-empty the cell
                        */

                        else
                        {
                            board[i][j] = '.';
                        }
                    }
                }

                /* it means we have checked 1..9 and none of them is satifying
                   so we should discard previous accecpted cell and should try
                   another value
                */
                return false;
            }
        }
    }

    // We'll come here only when all empty cells are filled with the
    // their correct element
    return true;
}

// this the function main function will call
void SolveSudoku(char board[9][9])
{
    solve(board);
}

char board[9][9];

int main()
{

    freopen("tc2.txt", "r", stdin);
    freopen("otpt.txt", "w", stdout);

    // taking input from input file into 9X9 two dimensional array
    for(int i=0 ; i<9 ; i++)
    {
        for(int j=0 ; j<9 ; j++)
        {
            scanf(" %c",&board[i][j]);
        }
    }

    // this function does not return anything just fill the emty cells in the input
    SolveSudoku(board);

    // after sudoku is solved we print the answer
    for(int i=0 ; i<9 ; i++)
    {
        for(int j=0 ; j<9 ; j++)
        {
            printf("%c ",board[i][j]);
        }
        printf("\n");
    }

    return 0;
}


/*
Given a 9×9 incomplete sudoku, solve it such that it becomes valid sudoku. Valid sudoku has the following properties.

1. All the rows should be filled with numbers(1 – 9) exactly once.

2. All the columns should be filled with numbers(1 – 9) exactly once.

3. Each 3×3 submatrix should be filled with numbers(1 – 9) exactly once.
*/



tc1
9 5 7 . 1 3 . 8 4
4 8 3 . 5 7 1 . 6
. 1 2 . 4 9 5 3 7
1 7 . 3 . 4 9 . 2
5 . 4 9 7 . 3 6 .
3 . 9 5 . 8 7 . 1
8 4 5 7 9 . 6 1 3
. 9 1 . 3 6 . 7 5
7 . 6 1 8 5 4 . 9

ouput
9 5 7 6 1 3 2 8 4
4 8 3 2 5 7 1 9 6
6 1 2 8 4 9 5 3 7
1 7 8 3 6 4 9 5 2
5 2 4 9 7 1 3 6 8
3 6 9 5 2 8 7 4 1
8 4 5 7 9 2 6 1 3
2 9 1 4 3 6 8 7 5
7 3 6 1 8 5 4 2 9

tc2
5 3 .  . 7 .  . . .
6 . .  1 9 5  . . .
. 9 8  . . .  . 6 .
8 . .  . 6 .  . . 3
4 . .  8 . 3  . . 1
7 . .  . 2 .  . . 6
. 6 .  . . .  2 8 .
. . .  4 1 9  . . 5
. . .  . 8 .  . 7 9

output
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9