Code:
/*Sudoku Solver
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* S=3 for standard 9x9 sudoku, I need to find a way to determine the size of the sudoku by reading the input file*/
#define S 2
#define N (S*S)
/* last not included loop*/
#define loop(_I,_From,_To) for (_I=_From;_I<_To;_I++)
/* last included loop */
#define loopto(_I,_From,_To) for (_I=_From;_I<=_To;_I++)
#define Error(X) do { fprintf(stderr,"ERROR %s\n",X); exit(1); } while(0)
typedef signed char sudoku_t[N][N];
int valid(int x,int y,int k,sudoku_t s)
/* returns 1 if char k can be put to s[x][y] */
{
int i,j,x0,y0;
loop (i,0,N) if (s[i][y]==k) return 0;
loop (j,0,N) if (s[x][j]==k) return 0;
x0=S*(x/S);
y0=S*(y/S);
loop (i,x0,x0+S)
loop (j,y0,y0+S) if (s[i][j]==k) return 0;
return 1;
}
void line(char *s)
/* 1 grid line */
{
int i;
loop (i,0,N)
printf("%c%c%c%c",s[i%S!=0],s[1],s[1],s[1]);
putchar(s[0]);
putchar('\n');
}
void prints(sudoku_t s, char *filename)
/* print sudoku s here is the problem.. need to save solved sudoku to a file */
{
/* File pointers to the input file and the outputfile */
FILE *fp;
int x,y;
printf("Saving %s...", filename);
// sanity check - game file has to exist and be writable.
if ((fp = fopen(filename,"w")) == NULL) {
printf("Output file cannot be written!\n");
return 0;
}
loop (x,0,N) {
line(x%S?"| ":"+-");
loop (y,0,N)
fprintf(fp,"%c %c ",
y%S?' ':'|',
s[x][y]?s[x][y]<=9?s[x][y]+'0':s[x][y]+'@':' '); // here is the problem I think... :/
fputs("|",fp); }
line("+-");
// write end of line
fprintf(fp, "\n");
}
/* Close the output file */
fclose (fp);
int nsol=0;
void recursive_search(sudoku_t s)
/*
scans sudoku for an empty field and tries to put a number 1..N there
if successfull, calls recursive_search again. h me8odos pou edeikses me xrisi omos ths memcpy
*/
{
int x,y,k;
loop (x,0,N) loop (y,0,N) {
if (s[x][y]==0) {
loopto (k,1,N) if (valid(x,y,k,s)) {
/* s[x][y]=k is valid, so let's do it and try next */
sudoku_t news;
memcpy(news,s,sizeof(sudoku_t));
news[x][y]=k;
recursive_search(news); }
/* no digit fits s[x][y], so giving up... */
return; } }
/* none of s[x][y] is empty ==> we have a solution */
nsol++; // psaxnw kai gia allo solution an yparxei ;)
}
int main(int argc,char **arg)
{
FILE *fp;
sudoku_t s;
int x,y;
char line[128];
if (argc<2) {
fprintf(stderr,"No file given!");
return 0;
}
else fp=fopen(arg[1],"rt");
if (!fp) Error(arg[1]);
loop (x,0,N) {
if (!fgets(line,128,fp)) Error("unexpected EOF");
loop (y,0,N) {
s[x][y]=line[y]==' '?0:line[y]<='9'?line[y]-'0':line[y]-'@';
if (s[x][y]<0 || s[x][y]>N) Error("input"); } }
putchar('\n');
recursive_search(s);
printf("%d solution%s found\n",nsol,"s"+(nsol==1));
return 0;
}