2
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
7
  • 1
    \$\begingroup\$ there are only two valid signatures for the function: main() (regardless of what visual studio will allow). They both have a return type of int \$\endgroup\$ – user3629249 Feb 21 '18 at 18:17
  • \$\begingroup\$ Please do not omit optional braces. Such omitting of optional braces makes the debugging of a program much more error prone \$\endgroup\$ – user3629249 Feb 21 '18 at 18:18
  • \$\begingroup\$ for ease of readability and understanding: 1) separate code blocks ( for if else while do...while switch case default ) via a single blank line. 2) separate functions be 2 or 3 blank lines (be consistent.) 3) follow the axiom: only one statement per line and (at most) one variable declaration per statement. 4) use meaningful variable names. Variable names should indicate content or usage (or better, both) 5) insert a (reasonable) space inside parens, after commas, after semicolons, around C operators \$\endgroup\$ – user3629249 Feb 21 '18 at 18:22
  • \$\begingroup\$ it is good programming practice to limit the 'scope' of variables as much as possible, So rather than: int i; and for( i=0; i<9; i++) it is better to write: for( int i=0; i<9; i++ ) which uses spacing for readability and limits the 'scope' of the variable to inside the for() code block. There are several places in the posted code where this 'limiting of scope' can be applied. \$\endgroup\$ – user3629249 Feb 21 '18 at 18:30
  • \$\begingroup\$ in function: checkSquare(), the local variable x is initialized to 1, then never modified. However, it is used as a return value. Much simpler (and just as clear) to eliminate that variable and replace return x; with return 1; \$\endgroup\$ – user3629249 Feb 21 '18 at 18:32
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ might be a good idea to demonstrate the code needed for 'recursion/backtracking' so the OP knows exactly what you are suggesting. \$\endgroup\$ – user3629249 Feb 21 '18 at 18:47
  • \$\begingroup\$ @user3629249 Done! \$\endgroup\$ – coderodde Feb 21 '18 at 19:15
  • \$\begingroup\$ I though that my solution is a backtrack algorithm without recursion? I wanted to do it recursive but I tho it would be much slower? Is the lower time worth the estethics? \$\endgroup\$ – BratZdenko Apr 4 '18 at 13:54
  • \$\begingroup\$ The backtracking algorithm I explained in Advice 2 can solve the hardest (known) sudoku on an average hardware in 36 milliseconds or so. The easy sudokus are solved on the same hardware in less than 10 milliseconds. Also, your code is really hard to follow: you should split the entire logic in manageable helper functions, each concentrating only one item of functionality. For example, you might have a function to check that the target digit can be set in a particular minisquare. \$\endgroup\$ – coderodde Apr 4 '18 at 15:58
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
-2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ If you want to add further information to an answer, please edit your existing answer instead of adding a new one, unless the second answer is complete and independet from the first. Please edit your first answer and then delete this one. \$\endgroup\$ – Raimund Krämer Feb 28 '18 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.