//not perfect, but a fun start
//have file 'sudoku114.txt' in working directory
//contains 9x9 starting condition for puzzle, ie:
/*
020600005
589240000
310000704
407090218
000000000
260005300
000109060
172560803
090830471
*/
#include <stdio.h>
#include <stdlib.h>
struct sudoku
{
int puzzle[9][9];
int iteration;
struct sudoku* next;
struct sudoku* prev;
};
struct sudoku *Head;
struct sudoku *Ref;
struct sudoku *New;
struct sudoku *Back;
char Filename[15] = "sudoku114.txt";
int avail[9];
int TOTAL,cheat;
int AvailSum()
{
int p,sum = 0;
for(p=0; p<9; p++)
sum += avail[p];
return sum;
};
void FindAvailables(int r, int c)
{
int i,j,n,m;
for(i=0; i<9; i++) //init available
avail[i] = 1;
for(i=0; i<9; i++) //elim availables
if(Ref->puzzle[r][i]>0)
avail[Ref->puzzle[r][i]-1] = 0; //along row
for(j=0; j<9; j++)
if(Ref->puzzle[j][c]>0)
avail[Ref->puzzle[j][c]-1] = 0; //along column
n = 3*(r/3); m = 3*(c/3);
for(i=n; i<3+n; i++)
for(j=m; j<3+m; j++)
if(Ref->puzzle[i][j]>0)
avail[Ref->puzzle[i][j]-1] = 0; //within group
};
void PrintPuzzle()
{
int r,c;
TOTAL = 0;
printf("\n-Iteration %d-\n\n",Ref->iteration);
printf(" 012 345 678\n");
for(r=0; r<9; r++)
{
if(r%3==0) printf("\n");
printf("%d ",r);
for(c=0; c<9; c++)
{
if(c%3==0) printf(" ");
printf("%d",Ref->puzzle[r][c]);
TOTAL += Ref->puzzle[r][c];
} printf("\n");
}
if(TOTAL==405)
{
printf("\n************\n* YOU WON! *\n************\n");
exit(EXIT_SUCCESS);
}
};
void Hints() //find the # avails for each cell, report list
{
int a=0,r,c,i,j,k,m,n,p=1; //format: [r,c] : (avails)
printf("\nHINTS\n");
while(p<10) //change to higher numbers for larger avail lists
{
printf("\nAVAIL-%d CELLS\n",p);
for(r=0; r<9; r++)
{
for(c=0; c<9; c++)
{
if(Ref->puzzle[r][c]==0) //find availabilities for non-occupied cells only
{
FindAvailables(r,c);
if(AvailSum()==p)
{
a++;
printf("[%d %d]:(",r,c);
for(k=0; k<9; k++)
{
if(avail[k]>0)
{
printf("%d ",k+1);
if(p==1 && cheat==1)
Ref->puzzle[r][c] = k+1; //input "9 11" autofills avail-1 cells
}
}
printf("\b)\n");
}
}
}
} p++;
}
PrintPuzzle();
if(!a)
{
printf("\nNO AVAIL-1 CELLS REMAIN\n");
if(cheat) cheat = 0;
}
};
int main()
{
Head = (struct sudoku*)malloc(sizeof(struct sudoku));
if(Head==NULL)
{ printf("CANT MAKE HEAD NODE"); exit(EXIT_FAILURE); }
Head->next = NULL;
Head->prev = NULL;
Head->iteration = 0; //Head will store the initial read-in from file
FILE *fptr;
fptr = fopen(Filename,"r");
if(fptr==NULL)
{
printf("\nUnable to access file \"%s\".\n",Filename);
printf("Please ensure it exists in working directory\n\n");
printf("Program Terminated...\n\n");
exit(EXIT_FAILURE);
}
int row=0,col=0,entry,i,j,n,m,c;
while((c = fgetc(fptr)-48)!=EOF)
{
if(c!=-38) Head->puzzle[row][col++] = c; //sep col++?
if(col>8)
{ col = 0; row++; }
if(row>8) break;
}
fclose(fptr);
Ref = Head;
bkup:
PrintPuzzle();
do
{
printf("\n(9 9 = HINTS)\n(9 11 = AUTOSOLVE)\n\n(row col): ");
scanf("%d %d",&row,&col);
if(row==9 && col==9) Hints();
else if(row==9 && col==11)
{ cheat = 1; while(cheat) Hints(); cheat = 0; }
else if(row>8 || col>8) printf("\nOut of Range\n");
else if(Ref->puzzle[row][col]) printf("\nOccupied\n");
else
{
FindAvailables(row,col);
if(!AvailSum())
{
printf("** -- DEADLOCKED -- **\nIteration: %d",Ref->iteration);
printf("\nBack up how many steps: ");
scanf("%d",&entry);
if(entry>Ref->iteration) entry = 0;
else entry = (Ref->iteration)-entry;
while((Ref->iteration)>entry)
{ Back = Ref->prev; Back->next = NULL; free(Ref); Ref = Back; }
goto bkup;
}
printf("\nAvailable: (");
for(i=0; i<9; i++)
if(avail[i])
printf("%d ",i+1);
printf("\b)");
printf("\nEntry(0 QUITS): ");
scanf("%d",&entry);
if(!avail[entry-1])
printf("\"%d\" NOT AVAILABLE",entry);
else
{
New = (struct sudoku*)malloc(sizeof(struct sudoku));
if(New==NULL)
return 1;
*New = *Ref;
New->puzzle[row][col] = entry;
New->iteration = (Ref->iteration)+1;
New->next = NULL;
New->prev = Ref;
Ref->next = New;
Ref = New;
PrintPuzzle();
}
}
} while(entry > 0);
return 0;
}