4x4 Sudoku solver performance

Question

The code is for a 4x4 Sudoku solver. It works fine when there are a small number of unfilled spaces (0's) but when I give the whole matrix input as 0's or so the solver takes a very long time. I need it to give only the first valid output, no need to calculate the rest of the outputs.

I input a matrix with values from 0 to 4. If they are from 1 to 4 then they are prefilled and they cannot be changed. But if the value is 0, then we can change and fill in any values from 1 to 4 so that once the Sudoku is filled validly we get the output else the program prints "No".

Matrix A contains the inputs. Matrix B contains either 1's or 0's. If the value is 0 at location x and y in matrix B, then that means that that value is not prefilled.

#include<stdio.h>
#include<stdlib.h>

void printd(int A[4][4])
{
  int i,j;
  for(i=0;i<4;i++)
  {
    for(j=0;j<4;j++)
    {
      printf("%d", A[i][j]);
    }
    printf("\n");
  }
  printf("\n");
  return;
}

int check(int A[4][4])
{
    int i,j,k,a,b,c,state=1,temp=1;
        for(i=0;i<4;i++)
        {
          for(j=0;j<4;j++)
          {
            if(A[i][j]==0)
              temp=2;
          }
        }
        if(temp==1)
        {
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            for(a=0;a<4;a++)
            {
                if(a!=i && A[i][j]==A[a][j])
                    state=0;
                if(a!=j && A[i][j]==A[i][a])
                    state=0;
                if(i<2 && j<2)
                {
                    for(b=0;b<2;b++)
                    {
                        for(c=0;c<2;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<2 && j<4)
                {
                    for(b=0;b<2;b++)
                    {
                        for(c=2;c<4;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<4 && j<2)
                {
                    for(b=2;b<4;b++)
                    {
                        for(c=0;c<2;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<4 && j<4)
                {
                    for(b=2;b<4;b++)
                    {
                        for(c=2;c<4;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
            }
        }
    }
    return state;
        }
        return 0;
}

int fill(int A[4][4],int B[4][4],int x,int y)
{
    int val,i,j,a,b,p;
    int C[4][4];
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            C[i][j]=A[i][j];
        }
    }
        val=check(A);
    if(val==1)
    {
        printf("Yes");
                printd(A);
        exit(0);
    }
    /*else if(val==0 && x==3 && y==3)
    {
        printf("N6o");
        return;
    }*/
    else if(x<4)
    {
                if(B[x][y]==0)
                {
                    for(p=1;p<5;p++)
                    {
                        C[x][y]=p;
                                                //printd(C);
                        //printf("%d %d %d\n", C[0][0], C[0][1], C[0][2]);
                        if(y<3)
                            fill(C,B,x,y+1);
                        else if(x<4)
                            fill(C,B,x+1,0);
                    }
                }
                                else
                                {
                                        if(y<3)
                                          fill(C,B,x,y+1);
                                        else if(x<4)
                                          fill(C,B,x+1,0);
                                }
    }
}

int main()
{
    int n,i,j,k,a,b,c,d;
    int A[4][4];
    int B[4][4]={0};
        //printd(B);
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d", &A[i][j]);
            if(A[i][j]!=0)
            {
                B[i][j]=1;      
            }
        }
    }
    fill(A,B,0,0);
    printf("No");
    return 0;
}

Answer 1

The formatting is messy:

• Many unexpectedly indented blocks and lines. Use indenting well to improve readability, by clearly identifying nested blocks of code.
• Put a space after commas in variable lists and parameter lists, for example:
  • Instead of int n,i,j,k,a,b,c,d prefer int n, i, j, k, a, b, c, d
  • Instead of fill(A,B,0,0) prefer fill(A, B, 0, 0)
• Put a space around operators, for example:
  • Instead of for(i=0;i<n;i++) prefer for(i = 0; i < n; i++)
  • Instead of if(A[i][j]!=0) prefer if (A[i][j] != 0)

The number 4 is magic in this code. It's everywhere. If you ever extend your implementation to a 5x5 matrix or other, you will have to replace that everywhere. It would be better to define a macro for this, for example:

#define DIM 4

Of course, some of the functions in the current implementation can't work with any other matrix. In those functions leave the number 4 as a reminder that you should improve the implementation to support arbitrary dimensions. In other functions that can work with any matrix (with some adjustments) such as main and fill, replace the number 4 with DIM.

Answer 2

...but when I give the whole matrix input as 0's or so the solver takes a very long time.

That is because your code is very brutal, you simply try every possibility, always check all the slots and continue the loops even when you already know the solution is bad:

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        if(A[i][j]==0)
            temp=2;
    }
}

The above loop can clearly be terminated inside the if:

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        if(A[i][j]==0)
        {
            temp=2;
            goto not_filled;
        }
    }
}
not_filled:

Similar opportunity for optimization with state:

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        for(a=0;a<4;a++)
        {
            if(a!=i && A[i][j]==A[a][j])
                state=0;

Looks like you can terminate the loop whenever you change state=0. goto is no bad, use it ;) (break cannot terminate all nested loops, goto can)

But that is only beginning, try thinking about the algorithm, can it be improved? What about checking the filled slot first (along with all sub-rows and sub-columns)? Try finding out all unnecessary computation you do and eliminate it (to speed it up).