Sudoku Solver in C without recursion

Question

I am trying to learn backtracing , so i wrote program for Sudoku It solves sudoku in approx. 1 ms in online c compiler

but this one sudoku puzzle is taking approx. 35 sec in that online c compiler with my code.

How to improvise the code , does recursion will help ? .If yes how ?(because recursion will also take same number of iterations as my code). I tried c codes available on google also (Sudoku Solver in C) with recursion , this one is taking approx. 7sec. to solve.

input:

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

code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define pass 1
#define fail 0
#define forward 1
#define backward 0
int flag = 0 ;
int a[9][9]  = {0} ;
int rulecheck_row(int row,int a[9][9])
{
    int i=0,j=0;
    for(i=0;i<9;i++)
        {
            for(j=i+1;j<9;j++)
                {
                    if((a[row][i] !=0) || ( a[row][j] !=0 ))
                    {
                                                
                    if(a[row][i] == a[row][j])
                    {
                        return fail;
                    }
                        
                    }
                }
        }
    
    return pass;
}

int rulecheck_column(int column,int a[9][9])
{
    int i=0,j=0;
    for(i=0;i<9;i++)
        {
            for(j=i+1;j<9;j++)
                {
                    if((a[i][column] !=0) || (a[j][column]))
                    {
                    if(a[i][column] == a[j][column])
                        return fail;
                    }
                }
        }
    return pass;
}



int duplicate_checker(int arr[9])
{
    int length = 9 ;
    for(int i = 0; i < length; i++) {    
        for(int j = i + 1; j < length; j++) {    
            if(arr[i]!=0 || arr[j]!=0)
            {
            if(arr[i] == arr[j])    
                return 1  ;
            }           
        }    
    }   
    return 0;
}
int repeat[3][3]={0};
int rulecheck_3x3matrix(int a[9][9])
{
    int b[9];
    int k=0;
    
     for(int loopr = 0 ; loopr < 3 ;loopr++)
    {
    
            for(int loop=0;loop<3;loop++)
            {
              
                for(int row=loopr*3;row<((loopr+1)*3);row++)
                {
                    for(int col=loop*3;col<((loop+1)*3);col++)
                    {
                         b[k++] = a[row][col] ;
                    }
                   
                }
                repeat[loopr][loop] = duplicate_checker(b);
                k=0;
                  
            }
    
    }
    for (int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(repeat[i][j] == 1)
                return fail;
        }
    }
    return pass;
    
}

int isPresentInBox(int i, int j, int num){
    int boxStartRow = i - i%3 ;
    int boxStartCol = j - j%3 ;

//check whether num is present in 3x3 box or not
   for (int row = 0; row < 3; row++)
   {
      for (int col = 0; col < 3; col++)
      {  
        if((row+boxStartRow) == i && (col+boxStartCol) ==j)
        {
        continue ;  
        }   
        if (a[row+boxStartRow][col+boxStartCol] == num)
            return fail;
        
      }
   }
   return pass;
}

int rulecheck_allelements()
{
    int i=0,j=0;
    // All elements should be b/w 0-9
    for( i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
                {
                    if(a[i][j] < 1 || a[i][j] > 9)
                        return fail ;
                }
        }
    return pass;
}

int main()
{
    int numofalreadyfilled = 0 ;
    int row[81],column[81] ;
    int flag_occupied = 0;
    int x = 0;
    int number = 0;
    int number_backup = 0;
    int direction = forward ;
    int flag_break_whileloop  = 0;
    clock_t start, end;
     double cpu_time_used;
     
    
    printf("Enter numbers with 0 for empty cells with space: \n");
    
    for(int l=0;l<9;l++)
    {
        for(int m=0;m<9;m++)
        {
            scanf("%d",&a[l][m]);
        }
    }
    
        printf("\n --- Entry finished ---\n");
         start = clock();
    
    
    for(int n=0;n<9;n++)
    {
        for(int o=0;o<9;o++)
        {
            if(a[n][o] >0 )
            {
                numofalreadyfilled++ ;
                row[x] = n;
                column[x] = o;
                x++ ;
            }
        }
    }
    printf("\nx:%d alrea : %d\n",x,numofalreadyfilled);
    printf("\n\n");
    for(int n=0;n<9;n++)
    {
        printf("\n");
        for(int o=0;o<9;o++)
        {
            printf("  %d ",a[n][o]); 
        }
    }
    for(int l=0;l<9;l++)
    {
        
            if(rulecheck_row(l,a) == fail)
            {
                printf("\n identical numbers in row\n");
                exit(0);
            }
            if(rulecheck_column(l,a) == fail)
            {
                printf("\n identical numbers in column\n");
                exit(0);
            }
        
    }
    if(rulecheck_3x3matrix(a) == fail)
    {
        printf("\n identical numbers in box\n");
                exit(0);
    }

    

    printf("\n");
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            for(int x=0;x<numofalreadyfilled;x++)
            {
                if((i == row[x]) && (j == column[x]))
                {
                    x = 0;
                    flag_occupied = 1;
                    break;
                }
            }
            if(flag_occupied == 1)
            {
                flag_occupied = 0 ;
                if(direction == forward)
                    continue ;
                else            //backtracking direction:backward
                {
                    j--;
                    j--;
                    if(j<-1 && i>0)
                        {
                            
                            i-- ;
                            j=7;
                        }
                    continue ;
                    
                }
            }
            
            if(direction == backward)
             {
                 a[i][j]++ ;
                  if(a[i][j]>9)
                     {
                         a[i][j] = 0;
                         j--;
                         j--;
                        if(j<-1 && i>0)
                        {
                            
                            i-- ;
                            j=7;
                        }
                     
                         continue ;
                     }
                        
                 
             }
             while(a[i][j] <= 9)
             {
                 
         if(a[i][j] == 0)
             {
                 a[i][j] = 1;
             }
             
                 if(rulecheck_row(i,a) & rulecheck_column(j,a) & isPresentInBox(i,j, a[i][j]))
                 {
                     direction = forward ;
                     flag_break_whileloop = 1;
                     break;
                 }
                 else
                 {
                     a[i][j]++ ;
                     if(a[i][j]>9)
                     {
                         a[i][j] = 0;
                         j--;
                         j--;
                        if(j<-1 && i>0)
                        {
                            
                            i-- ;
                            j=7;
                        }
                        direction = backward ;
                         flag_break_whileloop = 1;
                         break;
                     }
                 }
             }
             flag_break_whileloop = 0;
            //printf("---[%d][%d] num=%d \n",i,j,a[i][j]);
            if(j<-3)
            {
                printf("\n No Solution");
                exit(0);
            }
        }
    }
    
     for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
 //   printf("Hello World");
 

     end = clock();
     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\ntime : %lf",cpu_time_used);
    return 0;
}

