/*
This is source code of function which solves sudoku,
function returns 1 if solution exists and 0 if not exist.
In case if solution exists, you have resolution in entry parameter of
this function
You can run this function in function main() eg.
if(sudoku(T)) print(T);
where print(T) is group of printing instructions of all table T and T is matrix
which is declared as int T[9][9];
*/
#include <stdlib.h>
#include <stdio.h>
int sudoku(int S[9][9])
{
int **T;
int W[9];
int nr, ile, i, i1, j, j1, jest, k, L, LL, min, ok, w, wpis;
ok=1;
i=0;
while (i<9 && ok){
j=0;
while (j<9 && ok) {
ok=((S[i][j]>=0) && (S[i][j]<=9));
j++;
}
i++;
}
if (ok){
w=0;
while ((w<9) && ok){
for (i=0;i<9;i++) W[i]=0;
for (j=0;j<9;j++) if (S[w][j]>0) W[S[w][j]-1]++;
j=0;
while (j<9 && ok){
ok=(W[j]<2);
j++;
}
w++;
}
if (ok) {
k=0;
while (k<9 && ok){
for (i=0;i<9;i++) W[i]=0;
for (i=0;i<9;i++) if (S[i][k]>0) W[S[i][k]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
k++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=0;i<3;i++)
for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=0;i<3;i++)
for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=0;i<3;i++)
for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=3;i<6;i++)
for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=3;i<6;i++)
for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=3;i<6;i++)
for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=6;i<9;i++)
for (j=0;j<3;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=6;i<9;i++)
for (j=3;j<6;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
for (i=0;i<9;i++) W[i]=0;
for (i=6;i<9;i++)
for (j=6;j<9;j++) if (S[i][j]>0) W[S[i][j]-1]++;
i=0;
while (i<9 && ok){
ok=(W[i]<2);
i++;
}
if (ok){
ile=0;
T=(int **)malloc(2*sizeof(int *));
for(i=0;i<9;i++)
for(j=0;j<9;j++){
if (S[i][j]==0){
ile++;
T[0]=(int *)realloc(T[0], ile*sizeof(int));
T[1]=(int *)realloc(T[1], ile*sizeof(int));
T[0][ile-1]=i;
T[1][ile-1]=j;
}
}
if (ile>0){
nr=0;
while (nr>-1 && nr<ile){
wpis=0;
min=S[T[0][nr]][T[1][nr]];
S[T[0][nr]][T[1][nr]]=0;
LL=min;
for (L=9;L>min;L--){
jest=0;
j=0;
while (j<9){
if (S[T[0][nr]][j]==L) jest=1;
j++;
}
i=0;
while (i<9){
if (S[i][T[1][nr]]==L) jest=1;
i++;
}
if (T[0][nr]<3) i=0; else{
if (T[0][nr]>2 && T[0][nr]<6) i=3; else i=6;
}
if (T[1][nr]<3) j=0; else {
if (T[1][nr]>2 && T[1][nr]<6) j=3; else j=6;
}
for (i1=i;i1<i+3;i1++)
for (j1=j;j1<j+3;j1++) if (S[i1][j1]==L) jest=1;
if (!jest) LL=L;
}
if (LL>min){
S[T[0][nr]][T[1][nr]]=LL;
wpis=1;
} else
{
S[T[0][nr]][T[1][nr]]=0;
wpis=0;
}
if (wpis) nr++; else nr--;
}
}
ok=(nr>ile-1);
free(T[0]);
free(T[1]);
free(T);
}
}
}
}
}
}
}
}
}
}
}
}
return ok;
}
/*
in function main()
int T[9][9];
...
if (sudoku(T)) print(T);
...
*/
