Skip to content

Instantly share code, notes, and snippets.

@ShaMan123

ShaMan123/kakuru.cpp

Last active March 11, 2021 09:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ShaMan123/9efa385ff6e88bc087407767b8903441 to your computer and use it in GitHub Desktop.
Save ShaMan123/9efa385ff6e88bc087407767b8903441 to your computer and use it in GitHub Desktop.
Download ZIP
Sudoku Solver (Kakuru needs work on CreateUnit with int creator)
Raw
kakuru.cpp
#include <stdio.h>#include<stdlib.h>#include<math.h>#define NUM 9#define DIM NUM
typedef struct
{
int comb[NUM], val;
} comb;
typedef struct
{
int CO[2][2], val, type, len, indx;
comb *solution;
comb temp;
} unit;
/*comb* Create(comb *solution,int len,int *pos){ int i,j,k,start,rep,rept[NUM][NUM]={0},max,z; for(i=0;i<len;i++) { for(j=1;j<=NUM;j++) { rep=Combin(j,i,len); //printf("level=%d head=%d rep = %d\n",i,j,rep); rept[i][j-1]=rep; } } for(j=1;j<=NUM;j++) *pos=*pos+rept[0][j-1];
(*pos)--; solution=(comb*)realloc(solution,(*pos+1)*sizeof(comb));
for(i=0;i<=*pos;i++) set(solution+i);
//------------------------------------------------------- for(k=0;k<len;k++) { start=0; max=NUM-k; do { for(i=max;i>0;i--) Fill(solution,&start,rept[k][i-1],i,k); max=(solution+start)->comb[k-1]-1; }while(start<=*pos); } z=CheckAll(solution,*pos); return solution;}comb* Trim(comb *d,int val,int len,int *pos){ int i,j,k=0; comb *temp; temp=(comb*)malloc(sizeof(comb)); for(i=0;i<=(*pos);i++) { if((d+i)->val==val) { temp[k].val=val; for(j=0;j<NUM;j++) temp[k].comb[j]=(d+i)->comb[j]; printf("found in loc %d\n",i); k++; temp=(comb*)realloc(temp,(k+1)*sizeof(comb)); } } *pos=k-1; return temp;}comb* Includes(comb *d,int numb,int len,int *pos,int includes){ int i,j,k=0,flag; comb *temp; temp=(comb*)malloc(sizeof(comb)); for(i=0;i<=(*pos);i++) { flag=1; for(j=0;j<len;j++) if((d+i)->comb[j]==numb) flag=0; if(flag==includes) { temp[k].val=(d+i)->val; for(j=0;j<NUM;j++) temp[k].comb[j]=(d+i)->comb[j]; printf("found in loc %d\n",i); k++; temp=(comb*)realloc(temp,(k+1)*sizeof(comb)); } } *pos=k-1; return temp;}*/
void PrintCombin(unit d)
{
int i, j;
for (i = 0; i <= d.indx; i++)
{
printf("%d. %d = ", i, d.val);
for (j = 0; j < d.len; j++)
printf("%d ", d.solution[i].comb[j]);
putchar('\n');
}
}
void PrintUnits(unit *d, int size)
{
int i;
for (i = 0; i < size; i++)
{
printf("\nUNIT %d\n", i);
printf("by index start [%d][%d] end [%d][%d]\n", (d + i)->CO[0][0], (d + i)->CO[0][1], (d + i)->CO[1][0], (d + i)->CO[1][1]);
printf("sum %d, type %d, len %d, indx %d\n", (d + i)->val, (d + i)->type, (d + i)->len, (d + i)->indx);
PrintCombin(*(d + i));
}
}
void PrintK(int mat[][DIM][DIM + 1])
{
int i, j, k, m = pow(DIM, 0.5), dig = 0, l, h = 1;
for (i = 0; i < NUM; i++)
{
for (j = 0; j < NUM; j++)
{
if (mat[i][j][0] == -2)
printf("- ");
else
printf("%d ", mat[i][j][0]); /*printf("mat{%d][%d] %d =",i,j,mat[i][j][0]); for(k=1;k<NUM+1;k++) printf("%d ",mat[i][j][k]); putchar('\n');*/
}
putchar('\n');
} /* do { dig++; l=DIM/pow(10,dig); } while(l!=0);
for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { for(k=1;k<=dig;k++) { l=mat[i][j][0]/pow(10,k); if(l==0) { h=k+1; h=dig-k; break; } } for(k=1;k<=h;k++) putchar(' '); if(mat[i][j][0]==-2) putchar('-'); else printf("%d ",mat[i][j][0]); } putchar('\n'); } putchar('\n'); */
}
void PrintInput(int mat[][DIM])
{
int i, j;
for (i = 0; i < NUM; i++)
{
for (j = 0; j < NUM; j++)
{
if (mat[i][j] == -2)
printf("- ");
else
printf("%d ", mat[i][j]);
}
putchar('\n');
}
putchar('\n');
}
int matVal(int mat[][DIM][DIM + 1], int i, int j, int val)
{
int k, c = 0;
for (k = 1; k < DIM + 1; k++)
{
if (mat[i][j][k] == 0)
c++;
}
if (c == DIM - 1)
return 0;
else if (c == DIM)
return -1;
else if (val > 0)
{
for (k = 1; k < DIM + 1; k++)
mat[i][j][k] = 0;
mat[i][j][0] = val;
mat[i][j][val] = 1;
return 1;
}
else
mat[i][j][0] = 0;
return 0;
}
void SetPlaneK(int mat3[][DIM][DIM + 1], int mat[][DIM], int k0)
{
int i, j, k;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
mat3[i][j][0] = mat[i][j];
if (mat[i][j] >= 0)
matVal(mat3, i, j, mat[i][j]);
for (k = k0; k < DIM + 1; k++)
mat3[i][j][k] = -1;
}
}
}
void SetMat(int mat[][DIM])
{
int i, j;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
mat[i][j] = -2;
}
}
void SetTemp(int mat[][DIM], int temp[][DIM])
{
int i, j;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
temp[i][j] = mat[i][j];
}
}
int Factorial(int val)
{
int i, x = 1;
for (i = 1; i <= val; i++)
{
x = x * i;
}
return x;
}
int MaxVal(int max, int len)
{
int i, x = 0;
for (i = 0; i < len; i++)
{
x = x + max - i;
}
return x;
}
int Combin(int head, int curlev, int levels)
{
int i, z = levels - curlev - 1;
i = Factorial(head - 1) / (Factorial(z) * Factorial(head - 1 - z));
if (head < 1 || head - z < 1 || head > NUM - curlev)
return 0;
return i;
}
int check(comb d)
{
int i, temp[NUM] = {0}, z;
for (i = 0; i < NUM; i++)
{
z = d.comb[i];
if (z > 0 && z <= NUM)
temp[z - 1] = temp[z - 1] + 1;
else if (z > NUM)
return -2;
}
for (i = 0; i < NUM; i++)
{
if (temp[i] > 1)
return -1;
}
return 0;
}
int CheckAll(comb *d, int pos)
{
int i, z, p = 0, *err;
err = (int *)malloc(sizeof(int));
for (i = 0; i <= pos; i++)
{
z = check(d[i]);
if (z == -1)
{
p++;
err = (int *)realloc(err, p * sizeof(int));
err[p - 1] = i;
}
}
if (p > 0)
{
printf("%d Errors found in possibilties:\n", p);
for (i = 0; i < p; i++)
printf("%d\n", err[i]);
} //else //printf("No errors found\n"); free(err); return p;}void set(comb *d){ int i; //d->comb=(int*)malloc(len*sizeof(int)); for(i=0;i<NUM;i++) d->comb[i]=0; d->val=0;}void Fill(comb *d,int *start,int rep,int i,int level){ int j; //for(i=NUM-1;i>=0;i--) { for(j=*start;j<*start+rep;j++) { //printf("i=%d start : %d \n",i,*start); (d+j)->comb[level]=i; (d+j)->val=(d+j)->val+i; //printf("fill : %d \n",(d+j)->comb[0]); } *start=*start+rep; } //return z;}int Update(int mat[][DIM][DIM+1]){ int i,j,k,val,c,m=pow(DIM,0.5),z=0,hold,error=-1;//-------- checks if mat[i][j] has one option and holds it in mat[i][j][0] for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { c=0; val=mat[i][j][0]; if (val!=-2) //number is not wall { for(k=1;k<DIM+1;k++) //checks certainty in plane k { if (mat[i][j][k]==0) c++; else hold=k; } if (c==DIM-1) { mat[i][j][0]=hold; mat[i][j][hold]=1; } else if (c==DIM) { return error; } } } } //printf("z = %d\n",z); for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { if(mat[i][j][0]==0) z++; c=0; for(k=1;k<DIM+1;k++) //checks certainty in plane k { if (mat[i][j][k]==0) c++; } if (c==DIM) { return -1; } /*else if (c==DIM-1) z++;*/ } } return z;}int Eleminate(int mat[][DIM][DIM+1]){ int i,j,val,row,col,z,start,end;//-------- deletes possibilities in plane k using elemination by row or col for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { val=mat[i][j][0]; if (val>0) { start=0; end=NUM-1; for(row=i;row<DIM;row++) { if(mat[row][j][0]==-2) { end=row-1; break; } } for(row=i;row>=0;row--) { if(mat[row][j][0]==-2) { start=row+1; break; } } for(row=start;row<=end;row++) { if (row!=i && mat[row][j][0]<=0 && mat[row][j][val]==-1) mat[row][j][val]=0; } start=0; end=NUM-1; for(col=j;col<DIM;col++) { if(mat[i][col][0]==-2) { end=col-1; break; } } for(col=j;col>=0;col--) { if(mat[i][col][0]==-2) { start=col+1; break; } } for(col=start;col<=end;col++) { if (col!=j && mat[i][col][0]<=0 && mat[i][col][val]==-1) mat[i][col][val]=0; } } } } z=Update(mat); return z;}void CreateSolution(unit *d){ int i,j,k,start,rep,rept[NUM][NUM]={0},max,z; for(i=0;i<d->len;i++) { for(j=1;j<=NUM;j++) { rep=Combin(j,i,d->len); //printf("level=%d head=%d rep = %d\n",i,j,rep); rept[i][j-1]=rep; } } for(j=1;j<=NUM;j++) d->indx=d->indx+rept[0][j-1];
(d->indx)--;
d->solution = (comb *)realloc(d->solution, (d->indx + 1) * sizeof(comb));
for (i = 0; i <= d->indx; i++)
set(d->solution + i);
//------------------------------------------------------- for(k=0;k<d->len;k++) { start=0; max=NUM-k; do { for(i=max;i>0;i--) Fill(d->solution,&start,rept[k][i-1],i,k); max=(d->solution+start)->comb[k-1]-1; }while(start<=d->indx); } z=CheckAll(d->solution,d->indx); //return d.solution;}comb* TrimUnit(unit *d){ int i,j,k=0; comb *temp; temp=(comb*)malloc(sizeof(comb)); for(i=0;i<=d->indx;i++) { if(d->solution[i].val==d->val) { temp[k].val=d->val; for(j=0;j<NUM;j++) temp[k].comb[j]=d->solution[i].comb[j]; //printf("found in loc %d\n",i); k++; temp=(comb*)realloc(temp,(k+1)*sizeof(comb)); } } d->indx=k-1; //d->solution=temp; //free(temp); return temp;}comb* IncludesUnit(unit *d,int numb,int includes){ int i,j,k=0,flag; comb *temp; temp=(comb*)malloc(sizeof(comb)); for(i=0;i<=(d->indx);i++) { flag=1; for(j=0;j<d->len;j++) if(d->solution[i].comb[j]==numb) flag=0; if(flag==includes) { temp[k].val=d->solution->val; for(j=0;j<NUM;j++) temp[k].comb[j]=d->solution[i].comb[j]; //printf("found in loc %d\n",i); k++; temp=(comb*)realloc(temp,(k+1)*sizeof(comb)); } } d->indx=k-1; return temp;}void Unit_Mat(unit *d,int mat3[][DIM][DIM+1]){ //in d->solution checks if a possibility doesn't exist and updates mat3 int i,j,k,z,opt[NUM]={0}; for(i=0;i<=d->indx;i++) { for(j=0;j<d->len;j++) { z=d->solution[i].comb[j]; opt[z-1]=1; } } for(k=0;k<NUM;k++) { if(opt[k]==0) { for(i=d->CO[0][0];i<=d->CO[1][0];i++) { for(j=d->CO[0][1];j<=d->CO[1][1];j++) mat3[i][j][k+1]=0; } } } Update(mat3);}void Mat_Unit(unit *d,int mat3[][DIM][DIM+1]){ //checks plane k in mat3 and eleminates possibilities in d->solution int i,j,k,z,opt[NUM]={0},valid[NUM]={0}; for(k=1;k<NUM+1;k++) { for(i=d->CO[0][0];i<=d->CO[1][0];i++) { for(j=d->CO[0][1];j<=d->CO[1][1];j++) { if(mat3[i][j][k]!=0) opt[k-1]=1; if(mat3[i][j][k]==1) valid[k-1]=1; } } } /*for(k=0;k<NUM;k++) printf("opt[%d]=%d\n",k,opt[k]); for(k=0;k<NUM;k++) printf("valid[%d]=%d\n",k,valid[k]);*/ for(k=1;k<NUM+1;k++) { if(opt[k-1]==0) d->solution=IncludesUnit(d,k,1); if(valid[k-1]==1) d->solution=IncludesUnit(d,k,0); }}int readN(int flag,int min){ int n; switch(flag) { case 0: printf("insert row\n"); do { scanf("%d",&n); if(n<min || n>NUM) printf("invalid row number. re-insert row\n"); } while(n<min || n>NUM); break; case 1: printf("insert column\n"); do { scanf("%d",&n); if(n<min || n>NUM) printf("invalid column number. re-insert column\n"); } while(n<min || n>NUM); break; } return n-1;}int UnitCO(unit *d,int mat[][DIM],int manual){ int i,flag,start,end; do { flag=0; if(manual==0) { flushall(); printf("insert start co-ordinates\n"); d->CO[0][0]=readN(0,0); d->CO[0][1]=readN(1,0);
printf("insert end co-ordinates, column only\n"); //d->CO[1][0]=readN(0,d->CO[0][0]+1); d->CO[1][0]=d->CO[0][0]; d->CO[1][1]=readN(1,d->CO[0][1]+1);
start = d->CO[0][1] - 1;
if (start == -1)
start = 0;
end = d->CO[1][1] + 1;
if (end > NUM)
end = NUM;
for (i = start; i <= end; i++)
{
if (mat[d->CO[0][0]][i] >= 0)
flag = 1;
}
}
d->type = -1;
if (d->CO[0][0] == d->CO[1][0] && d->CO[0][1] == d->CO[1][1])
{
d->type = 2;
d->len = 1;
d->indx = 0;
}
else if (d->CO[0][0] == d->CO[1][0] && d->CO[0][1] != d->CO[1][1])
{
d->type = 0;
d->len = d->CO[1][1] - d->CO[0][1] + 1;
}
else if (d->CO[0][0] != d->CO[1][0] && d->CO[0][1] == d->CO[1][1])
{
d->type = 1;
d->len = d->CO[1][0] - d->CO[0][0] + 1;
}
if (d->type == -1 || flag == 1)
printf("invalid co-ordinates\n");
}
while (d->type == -1 || flag == 1)
;
if (d->type == 1)
{
printf("\ncolumn co-ordinates, [row][column]:\n");
printf("[%d][%d]\n", d->CO[0][0] + 1, d->CO[0][1] + 1);
printf("[%d][%d]\n", d->CO[1][0] + 1, d->CO[1][1] + 1);
}
else if (d->type == 2)
{
if (mat[d->CO[0][0]][d->CO[0][1]] < 0)
mat[d->CO[0][0]][d->CO[0][1]] = 0;
return -1;
}
return 0; /* if(d->type==0) { mat[d->CO[0][0]][d->CO[0][1]-1]=-2; mat[d->CO[0][0]][d->CO[0][1]+d->len]=-2; } else if(d->type==1) { mat[d->CO[0][0]-1][d->CO[0][1]]=-2; mat[d->CO[0][0]+d->len][d->CO[0][1]]=-2; }*/
}
int UnitSum(unit *d, int creator)
{
int min, max;
if (creator == 1 || creator == 3)
{
d->val = -1;
return 0;
}
min = MaxVal(d->len, d->len);
max = MaxVal(NUM, d->len);
do
{
printf("insert sum between %d and %d\n", min, max);
scanf("%d", &d->val);
} while (d->val < min || d->val > max);
return 1;
}
int UnitCombin(unit *d, int mat3[][DIM][DIM + 1], int mat[][DIM], int flag, int creator)
{
int i, z;
if (creator == 2 || creator == 3)
{
for (i = 0; i < d->len; i++)
d->temp.comb[i] = 0;
}
else
{ //printf("UnitCombin flag %d\n",flag); if(flag==0) { printf("insert %d given members of combination by order\n",d->len); if(d->type==0) { do { flushall(); for(i=0;i<d->len;i++) scanf("%d",&d->temp.comb[i]); //d->temp.comb[i]=0; z=check(d->temp); if(creator==1) z=0; if(z<0) printf("invalid combination. re-insert %d given members of combination by order\n",d->len); }while(z<0); flushall(); } else if(d->type==2) { do scanf("%d",&z); while(z<0 || z>NUM); d->temp.comb[0]=z; d->val=z; } } } for(i=0;i<d->len;i++) { if(d->type==0 || (d->type==2 && flag==0)) { mat[d->CO[0][0]][d->CO[0][1]+i]=d->temp.comb[i]; //printf("updating mat[%d][%d] with temp valus is %d\n",d->CO[0][0],d->CO[0][1]+i,d->temp.comb[i]); matVal(mat3,d->CO[0][0],d->CO[0][1]+i,d->temp.comb[i]); } else if(d->type==1) { d->temp.comb[i]=mat[d->CO[0][0]+i][d->CO[0][1]]; //printf("temp= %d is mat[%d][%d]= %d\n",d->temp.comb[i],d->CO[0][0]+i,d->CO[0][1],mat[d->CO[0][0]+i][d->CO[0][1]]); /*if(d->temp.comb[i]>0) matVal(mat3,d->CO[0][0]+i,d->CO[0][1],d->temp.comb[i]);*/ } } return 1;}int ReadUnit(unit *d,int mat3[][DIM][DIM+1],int mat[][DIM],int manual,int redo,int creator){ int i,z=0,p; d->solution=(comb*)malloc(sizeof(comb)); d->indx=0; switch(redo) { case 0: z=UnitCO(d,mat,manual); if(z!=-1) p=UnitSum(d,creator); p=UnitCombin(d,mat3,mat,manual,creator); break; case 1: printf("invalid sum\n"); p=UnitSum(d,creator); p=UnitCombin(d,mat3,mat,manual,creator); break; case 2: printf("invalid combination\n"); p=UnitCombin(d,mat3,mat,manual,creator); break; default: break; } return z;}int CreateUnit(unit *d,int mat3[][DIM][DIM+1],int mat[][DIM],int flag,int creator){ int i,p,z,redo=0; do { z=ReadUnit(d,mat3,mat,flag,redo,creator);//----------------------------- trims by sum if(z==0 && creator!=3) //is unit len>1 { if(creator!=1) { CreateSolution(d); d->solution=TrimUnit(d); //trims by sum if(d->indx==-1) redo=1; }//-------------------------------- trims by members if(creator!=2) { for(i=0;i<d->len;i++) { if(d->temp.comb[i]>0) d->solution=IncludesUnit(d,d->temp.comb[i],0); //trims by members } }///////////////////// creator=1 loops endless to CreateUnit if(d->indx==-1) { if(d->type==0 && creator!=2) redo=2; else if(d->type>0 && creator!=1) //doesn't enter if(z=0) //has no members, acts as trim by sum - > number invalid cause number=!sum redo=1; // is type col - > members are correct - > sum is invalid }//-------------------------------------------- //PrintCombin(*d); } //else //return z; }while(d->indx==-1); p=Eleminate(mat3); return z;}unit* BuildCols(unit *kakuru,int *size,int mat3[][DIM][DIM+1],int mat[][DIM],int creator){ int i=0,c,flag,k,j,z,temp[NUM],indx[NUM][2]={0},start,end; for(j=0;j<NUM;j++) { flag=0; c=0; for(i=0;i<NUM;i++) temp[i]=0; for(i=0;i<NUM;i++) { if(mat[i][j]>=0) { temp[i]=1; flag=1; } } if(flag==1) { for(i=0;i<NUM;i++) { if(temp[i]==1 && (temp[i-1]==0 || i==0)) { indx[c][0]=i; indx[c][1]=i; } if(temp[i]==0 && temp[i-1]==1) { indx[c][1]=i-1; c++; } else if(temp[i]==1 && i==NUM-1) { indx[c][1]=i; c++; //printf("mat[%d][%d] = %d flag %d\n",i,j,mat[i][j],flag); }
}
for (k = 0; k < c; k++)
{ // printf("c %d col %d rows %d-%d\n",c,j,indx[k][0],indx[k][1]); kakuru=(unit*)realloc(kakuru,(*size+1)*sizeof(unit)); (kakuru+*size)->CO[0][0]=indx[k][0]; (kakuru+*size)->CO[0][1]=j; (kakuru+*size)->CO[1][0]=indx[k][1]; (kakuru+*size)->CO[1][1]=j; z=CreateUnit(kakuru+*size,mat3,mat,1,creator); *size=*size+1+z; //(*size)++; kakuru=(unit*)realloc(kakuru,(*size+1)*sizeof(unit)); } } } return kakuru;}unit* BuildRows(int mat3[][DIM][DIM+1],int mat[][DIM],int *size,int creator){ int i=0,j,z,flag,temp[NUM][NUM]; unit *rows; rows=(unit*)malloc(sizeof(unit)); do { SetTemp(mat,temp); //rows=(unit*)realloc(rows,(i+1)*sizeof(unit)); printf("Unit no. %d\n",i+1); z=CreateUnit(rows+i,mat3,mat,0,creator);
printf("\ninsert 0 to add another row unit, insert -1 to re-enter current row unit, else to insert column units\n");
scanf("%d", &flag);
if (flag == -1)
{
SetTemp(temp, mat);
SetPlaneK(mat3, mat, 1);
if (z != -1)
i--;
}
i = i + 1 + z; //???? rows=(unit*)realloc(rows,(i+1)*sizeof(unit)); }while(flag<=0); rows=BuildCols(rows,&i,mat3,mat,creator); *size=i; //printf("\n\nBUILD finished size is %d\n\n",*size); return rows;}int Solve(unit *d,int size,int mat3[][DIM][DIM+1]){ int i,j,k=0,z; //printf("SOLVE size is %d\n",size); do { k++; for(i=0;i<size;i++) { for(j=0;j<=(d+i)->indx;j++) { Unit_Mat(d+i,mat3); z=Eleminate(mat3); Mat_Unit(d+i,mat3); z=Eleminate(mat3); } } }while(z>0 && k<20); return z;}void main(){ //to create KAKURU change CreateUnit to build unit without sum\temp unit *x; int i,j,z,*size=0,flag,creator; int mat3[DIM][DIM][DIM+1],mat[DIM][DIM]; int Looped[DIM][DIM][DIM+1]={0};
SetMat(mat);
SetPlaneK(mat3, mat, 1);
printf("enter 0 to solve KAKURU\n");
printf("enter 1 to solve KAKURU without entering sums\n");
printf("enter 2 to solve KAKURU without entering numbers\n");
printf("enter 3 to solve KAKURU without entering sums and numbers\n");
scanf("%d", &creator);
x = BuildRows(mat3, mat, &size, creator);
do
{
PrintInput(mat);
z = Solve(x, size, mat3);
PrintK(mat3);
if (z == -1)
printf("An ERROR has been found\n");
printf("enter 0 to change settings (not available), else to exit\n");
scanf("%d", &flag);
} while (flag == 0);
free(x);
}
Raw
main.cpp
#include <stdio.h>
#include <math.h>
#define DIM 9
void SetPlaneK(int mat[][DIM][DIM + 1], int k0)
{
int i, j, k;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
for (k = k0; k < DIM + 1; k++)
mat[i][j][k] = -1;
}
}
}
void Print(int mat[][DIM][DIM + 1])
{
int i, j, k, m = pow(DIM, 0.5), dig = 0, l, h = 1;
do
{
dig++;
l = DIM / pow(10, dig);
} while (l != 0);
for (i = 0; i < DIM; i++)
{
if (i % m == 0 && i > 0)
{
for (k = 1; k < (dig + 1) * DIM + m - 1; k++)
putchar('-');
putchar('\n');
}
for (j = 0; j < DIM; j++)
{
if (j % m == 0 && j > 0)
printf("|");
for (k = 1; k <= dig; k++)
{
l = mat[i][j][0] / pow(10, k);
if (l == 0)
{
h = k + 1;
h = dig - k;
break;
}
}
for (k = 1; k <= h; k++)
putchar(' ');
printf("%d ", mat[i][j][0]);
}
putchar('\n');
}
putchar('\n');
}
void sPrint(int mat[][DIM][DIM + 1], int row, int col)
{
int i, j, k, m = pow(DIM, 0.5), dig = 0, l, h = 1;
do
{
dig++;
l = DIM / pow(10, dig);
} while (l != 0);
for (i = 0; i <= row; i++)
{
if (i % m == 0 && i > 0)
{
for (k = 1; k < (dig + 1) * DIM + m - 1; k++)
putchar('-');
putchar('\n');
}
for (j = 0; j < DIM; j++)
{
if (i == row && j == col)
break;
else
{ // if(j%m==0 && j>0) // printf("|"); for(k=1;k<=dig;k++) { l=mat[i][j][0]/pow(10,k); if(l==0) { h=k+1; h=dig-k; break; } } for(k=1;k<=h;k++) putchar(' '); printf("%d ",mat[i][j][0]); } } if (i!=row) putchar('\n'); }
}
void PrintP(int mat[][DIM][DIM + 1], int row, int col, int options[])
{
int k;
printf("possibilities for mat[%d][%d]\n", row, col);
printf("value is %d : ", mat[row][col][0]);
for (k = 1; k < DIM + 1; k++)
{
options[k] = mat[row][col][k];
if (mat[row][col][k] == -1)
printf("%d, ", k);
else if (mat[row][col][k] == 1)
printf("answer=%d, ", k);
}
putchar('\n');
}
void REread(int Source[][DIM][DIM + 1], int Dest[][DIM][DIM + 1], int k0)
{
int i, j, k;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
for (k = k0; k < DIM + 1; k++)
Dest[i][j][k] = Source[i][j][k];
}
}
}
int REread1(int Source[][DIM][DIM + 1], int Dest[][DIM][DIM + 1], int checkonly)
{
int i, j, k, c = 0;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
k = Source[i][j][0];
if (k > 0 && Dest[i][j][k] == -1)
c++;
if (k > 0 && checkonly == 1)
Dest[i][j][k] = 0;
}
}
return c;
}
int CheckMat(int Source[][DIM][DIM + 1], int Dest[][DIM][DIM + 1])
{
int i, j, k, c = 0;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
for (k = 0; k < DIM + 1; k++)
if (Dest[i][j][k] == Source[i][j][k])
c++;
}
}
return c;
}
int Update(int mat[][DIM][DIM + 1])
{
int i, j, k, val, c, m = pow(DIM, 0.5), z = 0, hold, error = -1; //-------- checks if mat[i][j] has one option and holds it in mat[i][j][0] for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { c=0; val=mat[i][j][0]; //if (val<=0) //number is undefined yet { for(k=1;k<DIM+1;k++) //checks certainty in plane k { if (mat[i][j][k]==0) c++; else hold=k; } if (c==DIM-1) { mat[i][j][0]=hold; mat[i][j][hold]=1; } else if (c==DIM) { return error; } } } } //printf("z = %d\n",z); for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { c=0; for(k=1;k<DIM+1;k++) //checks certainty in plane k { if (mat[i][j][k]==0) c++; } if (c==DIM) { return -1; } else if (c==DIM-1) z++; } } return z;}int UpdateSingle(int if_val,int mat[][DIM][DIM+1], int i, int j){ int k,c=0,hold,z=0;
if (mat[i][j][0] <= if_val)
{
for (k = 1; k < DIM + 1; k++) //checks certainty in plane k { if (mat[i][j][k]==0) c++; else hold=k; } if (c==DIM-1) { mat[i][j][0]=hold; mat[i][j][hold]=1; } else if (c==DIM) { z=-1; printf("\nUpdateSingle No Options For location %d/%d\n",i,j); return z; } } //if (z!=0) //printf("UpdateSingle z is %d from %d/%d\n",z,i,j); return c;}int Eleminate(int mat[][DIM][DIM+1]){ int i,j,val,c=0,row,col,m=pow(DIM,0.5),temp[DIM]={0},z;//-------- deletes Eleminate in plane k using elemination. for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { val=mat[i][j][0]; if (val>0) { for(row=0;row<DIM;row++) { if (row!=i && mat[row][j][0]<=0 && mat[row][j][val]==-1) mat[row][j][val]=0; if (row!=j && mat[i][row][0]<=0 && mat[i][row][val]==-1) mat[i][row][val]=0; } // for the same square for(row=0;row<DIM;row++) { for(col=0;col<DIM;col++) { if (row/m==i/m && col/m==j/m && mat[row][col][val]==-1) { if (row!=i || col!=j) mat[row][col][val]=0; } } } } } } z=Update(mat); return z;}void X_Eleminate(int mat[][DIM][DIM+1],int if_val_UpdateSingle){ int i,j,k,val,c=0,m=pow(DIM,0.5),temp=0,z;//-------- deletes potentials in plane k using elemination. for(i=0;i<DIM;i++) { //  left to right --------------------------- val=mat[i][i][0]; //printf("$$$$ = = X_Eliminate %d/%d/%d is %d has value of %d\n",i,i,val,mat[i][i][val],mat[i][i][0]); if (val>0) { for(j=0;j<DIM;j++) { if (j!=i && mat[j][j][val]==-1) //&& mat[j][j][0]<=0 ----------------  because of function check! { mat[j][j][val]=0; //printf("X_Eliminate %d/%d/%d is %d has value of %d\n",j,j,val,mat[j][j][val],mat[j][j][0]); } z=UpdateSingle(if_val_UpdateSingle,mat,j,j); //if (z==1) //printf("X_Eliminate z is %d temp is %d - %d/%d/%d is %d has value of %d\n",z,temp,j,j,val,mat[j][j][val],mat[j][j][0]); } } // right to left------------------------------------ k=DIM-1-i; val=mat[i][k][0]; //printf("$$$$ = = X_Eliminate X2 %d/%d/%d is %d has value of %d\n",i,k,val,mat[i][k][val],mat[i][k][0]); if (val>0) { for(j=0;j<DIM;j++) { if (j!=i && mat[j][DIM-1-j][val]==-1)  //&& mat[j][DIM-1-j][0]<=0  ----------------  because of function check! { mat[j][DIM-1-j][val]=0; //printf("X_Eliminate %d/%d/%d is %d has value of %d\n",j,DIM-1-j,val,mat[j][DIM-1-j][val],mat[j][DIM-1-j][0]); } z=UpdateSingle(if_val_UpdateSingle,mat,j,DIM-1-j); } } } }void Vectors(int mat[][DIM][DIM+1]){ int i,j,k,c=0,row,col,m=pow(DIM,0.5),iRow,iCol,cBox,flagR,flagC,z; //-------- deletes Eleminate in plane k
z = Update(mat);
for (i = 0; i < m; i++)
{
for (j = 0; j < m; j++)
{
for (k = 1; k < DIM + 1; k++)
{
for (row = i * m; row < (i + 1) * m; row++)
{
if (row == i * m)
{
cBox = 0;
flagR = 1;
flagC = 1;
iRow = -1;
iCol = -1;
}
for (col = j * m; col < (j + 1) * m; col++) // for the same square { if (mat[row][col][k]==1) { cBox=0; flagR=-1; flagC=-1; iRow=-1; iCol=-1; break; }
if (mat[row][col][k] == -1)
{
cBox++;
if (flagR == 1)
{
iRow = row;
flagR = 0;
}
if (iRow != row && flagR == 0)
flagR = -1; // printf("number %d - row %d vector from box %d/%d c=%d flagR= %d\n",k,iRow,i,j,cBox,flagR); if (flagC==1) { iCol=col; flagC=0; } if (iCol!=col && flagC==0) flagC=-1; //printf("number %d - col %d vector from box %d/%d c=%d flagC = %d\n",k,iCol,i,j,cBox,flagC); } //printf("mat[%d][%d][%d]=%d in box %d/%d cbox is %d\n",row,col,k,mat[row][col][k],i,j,cBox); } }
if (cBox <= m && cBox > 1) //creates vectors { //printf("number %d - row %d vector from box %d/%d c=%d\n",k,iRow,i,j,cBox); if (flagR==0) { //printf("number %d - row %d vector from box %d/%d c=%d\n",k,iRow,i,j,cBox); for(row=0;row<DIM;row++) { for(col=0;col<DIM;col++) { if (row==iRow && col/m!=j && mat[row][col][k]==-1) { mat[row][col][k]=0; //printf("TRIMMED!! number %d - row %d vector from box %d/%d from box %d/%d trimmed mat[%d][%d]\n",k,iRow,i,j,row/m,col/m,row,col); } //printf("row %d num %d vector from box %d/%d c=%d trimmed %d/%d\n",iRow,k,i,j,cBox,row,col); } } } if (flagC==0) // should be else if { //printf("number %d - col %d vector from box %d/%d c=%d\n",k,iCol,i,j,cBox); for(row=0;row<DIM;row++) { for(col=0;col<DIM;col++) { if (row/m!=i && col==iCol && mat[row][col][k]==-1) { mat[row][col][k]=0; //printf("TRIMMED!! number %d - col %d  vector from box %d/%d=%d/%d trimmed mat[%d][%d]\n",k,iCol,i,j,row/m,col/m,row,col); } } } } } }
z = Update(mat);
}
}
}
void X_Vectors(int mat[][DIM][DIM + 1])
{
int i, j, k, c = 0, row, col, m = pow(DIM, 0.5), flagX, flagX2, z; //-------- deletes Eleminate in plane k for(i=0;i<m;i++) { for(j=0;j<m;j++) { //----------------   i and j choose a box! for(k=1;k<DIM+1;k++) //-------------   k chooses a number { c=0; for(row=i*m;row<(i+1)*m;row++) { if(row==i*m) { c=0; flagX=1; flagX2=1; } for(col=j*m;col<(j+1)*m;col++) // for the same square { if (mat[row][col][k]==1) { c=0; flagX=-1; flagX2=-1; break; } if (mat[row][col][k]==-1) { c++; if (row==col && flagX==1) flagX=0; if (row!=col) flagX=-1; if (row==DIM-1-col && flagX2==1) flagX2=0; if (row!=DIM-1-col) flagX2=-1;
if (DIM % 2 == 1 && i == (m - 1) / 2 && j == (m - 1) / 2 && col != DIM - 1 - col) //if in center box there are other potentials { if (row==col) flagX2=-1; if (row==DIM-1-col) flagX=-1; } } } } //creates vectors if (c<=m && c>1) { for(row=0;row<DIM;row++) { for(col=0;col<DIM;col++) { if (flagX==0 && row==col && row/m!=i && col/m!=j && mat[row][col][k]==-1) { mat[row][col][k]=0; printf("TRIMMED!! number %d - vector X1 from box %d/%d to box %d/%d trimmed mat[%d][%d]\n",k,i,j,row/m,col/m,row,col); } if (flagX2==0 && row==DIM-1-col && row/m!=i && col/m!=j && mat[row][col][k]==-1) { mat[row][col][k]=0; printf("TRIMMED!! number %d - vector X2 from box %d/%d to box %d/%d trimmed mat[%d][%d]\n",k,i,j,row/m,col/m,row,col); } } } } } } } z=Update(mat);}void Complete(int mat[][DIM][DIM+1]){ int i,j,k,val,c=0,row,col,m=pow(DIM,0.5),cRow,cCol,cBox,z; //------- checks and completes rows, cols and boxes up to DIM (9). for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { val=mat[i][j][0]; if (val<=0) { for(k=1;k<DIM+1;k++) { cRow=0; cCol=0; cBox=0; if (mat[i][j][k]==-1) { for(row=0;row<DIM;row++) { if (mat[row][j][k]==0) cRow++; if (mat[i][row][k]==0) cCol++; for(col=0;col<DIM;col++) { if (row/m==i/m && col/m==j/m && mat[row][col][k]==0) // for the same square cBox++; }
}
if (cRow == DIM - 1 || cCol == DIM - 1 || cBox == DIM - 1)
{
for (col = 1; col < DIM + 1; col++)
{
if (col != k)
mat[i][j][col] = 0;
}
z = UpdateSingle(0, mat, i, j);
}
}
}
}
}
}
}
int X_Complete(int mat[][DIM][DIM + 1])
{
int i, j, k, x, col, c, val, z, temp = 0; //------- checks and completes rows, cols and boxes up to DIM (9). for(i=0;i<DIM;i++) { val=mat[i][i][0]; if (val<=0) { for(k=1;k<DIM+1;k++) { c=0; for(j=0;j<DIM;j++) { if (j!=i && mat[j][j][k]==0) c++; } if (c==DIM-1) { for(col=1;col<DIM+1;col++) { if (col!=k) mat[i][i][col]=0; } z=UpdateSingle(0,mat,i,i); if (z==8) temp++; } else if (c==DIM) printf("No Options For in X_Vectors X caused by %d/%d/%d to %d/%d/%d\n",i,i,k,j,j,k); } } x=DIM-1-i; val=mat[i][x][0]; if (val<=0) { for(k=1;k<DIM+1;k++) { c=0; for(j=0;j<DIM;j++) { if (j!=i && mat[j][DIM-1-j][k]==0) c++; } if (c==DIM-1) { for(col=1;col<DIM+1;col++) { if (col!=k) mat[i][x][col]=0; } z=UpdateSingle(0,mat,i,x); if (z==8) temp++; } else if (c==DIM) printf("No Options For in X_Vectors X2 caused by %d/%d/%d to %d/%d/%d\n",i,x,k,j,DIM-1-j,k); } } } return temp;}int Solver(int mat[][DIM][DIM+1],int isX){ int z,val; if (isX==0) { z=Eleminate(mat); X_Eleminate(mat,0); Vectors(mat); X_Vectors(mat); z=X_Complete(mat); Complete(mat); val=Update(mat);
}
else
{
z = Eleminate(mat);
Complete(mat);
Vectors(mat);
val = Update(mat);
}
return val;
}
int Input1(int mat[][DIM][DIM + 1], int isX)
{
int k, z, val, row, col, input, choice, old, options[DIM + 1] = {0};
int temp[DIM][DIM][DIM + 1] = {0};
REread(mat, temp, 0);
printf("insert row number\n");
scanf("%d", &row);
printf("insert column number\n");
scanf("%d", &col);
do
{
if (row < 0 || row >= DIM)
{
printf("insert a valid row number\n");
scanf("%d", &row);
}
if (col < 0 || col >= DIM)
{
printf("insert a valid column number\n");
scanf("%d", &col);
}
} while (row < 0 && row >= DIM && col < 0 && col >= DIM);
old = mat[row][col][0];
printf("old value of mat[%d][%d] is %d\n", row, col, old);
printf("insert new number into mat[%d][%d]\nthese are the options:\n", row, col);
PrintP(mat, row, col, options);
scanf("%d", &input);
while (input < 0 || input > DIM) // || temp[row][col][input]!=1) { PrintP(mat,row,col,options); scanf("%d",&input); }
temp[row][col][0] = -1;
SetPlaneK(temp, 1);
z = Solver(temp, isX);
do
{
val = z;
z = Solver(temp, isX);
} while (z != val);
if (temp[row][col][input] == -1)
{
for (k = 1; k < DIM + 1; k++)
temp[row][col][k] = 0;
temp[row][col][0] = input;
temp[row][col][input] = 1;
z = Solver(temp, isX);
do
{
val = z;
z = Solver(temp, isX);
} while (z != val);
printf("press 1 to save changes to SUDOKO\n");
scanf("%d", &choice);
if (choice == 1)
REread(temp, mat, 0);
}
else
printf("Invalid number\n");
return z;
}
void Menu(int mat[][DIM][DIM + 1], int i, int *column, int hold, int isX)
{
int j, k, z, val, choice = -1, col = *column;
do
{
printf("number %d entered in SUDOKU[%d][%d] is wrong\n", hold, i, col);
printf("press 0 to re-enter the entire row\n");
printf("press 1 to re-enter the last number\n");
printf("press 2 to print input\n");
printf("press 3 to print entire SUDOKU\n");
printf("press 4 to change a number by co-ordinates\n");
printf("press 5 to exit menu\n");
scanf("%d", &choice);
//putchar('\n'); //printf("$$ choice is %d last mat[%d][%d]=%d\n",choice,i,col,mat[i][col][0]); switch (choice) { case 0: { *column=0; for(j=0;j<DIM;j++) mat[i][j][0]=-1; SetPlaneK(mat,1); z=Solver(mat,isX); do { val=z; z=Solver(mat,isX); }while(z!=val); sPrint(mat,i,*column); break; } case 1: { for(j=col;j<DIM;j++) { for(k=0;k<DIM+1;k++) mat[i][j][k]=-1; } z=Solver(mat,isX); do { val=z; z=Solver(mat,isX); }while(z!=val);
sPrint(mat, i, col);
break;
}
case 2:
{
sPrint(mat, i, col);
putchar('\n');
choice = -1;
break;
}
case 3:
{
Print(mat);
choice = -1;
break;
}
case 4:
{
z = Input1(mat, isX);
choice = -1;
break;
}
case 5:
break;
default:
{
choice = -1;
break;
}
}
}
while (choice == -1)
;
}
void Read0(int mat[][DIM][DIM + 1], int isX, int temp[][DIM])
{
int i = 0, j, row = 0, col = 0, k, input, z, flag, exit = 0, hold;
SetPlaneK(mat, 0);
printf("enter SUDUKO a whole row at a time using 0 as empty cells\n");
printf("enter invalid number to enter menu\n");
do
{
if (exit == 0)
{
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
input = -1; //printf("input = %d - mat[%d][%d] = %d\n",input,i,j,mat[i][j][0]);
if (mat[i][j][0] > 0 && i >= row && j >= col) // if a hole row entered then Eleminate writes to mat[i][DIM-1][0] and then input writes to mat[i+1][0][0] { scanf("%d",&input); if(mat[i][j][0]!=input && input>0) { row=i; col=j; exit=1; hold=input; }
}
else if (mat[i][j][0] == -1)
{
scanf("%d", &input);
if (exit == 0)
{ //printf("mat[%d][%d] = %d\n",input,i,j,mat[i][j][0]); if (mat[i][j][input]==0 && input>0) flag=1; else flag=0; if (input<0 || input>DIM || flag==1) { row=i; col=j; exit=1; hold=input; } else if (input==0) mat[i][j][0]=0; else if (input>0 && exit==0) { for(k=1;k<DIM+1;k++) mat[i][j][k]=0;
mat[i][j][0] = input;
mat[i][j][input] = 1;
z = Solver(mat, isX);
if (z == -1)
{
row = i;
col = j;
exit = 1;
hold = input;
}
} //sPrint(mat,i,j); //putchar('\n'); } } } if (exit==1) break; } } if (exit==1) { Menu(mat,i,&col,hold,isX); exit=0; }
}
while (mat[DIM - 1][DIM - 1][0] == -1)
;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
temp[i][j] = mat[i][j][0];
}
}
void Read(int mat[][DIM][DIM + 1], int isX, int temp[][DIM])
{
int i = 0, j, row = 0, col = 0, k, input, z, flag, exit = 0, hold;
SetPlaneK(mat, 0);
printf("enter SUDUKO a whole row at a time using 0 as empty cells\n");
printf("enter invalid number to enter menu\n");
do
{
for (i = 0; i < DIM; i++)
{
for (j = col; j < DIM; j++)
{
if (exit == 1)
exit = 0;
scanf("%d", &input);
if (input < 0 || input > DIM)
{
exit = 1;
break;
}
else
{
mat[i][j][0] = input;
if (mat[i][j][input] == 0 && input > 0)
{
exit = 1;
break;
}
else if (input > 0 && exit == 0)
{
for (k = 1; k < DIM + 1; k++)
mat[i][j][k] = 0;
mat[i][j][0] = input;
mat[i][j][input] = 1;
z = Solver(mat, isX);
if (z == -1)
{
exit = 1;
break;
}
} //printf("input = %d - mat[%d][%d] = %d\n",input,i,j,mat[i][j][0]); } } flushall(); if (exit==1) { col=j; Menu(mat,i,&col,input,isX); i--; } else col=0; } }while(mat[DIM-1][DIM-1][0]==-1);
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
temp[i][j] = mat[i][j][0];
}
}
void Read1(int mat[][DIM][DIM + 1], int isX, int temp[][DIM])
{
int mat1[DIM][DIM] = {{0, 1, 0, 6, 0, 0, 0, 5, 0}, {0, 4, 0, 1, 7, 0, 0, 0, 2}, {0, 0, 9, 8, 0, 3, 6, 0, 0}, {8, 6, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 1, 0, 3, 0, 5, 6, 0}, {0, 0, 0, 0, 0, 0, 0, 4, 8}, {0, 0, 7, 2, 0, 5, 8, 0, 0}, {1, 0, 3, 0, 0, 4, 0, 7, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}}; //int mat1[DIM][DIM]={{0,7,0,0,0,1,0,6,0},{6,0,0,0,0,9,0,0,2},{0,1,0,3,6,0,0,0,5},{7,0,6,0,0,4,9,0,1},{0,0,0,7,0,5,0,0,0},{5,0,2,9,0,0,7,0,0},{3,0,0,0,9,7,0,8,0},{1,0,7,8,0,0,0,0,0},{0,6,0,0,0,0,0,2,0}}; //int mat1[DIM][DIM]={{0,8,1,0,5,0,0,6,7},{0,3,0,0,0,1,5,4,0},{0,0,0,0,2,0,0,0,0},{0,0,0,5,9,0,0,0,6},{9,4,0,0,0,0,0,8,3},{2,0,0,0,1,3,0,0,4},{0,0,0,0,6,0,0,0,0},{0,0,9,1,0,0,0,7,0},{0,5,0,0,3,0,8,9,0}}; //int mat1[DIM][DIM]={{2,0},{0,0,3,8,0,0,0,6,2},{1,0,9,0,0,3,0,8,7},{5,9,0,3,0},{0,0,2,0,8,0,6,0,0},{0,0,0,0,0,7,0,3,4},{7,0,0,9,0,0,8,0,3},{0,1,0,0,0,2,5,0,0},{0,0,0,0,4,0,0,0,1}}; //int mat1[DIM][DIM]={{0,0,0,1,0,6,0,0,7},{0,2,0,0,5,0,0,8,0},{6,0,0,0,8,0,0,0,0},{0,0,1,0,0,0,4,0,0},{8,0,0,7,1,4,0,0,5},{0,0,6,0,0,0,3,0,0},{0,0,0,0,7,0,0,0,9},{0,6,0,0,4,0},{2,0,0,3,0,9,0}}; //int mat1[DIM][DIM]={{0,0,0,0,8,0,0,3,6},{0,0,8,0,0,0,5,0,0},{0,0,0,0,0,0,0,0,4},{0,0,6,8,0,0,4,1,0},{0,0,0,3,5,4,0,0,0},{0,5,7,0,0,9,2,0,0},{1,0},{0,0,2,0,0,0,9,0,0},{0,6,0,0,7,0,0,0,1}}; //int mat1[DIM][DIM]={{0,8,6,0,15,14,0,0,0,0,0,0,0,0,4,0},{9,1,15,0,0,0,16,11,0,13,0,0,0,0,3,5},{0,0,0,0,0,0,0,0,0,16,12,3,8,0,11,15},{0,0,3,7,4,5,0,9,0,14,8,0,16,0},{0,0,7,0,10,3,0,6,0,8,0,9,14,0,0,2},{0,0,12,6,0,0,9,14,10,0,0,1,15,0,0,3},{0,11,16,1,2,0,0,0,0,0,13,0,0,0,9,0},{0,0,0,0,0,1,0,12,16,0,3,2,4,0,13,0},{0,7,0,10,6,11,0,3,1,0,2,0},{0,6,0,0,0,12,0,0,0,0,0,8,3,4,10,0},{1,0,0,15,16,0,0,4,6,3,0,0,2,13,0,0},{8,0,0,13,5,0,2,0,4,0,9,7,0,6,0},{0,0,0,8,0,9,11,0,3,0,4,10,1,12},{7,9,0,3,8,13,6,0},{12,2,0,0,0,0,4,0,8,15,0,0,0,3,6,14},{0,10,0,0,0,0,0,0,0,0,6,11,0,8,16}}; //int mat1[DIM][DIM]={{0,0,0,0,15,14,0,0,0,0,0,0,0,0,4,0},{9,1,15,0,0,0,16,11,0,13,0,0,0,0,3,5},{0,0,0,0,0,0,0,0,0,16,12,3,0,0,11,15},{0,0,3,7,4,5,0,9,0,14,8,0,16,0},{0,0,7,0,10,3,0,6,0,8,0,9,14,0,0,2},{0,0,12,6,0,0,9,14,10,0,0,1,15,0,0,3},{0,11,16,1,2,0,0,0,0,0,13,0,0,0,9,0},{0,0,0,0,0,1,0,12,16,0,3,2,4,0,13,0},{0,7,0,10,6,11,0,3,1,0,2,0},{0,6,0,0,0,12,0,0,0,0,0,8,3,4,10,0},{1,0,0,15,16,0,0,4,6,3,0,0,2,13,0,0},{8,0,0,13,5,0,2,0,4,0,9,7,0,6,0},{0,0,0,8,0,9,11,0,3,0,4,10,1,12},{7,9,0,3,8,13,6,0},{12,2,0,0,0,0,4,0,8,15,0,0,0,3,6,14},{0,10,0,0,0,0,0,0,0,0,6,11,0,8,16}};// int mat1[DIM][DIM]={{0,0,0,0,0,14,0,0,0,0,0,0,0,0,4,0},{0,0,0,0,0,0,16,11,0,13,0,0,0,0,3,5},{0,0,0,0,0,0,0,0,0,16,12,3,8,0,11,15},{0,0,3,7,4,5,0,9,0,14,8,0,16,0},{0,0,7,0,10,3,0,0,0,8,0,9,14,0,0,2},{0,0,12,6,0,0,9,14,10,0,0,1,15,0,0,3},{0,11,16,1,2,0,0,0,0,0,13,0,0,0,9,0},{0,0,0,0,0,1,0,12,16,0,3,2,4,0,13,0},{0,7,0,10,6,11,0,3,1,0,2,0},{0,6,0,0,0,12,0,0,0,0,0,8,3,4,10,0},{1,0,0,15,16,0,0,4,6,3,0,0,2,13,0,0},{8,0,0,13,5,0,2,0,4,0,9,7,0,6,0},{0,0,0,8,0,9,11,0,3,0,4,10,1,12},{7,9,0,3,8,13,6,0},{12,2,0,0,0,0,4,0,8,15,0,0,0,3,6,14},{0,10,0,0,0,0,0,0,0,0,6,11,0,8,16}}; int i,j,k,input;
for (i = 0; i < DIM; i++)
{
for (j = 0; j < DIM; j++)
{
input = mat1[i][j]; //if (input==1) mat[i][j][0]=0; for(k=1;k<DIM+1;k++) { if (input>0) mat[i][j][k]=0; else mat[i][j][k]=-1; } if (input>0) //&& flag[input-1]==0) { //flag[input-1]=flag[input-1]+1; mat[i][j][0]=input; mat[i][j][input]=1; } } } for(i=0;i<DIM;i++) for(j=0;j<DIM;j++) temp[i][j]=mat[i][j][0];}void Pick4Guess(int mat[][DIM][DIM+1],int PlaneK[],int Looped[][DIM][DIM+1],int* row,int* col,int* Opt){ int i,j,k,c=0,z=0,m=pow(DIM,2),loop=0; do { (*Opt)--; if(*Opt==1) break; for(i=0;i<DIM;i++) { for(j=0;j<DIM;j++) { if(loop==0) for(k=0;k<DIM+1;k++) PlaneK[k]=0;
c = 0;
if (mat[i][j][0] <= 0 && loop == 0 && Looped[i][j][0] == 0)
{
for (k = 1; k < DIM + 1; k++) //checks certainty in plane k { if (mat[i][j][k]==-1) { PlaneK[k]=1; c++; } else if(mat[i][j][k]==1) { loop=0; break; } } } if(c==*Opt && loop==0 && Looped[i][j][0]==0) { PlaneK[0]=1; *row=i; *col=j; loop=1; Looped[i][j][0]=1; } } } }while(loop==0 && *Opt>1);
//return Opt;}int Guess(int mat[][DIM][DIM+1],int isX,int Looped[][DIM][DIM+1],int* printed){ int i,k,c,hold,z=0,z1,Opt=DIM+1,row,col,m=pow(DIM,2),loop=0,Check,count=0,exit=0,p; int PlaneK[DIM+1]={0},temp[DIM][DIM][DIM+1]={0};
REread(mat, temp, 0);
REread(mat, Looped, 1);
do
{
Pick4Guess(temp, PlaneK, Looped, &row, &col, &Opt);
count = 0;
loop = Opt;
//------------------ GUESS! do { //--------------- //picks a number to guess //printf("Opt is %d loop is %d count is %d\n",Opt,loop,count); for(k=1;k<DIM+1;k++) { if(PlaneK[k]==1) { hold=k; loop--; break; } } //printf("Opt is %d loop is %d\n",Opt,loop);
for (k = 1; k < DIM + 1; k++)
temp[row][col][k] = 0;
temp[row][col][0] = hold;
temp[row][col][hold] = 1;
//--------------------------------------------------------- //------- solves temp ------------------------------ i=0; Check=0; z1=-2; do { i++; z1=Check; //printf("Guessing loop is %d\n",i); Check=Solver(temp,isX); //solves with guessed number }while(Check!=-1 && Check!=m && i!=20 && Check!=z1);
//printf("Guessing mat[%d][%d] is %d, Solved %d times, %d Guessed Correctly\n",row,col,hold,i,Check); //--------------------------------------------------------
if (Check == -1 || Check < m) //bad guess { //------------------------ REread(mat,temp,0);
if (Check == -1)
{
PlaneK[hold] = 0;
mat[row][col][hold] = 0; //-------------- Updates mat with impossible options into plane k! Looped[row][col][hold]=0; //-------------- Updates Looped with impossible options into plane k! Looped[row][col][0]=0; //for Pick4Guess //--------------------- Solves mat with updates exit=-1; i=0; z=0; z1=-2; do { i++; z1=z; z=Solver(mat,isX); }while(z!=-1 && z!=m && i!=20 && z!=z1); if(z==m) return 1; } //--------------------------------------------------------------------------- else if(Check>0 && Check<m) { p=REread1(temp,Looped,0); if(p>0) count++; PlaneK[hold]=-1; } } else if(Check==m) { exit=1; PlaneK[hold]=2; p=REread1(temp,Looped,1); if(p>0) { (*printed)++; count++; printf("Option %d\n",*printed); Print(temp); } REread(mat,temp,0); }
}
while (loop > 0 && Opt > 1)
;
c = 0;
for (k = 1; k < DIM + 1; k++)
{
if (PlaneK[k] == -1)
c++;
}
if (c == 0)
return count;
if (exit == 1)
{
if (Opt > 1)
Opt++;
if (count == 1)
REread(temp, mat, 0);
}
else if (exit == -1 && Opt > 1) /// Opt++; }while(Opt>1);
return -1;
}
int MainMenu(int mat[][DIM][DIM + 1], int isX, int Looped[][DIM][DIM + 1], int *loop, int *val)
{
int flag, a, b, k, z = *val, options[DIM + 1] = {0}, printed = 0;
printf("\npress 0 to continue\n");
printf("press 1 to check a certain number\n");
printf("press 2 to use guessing function\n");
printf("press 3 to change a number by co-ordinates\n");
printf("press 4 to exit menu\n");
scanf("%d", &flag);
switch (flag)
{
case 0:
{
*loop = 0;
flag = 4;
break;
}
case 1:
{
printf("insert row number\n");
scanf("%d", &a);
printf("insert column number\n");
scanf("%d", &b);
do
{
if (a < 0 || a >= DIM)
{
printf("insert a valid a number\n");
scanf("%d", &a);
}
if (b < 0 || b >= DIM)
{
printf("insert a valid column number\n");
scanf("%d", &b);
}
} while (a < 0 && a >= DIM && b < 0 && b >= DIM);
PrintP(mat, a, b, options);
break;
}
case 2:
{
z = Guess(mat, isX, Looped, &printed);
if (z == 1)
flag = 4;
else if (z > 1)
printf("Guess has determined %d solutions\n", z);
else if (z == -1)
printf("No determined solution found\n");
break;
if (printed > 0)
printf("Guess has found %d solutions, there could be more\n", z);
}
case 3:
z = Input1(mat, isX);
break;
default:
break;
}
*val = z;
return flag;
}
void main()
{
int mat[DIM][DIM][DIM + 1] = {0}, temp[DIM][DIM] = {0};
int Looped[DIM][DIM][DIM + 1] = {0};
int val = -2, i = 0, j = 0, m = pow(DIM, 2), flag, isX, z;
printf("Press 0 if this a an X sudoku or any other number if not\n");
scanf("%d", &isX);
flushall();
if (isX == 0)
printf("you have chose X SUDOKU\n");
else
printf("you have chose a regular SUDOKU\n");
Read(mat, isX, temp);
Print(mat);
putchar('\n');
while (val != m) //&& val!=-1) { z=val; val=Solver(mat,isX); //printf("no. of loops reached is %d z is %d\n",j,val); i++; j++;
if (i >= 20 || z == val)
{
printf("no. of loops reached is %d\n", j);
Print(mat);
do
{
flag = MainMenu(mat, isX, Looped, &i, &z);
} while (flag != 3);
}
}
if (val == -1)
printf("An Error was found during calculation!\n");
else
printf("no. of loops until solution %d\n", j);
Print(mat);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment