Sudoku Solver C Program

This program is written in C language. This program is for solving Sudoku. The algorithm used in this is Backtracking and the Datasturctures used in this program are 2-D array,Stacks,arrays.
So how does it work.
1. First it takes the input.
2. Then it looks for the first empty block, when it finds one it pushes all possible values for that block     in the Stack associated with the block. Then it pops the first entry and places it into the block, And     goto the next empty block.
3. And we repeat the step 2 and move on till we reach to the end or we find a block for which the no.     of possible values is zero. In the second case we goto the previous block that was empty and place       another value from the stack. If stack becomes empty we clear the block and goto previous block.
    And in this way the process continues till we reach to the end or all stacks become empty.
4. When the last block is filled then we terminate the program and print the solution.

Author : AAHO


#include<stdio.h>
int sudokumatrix[9][9]={0};
int top[81];
int stack[81][9];
void push(int s,int val)
{
    stack[s][++top[s]]=val;
}
int pop(int s)
{
    int aaho;
    aaho= stack[s][top[s]--];
    return aaho;
}
int sudoku(int x,int y)
{
    if(x<9&&y<9)                 // if( the block is in valid  range <= 81)
    {
        if(sudokumatrix[x][y]==0)          // if( block is empty)
        {
            all_possible_entries(x,y);       //find the valid values for the block and push them into the stack
            while(top[x*9+y]>-1)            //while( you have tried all valid values for the block)
            {
                sudokumatrix[x][y]=pop(x*9+y);                // pop a valid value from stack and fill the block
                if(sudoku(x+(y+1)/9,(y+1)%9))             // move to next block & check if( return value == 1)
                    return 1;                                                  // return 1  means sudoku has been solved
            }
            sudokumatrix[x][y]=0;                              // didn't get to the solution reset the value to empty
            return 0;                                                    // no success
        }
        return sudoku(x+(y+1)/9,(y+1)%9);         //if block is already filled move to next block and pass
    }                                                                    // - the return value whatever it is
    return 1;                                                     // filled all the blocks in the matrix  return success
}
void all_possible_entries(int x,int y)                  // block's coordinate in the sudoku
{
    int arr[10]={0};
    int i,j,bx,by;
    for(j=0;j<9;j++)                              // scan column of the block and record already present values
        arr[sudokumatrix[x][j]]=1;
    for(i=0;i<9;i++)                             // scan row of the block and record already present values
        arr[sudokumatrix[i][y]]=1;
    bx=x/3;                                         //starting row for the corresponding 3*3 matrix  
    by=y/3;                                         //starting column for the corresponding 3*3 matrix
    for(i=bx*3;i<(bx+1)*3;i++)        // scan the corresponding 3*3 matrix for already present values
        for(j=by*3;j<(by+1)*3;j++)
        arr[sudokumatrix[i][j]] = 1;
    for(i=1;i<10;i++)                        // push the values into the stack which are not present in
        if(arr[i]==0)                           // column, row and corresponding  3*3 matrix
        push(x*9+y,i);
}
int main()
{
    int i,j,x,y,n,value,c=0,flag,ch;
    while(1)
    {
    printf("Enter the Method of entering the Sudoku\n1. Matrix Form\n2. Available Value Form\n");
    scanf("%d",&ch);
    switch(ch)
    {
        case 1: {
                    printf("Enter the Sudoku in the matrix form replace blank with 0\n");
                    for(i=0;i<9;i++)
                        for(j=0;j<9;j++)
                        scanf("%d",&sudokumatrix[i][j]);
                }
                break;
        case 2: {
                    printf("enter the no. of values already known\n");
                    scanf("%d",&n);
                    printf("Enter the available value in following format row col value\n");
                    if(n>0)
                    for(i=0;i<n;i++)
                    {
                        in:
                        scanf("%d%d%d",&x,&y,&value);
                        if(value>9||value<1)
                        {
                            printf("Value is not valid.Enter a valid value");
                            goto in;
                        }
                        sudokumatrix[x-1][y-1]=value;
                    }

                }
    }

    for(i=0;i<81;i++)           //set all top of the stacks to -1
        top[i]=-1;
        printf("\n\n");
    if(sudoku(0,0))             // if(sudoku returns a success or 1)
    {
        printf("The solution is :\n");
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
                printf("%d ",sudokumatrix[i][j]);
            printf("\n");
        }
    }
    else
        printf("This Sudoku do not have any Solution.\n");
    Re:
    printf("What do you want to do\n1. Continue\n2. Clear and Continue\n3. Exit\n");
    scanf("%d",&ch);
    switch(ch)
    {
        case 1: printf("\n-------------------------------------------------\n");
                break;
        case 2: system("cls");
                break;
        case 3: exit(0);
        default : {printf("invalid entry"); goto Re;}
    }
    }
        return 0;
}