Beginner's Sudoku solver in C

Question

I'm beginner programmer and I've challenged myself to write sudoku solver in C. I have finished it in few days and now I want to make it faster.

With this sample input execution time is 1.781 seconds (which includes loading of program, I'm using code:blocks in which time is automatically measured)

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

Here's the code:

 #include<stdio.h>

int sudoku[9][9]=
{
    0,0,0,0,0,4,0,0,0,
    0,6,8,0,0,0,5,0,0,
    0,2,0,0,0,0,0,7,6,
    6,0,0,0,0,0,8,9,0,
    0,0,5,2,6,0,0,0,0,
    0,0,0,9,0,0,1,0,0,
    0,0,0,0,0,7,0,5,0,
    0,4,0,0,0,0,0,0,1,
    0,0,0,0,5,1,4,0,0
};
int a[9][9]=
{
    0,0,0,0,0,4,0,0,0,
    0,6,8,0,0,0,5,0,0,
    0,2,0,0,0,0,0,7,6,
    6,0,0,0,0,0,8,9,0,
    0,0,5,2,6,0,0,0,0,
    0,0,0,9,0,0,1,0,0,
    0,0,0,0,0,7,0,5,0,
    0,4,0,0,0,0,0,0,1,
    0,0,0,0,5,1,4,0,0
};
//PRINT SUDOKU
void printSudoku()
{
    int i,j;
    for(i = 0; i < 9; i++) { if(i==3 || i==6) printf("\n");
        for(j = 0; j < 9; j++)    {
            printf("%d",sudoku[i][j]);
            printf(" ");
            if(j>7) printf("\n");
            if(j==2 || j==5) printf("  ");

        }
    }
    printf("\n");
}
//CHECK ROW
int checkRow(int num, int i)    {
    int j,x=1;
    for(j = 0; j < 9; j++)
        if(sudoku[i][j] == num)    return 0;

    return x;
}
//CHECK COLUMN
int checkCol(int num, int j) {
    int i,x=1;
    for(i = 0; i < 9; i++)
        if(sudoku[i][j]==num)    return 0;

    return x;
}

//CHECK SQUARE
int checkSquare(int num, int xj, int yi)
{
    int x=1;
    int i,j;
    for(i = yi; i < yi+3; i++)
        for(j = xj; j < xj+3; j++)
            if(sudoku[i][j]==num)    return 0;

    return x;
}
//MAIN PROGRAM
main()
{
    int i,j,num,row,col;
    int pi,pj,xj,yi,square;

    printSudoku();

    for(i = 0; i < 9; i++)
        for(j = 0; j < 9; j++) {
            if(sudoku[i][j]==0)    {
                num=1;

                do    {
                    if(num>9)    {
                        pi=i;
                        if(j == 0)  {
                            if(i!=0)    {
                                pj=8;
                                pi=i-1;
                            }
                        }
                        else    {
                            pj=j-1;
                        }
                        for(i = pi; i >= 0; i--)
                            for(j = pj; j >= 0; j--)    {
                                pj=8;

                                if(a[i][j]==0 && sudoku[i][j]==9)    {
                                    sudoku[i][j]=0;
                                }
                                else if(a[i][j]==0 && sudoku[i][j]<9)    {

                                    num=sudoku[i][j]+1;
                                    sudoku[i][j]=0;
                                    goto check;
                                }
                            }
                    }
                check:row=checkRow(num,i);
                    col=checkCol(num,j);
                    if(j<3)    xj=0;
                    if(j>2 && j<6) xj=3;
                    if(j>5) xj=6;
                    if(i<3)    yi=0;
                    if(i>2 && i<6) yi=3;
                    if(i>5) yi=6;
                    square=checkSquare(num,xj,yi);
                    if(row==1 && col==1 && square==1)
                        sudoku[i][j]=num;
                    else
                        num++;

                }
                while(row==0 || col==0 || square==0);
            }
        }

    printf("\n");
    printSudoku();

}

As I've said I'm a beginner programmer so sorry that my code is long and messy.

Does anyone know how can I make this faster?
Would it be faster if I used recursion?
And also how can I measure real execution time?

Answer 1

Advice 1

Instead of having checkRow, checkCol and checkSquare, I suggest you allocate a simple char array for each row, column and minisquare:

char visited[10];

You initialize each visited[0], ..., visited[9] to zero. Next, when you put a number in an empty cell, you mark it in three such "sets": current column, current row and current minisquare. This arrangement will bring the complexity of checking each row, column and minisquare from \$\Theta(d)\$ to \$\Theta(1)\$, where \$d\$ is the width/height of the input sudoku board.

Advice 2

What comes to the actual algorithm, I suggest you use recursion/backtracking. That will clean your code quite a bit, and will allow you better adapting it to, say, \$4 \times 4\$ or \$16 \times 16\$-sudokus.

The idea is as follows. You march through the board rows, each row from left to write. You leave the cells that have a predefined value as is, but you put 1 to the first empty cell, and recur to the next cell. If 1 does not belong, you try 2, 3 and so on. Once you have found a valid value, move to the next empty cell. At some point it might happen than none of the numbers fit. In such a case you go one step backwards (backtracking) and try increment the previous value. If you can translate from Java, see this, starting from line 163.

Answer 2

Faster will be to go first where you have less possibilities.

1. calculate for each empty cell what are the possible number you can put(check by line, bycolumn and by block)

   1.1 if only one number in an empty cell: you put it and update the table of possibilities and continue while you have only one possibility

2. if more than one in one cell you do recursion for all the possibilities sending a full copy of the sudoku modified

About the structure to use:

• Int [9][9] for the sudoku
• Boolean [9][9][9] for the possibilities
• Int [9][9] to count the possibilities: when you modify a cell you put 10 in the same cell of this table so it will never been chosen as any of the possibility
• And a number missing cells to know how many cells are left

So you can put all the number that has only one possibility. In the sudoku. When no more only 1 you recalculate... if no more one possibility you recurse on each possibility of one selected cell the one that has less possibilities.

While you can detect more accurately the possibilities. Less recursion and your program will be faster. If no recursion time is linear.

Answer 3

The boolean [9][9][9] is initially set all on true.

You have 2 in one cell so you put false into the line and column and block of [][][2]

When you check all the sudoku spots you fill the other table counting the true.

To traverse the sudoku array I would prefer 2 variables: one for the column and one for the block so the code will be more readable.