Code For Sudoku:
Here is the code to solve Sudoku which i wrote in C
It's bit-lenghty but it can solve all difficulty levels
here is the input format to be given at the command prompt
--->./a.out
11 5
12 4
14 6
15 1
19 8
23 1
25 9
29 4
31 1
33 5
37 7
40 9
44 2
47 6
49 8
51 3
55 2
61 7
66 5
68 3
69 6
-1
0-80 is the grid numbers
the format should be [grid number(0-80) [1-9]
input should end with -1;
Here is the source code:
Code:
#include<stdio.h>
#include<stdlib.h>
int check,zcount;
int update(int pos);
int re_update(int pos);
struct str
{
int num;
int flag[10];
int group[20];
};
int count[81],once=0;
typedef struct str mynode;
mynode node[81];
///////////////////////////////////////////////
//////////////////////////////////////////////
int main()
{
int i,temp,temp_n[81],tcount=0,num,index;
int n[81];
for(i=0;i<81;i++)
n[i]=0;
printf("\n");
/*---------------------------Taking input------------------------------------*/
printf("\nEnter the index 0-80 and number 1-9\n");
printf("\nEnter -1 to solve the puzzle \n");
while(1)
{
scanf("%d",&index);
if(index==-1)
break;
scanf("%d",&num);
if(num>9||num<1||index>80||index<0)
{
printf("\n.......Invalid input.........\n");
continue;
}
else if(node[index].num!=0)
{
printf("\n.......Already filled........\n");
continue;
}
else
{
node[index].num=num;
update(index);
tcount++;
}
}
zcount=81-tcount;
printf("\n-------------------The number of filled places is %d------------------\n",tcount);
for(i=0;i<81;i++)
printf("%2d ",count[i]);
printf("\n");
tcount=0;
printf("\n\n");
printf("\n\n");
for(i=0;i<81;i++)
{
printf("%2d ",node[i].num);
if(node[i].num==0)
tcount++;
if((i+1)%3==0)
printf(" ");
if((i+1)%9==0)
printf("\n\n");
if((i+1)%27==0)
printf("\n");
}
printf("\n-------------------The number of unfilled places is %d------------------\n",tcount);
for(i=0;i<81;i++)
n[i]=node[i].num;
for(i=0;i<81;i++)
{
temp_n[i]=n[i];
temp=check_error(i,n);
if(temp==-1)
{
printf("\n\n");
printf("-------Puzzle cannot be solved -------- ");
printf("\n\n");
printf("-------Error at block %d -------- ",i);
printf("\n\n");
exit(0);
}
}
temp=0;
temp=sudoku();
if(temp==-1)
printf("\n Puzzle is not solved \n");
for(i=0;i<81;i++)
printf("%2d ",count[i]);
printf("\n");
printf("\n\n");
tcount =0;
for(i=0;i<81;i++)
{
printf("%d ",node[i].num);
if(node[i].num==0)
tcount++;
if((i+1)%3==0)
printf(" ");
if((i+1)%9==0)
printf("\n\n");
if((i+1)%27==0)
printf("\n");
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int sudoku()
{
int i,j,k,error=0,numb=8,flag=0,s_error=0,n[81],temp=0 ;
while(zcount!=0)
{
flag=1;
for(i=0;i<81;i++)
{
if(count[i]==numb&&node[i].num==0)
{
flag=0; //indicating that a node with required count is present in the loop;
for(j=1;j<10;j++)
if(node[i].flag[j]==0)
{
node[i].flag[j]=1;
node[i].num=j;
printf("\n<------Element %2d set to %d------->",i,j);
count[i]++;
zcount--;
error=update(i);
if(error==-1)
{
printf("\n---reupdating started");
re_update(i);
count[i]--;
zcount++;
node[i].flag[j]=0;
printf("\n---reupdating finished");
continue;
}
else
s_error=sudoku();
if(s_error==-1)
{
re_update(i);
count[i]--;
zcount++;
node[i].flag[j]=0;
continue;
}
//printf("\n----> zeroes-%2d",zcount);
printf("\n---Breaking");
break;
}
else
continue;
if(error==-1||s_error==-1)
return -1;
}
if(zcount==0)
break;
}
if(flag==1)
numb--;
}
/*
for(i=0;i<81;i++)
printf("%2d ",count[i]);
printf("\n");
*/
if(once==1)
{
for(i=0;i<81;i++)
n[i]=node[i].num;
for(i=0;i<81;i++)
{
temp=check_error(i,n);
if(temp==-1)
{
printf("\n\n");
printf("-------Puzzle wrongly solved -------- ");
printf("\n\n");
printf("-------Error at block %d -------- ",i);
printf("\n\n");
exit(0);
}
}
exit(0);
}
printf("\n\n");
printf("\n\n");
for(i=0;i<81;i++)
{
printf("%2d ",node[i].num);
if((i+1)%3==0)
printf(" ");
if((i+1)%9==0)
printf("\n\n");
if((i+1)%27==0)
printf("\n");
}
once=1;
return 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int check_error(int pos,int *block)
{
int m,n,index,t_num,flag=0,t_index,i,j;
i=pos/9;
j=pos%9;
index=i*9+j;
if(block[index]!=0)
{
t_num=block[index];
for(m=0;m<9;m++)
{
if(m!=i)
{
t_index=m*9+j;
if(block[t_index]==t_num)
flag=1;
}
if(m!=j)
{
t_index=9*i+m;
if(block[t_index]==t_num)
flag=1;
}
if(flag==1)
{
//printf("--------->Break at %d---pos=%d<-----------\n",m,pos);
return -1;
}
// row and column check completed;
}
/////////////1
for(m=i+1;m>=0;m++)
{
if(m%3==0)
break;
for(n=j+1;n>=0;n++)
{
if(n%3==0)
break;
t_index=9*m+n;
if(block[t_index]==t_num)
{
//printf("--------->Break at %d %d---pos=%d-------------->\n",m,n,pos);
return -1;
}
}
}
/////////2
for(m=i+1;m>=0;m++)
{
if(m%3==0)
break;
for(n=j-1;n>=0;n--)
{
if(n%3==2)
break;
t_index=9*m+n;
if(block[t_index]==t_num)
{
//printf("--------->Break at %d %d-------------->\n",m,n);
return -1;
}
}
}
///////////////3
for(m=i-1;m>=0;m--)
{
if(m%3==2)
break;
for(n=j-1;n>=0;n--)
{
if(n%3==2)
break;
t_index=9*m+n;
if(block[t_index]==t_num)
{
//printf("--------->Break at %d %d-------------->\n",m,n);
return -1;
}
}
}
//// 4
for(m=i-1;m>=0;m--)
{
if(m%3==2)
break;
for(n=j+1;n>=0;n++)
{
if(n%3==0)
break;
t_index=9*m+n;
if(block[t_index]==t_num)
{
//printf("--------->Break at %d %d-------------->\n",m,n);
return -1;
}
}
}
//end of num!=0 check;
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int update(int pos)
{
int m,n,index,t_num,flag=0,t_index,i,j,l,error=0;
i=pos/9;
j=pos%9;
index=i*9+j;
if(node[index].num!=0)
{
t_num=node[index].num;
for(m=0;m<9;m++)
{
if(m!=i)
{
t_index=m*9+j;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
if(m!=j)
{
t_index=9*i+m;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
// row and column check completed;
}
/////////////1
for(m=i+1;m>=0;m++)
{
if(m%3==0)
break;
for(n=j+1;n>=0;n++)
{
if(n%3==0)
break;
t_index=9*m+n;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
}
/////////2
for(m=i+1;m>=0;m++)
{
if(m%3==0)
break;
for(n=j-1;n>=0;n--)
{
if(n%3==2)
break;
t_index=9*m+n;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
}
///////////////3
for(m=i-1;m>=0;m--)
{
if(m%3==2)
break;
for(n=j-1;n>=0;n--)
{
if(n%3==2)
break;
t_index=9*m+n;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
}
//// 4
for(m=i-1;m>=0;m--)
{
if(m%3==2)
break;
for(n=j+1;n>=0;n++)
{
if(n%3==0)
break;
t_index=9*m+n;
if(node[t_index].flag[t_num]==0)
{
node[t_index].flag[t_num]=1;
count[t_index]++;
if(count[t_index]==9&&node[t_index].num==0)
error=-1;
for(l=0;l<20;l++)
if(node[index].group[l]==0)
{
if(t_index==0)
t_index=-1;
node[index].group[l]=t_index;
break;
}
else
continue;
}
}
}
//end of num!=0 check;
}
if(error==-1)
printf("\nError at --%d \n",pos);
return error;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int re_update(int pos)
{
int m,n,index,t_num,flag=0,t_index,i,j,l;
i=pos/9;
j=pos%9;
index=i*9+j;
if(node[index].num!=0)
{
t_num=node[index].num;
node[index].num=0;
for(l=0;l<20;l++)
{
if(node[index].group[l]==0)
break;
t_index=node[index].group[l];
if(t_index==-1)
t_index=0;
node[t_index].flag[t_num]=0;
count[t_index]--;
node[index].group[l]=0;
}
}
return 0;
}