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;
}

• user52292: Try this meta: How can I prepare my code so that I can paste it formatted? if you have problems with copy-pasting the code (especially tabs).
• JS1: 1. You don't need arrays B or C, if you replace guesses with 0 when you backtrack. 2. You don't need to check the whole matrix on every guess. You should only check whether your last guess was illegal. 3. When you encounter a filled in square, you should scan ahead to find the next unfilled square and recurse on that. There's no need to recurse on filled squares, because you don't do anything with them.

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.

• Almo: PUT SPACES AROUND OPERATORS very, very good tip. This is very important for legibility. I have yet to work somewhere that this was not part of the code standard.

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).

• Martijn: If you dislike goto sufficiently to want to avoid it here, you can add in a int knownbad = 0; and use it as an exit condition on each loop. The first would become for(i=0;knownbad == 0 && i<4; i++) for example. goto not_filled would become knownbad = 1;. It's a matter of taste and preference.
• user52292: I would rather use few (inline) functions with return if you don't like goto.