Answer 1

Algorithmic Performance

There are a number of things you might do to improve the local performance of this code. But I think fundamentally the problem is that you are using a "brute force" approach, and that is inherently limited.

Your code basically identifies "empty" squares and treats those squares as a number. It increases the low digit whenever the number is not a valid solution, and increases digits that are found to be in conflict during generation (which is a smart heuristic that improves performance by a lot).

Ultimately, though, if you have 81 squares, and 10 pre-filled squares, you have 9^71 possible solutions to check. It's great if you can knock some of them out with rule checks, but you're still starting from a very large number. Half of the time, the solution will be in the top end of the range and you'll be in performance hell.

I suggest you change your approach entirely. Instead of enumerating every possible solution, try to actually solve the puzzle. By that, I mean apply the documented rules and generate the answer. The code for doing this is more complex (you have to track possible answers and what-not) but it should run much faster in the average case. (Obviously the dumb case will win in a scenario where the first thing it tries is correct. But you won't have those 35 second runs...)

Readability vs. Performance

Ignoring the algorithmic issues above, your code also is written to be readable in preference to performant. Writing a 9x9 nested loop for checking if a[i][j] meets whatever condition is clean, but not necessarily fast. Especially if you already know the answer but have thrown it away.

In scenarios where you are setting the value of a cell, why not go ahead and update other data structures? For example, keep a bitmask of values present in the row, column, and square for each cell. Use pointers to share a common value. Then you can check the 1 << digit bit of each bitmask against 0 to see if that digit is present already.

In a search situation, shared data and early pruning is very useful. You still need to balance computation against precalculation. It may be (you'll have to check this on your machine) that it's faster to compute indexes than to store pointers. (Cache lines and what-not) So you really should have a set of puzzles for testing that are both slow and fast, etc.

(As you add more and more complex data structures, you will want to write function(s) to manage your updates for you, to make sure you don't miss updating any of the values.)

Answer 2

Incidentally, I worked on exactly this problem during my vocational training. We were doing it in class, and most students came up with a solution comparable to yours. I added one extra step, and was suprised myself to find it increased performance up to a factor of approx. 20, depending on the distribution of prefilled fields.

Re-reading that old code, I can see that the algorithm I implemented was a bit difficult to understand, and can be reformulated without changing the basic idea of how to achieve performance gains.

Force early failures

Each empty field needs to pass three tests for being unique in its row, column and 3x3 box. The more prefilled fields there are in the relevant row/column/box, the less tests of filling the field with some number it will take until one fails, and the earlier you can backtrack within your recursion.

So, instead of progressing simply from top left to bottom right when filling in empty fields, fill those fields first where the least number of tests are needed:

1. Identify the most-filled box that still has empty fields.
2. Identify the empty field within that box with the most-filled row and column.
3. Test filling that empty field with a number.
4. If the test fails, repeat (3.) with another number. If the test passes, repeat (2.). If no test passes, backtrack one field and test another number.
5. If a box cannot be filled with all fields passing, backtrack one box, to its last-filled field and test another number. If the box can be filled, repeat (1.).

Equivalent solutions

My original algorithm did identify filled fields only once at the beginning, and then rewrote the Sudoku puzzle to an equivalent one that can be solved faster.

Sudoku puzzles can be rewritten in a different form without changing the solution. Divide the 9x9 field into 9 3x3 boxes in three rows and columns. You now can swap the three boxes in the first row with the three boxes in the second or the three boxes in the third row, and the solution within the box remains the same and valid. The same is true for columns. Also, you can use the same process to swap single 1x9 rows or 9x1 columns if you restrict the swapping to within row/column 1-3, 4-6 and 7-9, respectively.

You can rewrite your starting puzzle in a way that moves the already filled fields to the top left as far as the described equivalency rules allow. In other words, order boxes/rows/columns ascending by their number of empty fields. Then you can fill the empty fields from top left to bottom right, and still take advantage of finding wrong candidates early, as described above.

The last step after finding a solution is then to invert the swapping process.