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;
}
B
orC
, if you replace guesses with 0 when you backtrack. 2. You don't need tocheck
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. \$\endgroup\$ – JS1 Nov 15 '14 at 11:46