/* su_doku
 *
 * construit, complète, donne le nombre de solutions
 * 
 * GNU GPL Licence
 * Jean-Paul Davalan Nov. 2005 <jpdvl@wanadoo.fr>
 * 
 * http://perso.wanadoo.fr/jean-paul.davalan/jeux/logic/sudoku/su_doku.c
 *
 * 
 * compilation : gcc -O2 -o sud su_doku.c
 *
 * utilisation : sud "grille incomplète"
 *
 * exemples : 
 *   sudoku\> sud "----915----5--6---12-----94--8-7---1--2---4--3---6-2--81-----23---2--7----364----"
 *   -7---1--2---4--3---6-2--81-----23---2--7----364----"--915----5--6---12-----94--8
 *   solution 1 :
 *   4 8 7  3 9 1  5 6 2
 *   9 3 5  4 2 6  8 1 7
 *   1 2 6  7 8 5  3 9 4
 *
 *   6 4 8  5 7 2  9 3 1
 *   7 5 2  1 3 9  4 8 6
 *   3 9 1  8 6 4  2 7 5
 *
 *   8 1 4  9 5 7  6 2 3
 *   5 6 9  2 1 3  7 4 8
 *   2 7 3  6 4 8  1 5 9
 *
 *   Nombre de solutions : 1
 *   
 *   sudoku\> sud "12----6---7-----9--6--54---3----79-----1-8------4----2---56--1--3-----8---4------"
 *   ...
 *   Nombre de solutions : 847
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int m[]={0,1,2,4,8,16,32,64,128,256};

typedef struct sud {
	int nsolutions, 
	    chiffres,
	    *tb,
	    *fixe,
	    *lib;
} sud;


void affiche(sud *s, int aff);
void avance(sud *s, int u, int aff, int maxsols);
sud * nouveau();
void suddel(sud *s);
sud * copie(sud *s);
void lecture(sud *s, char *st);




sud * nouveau() {
	sud *p = (sud *) malloc(1*sizeof(sud));
        p->tb = (int *) malloc(81*sizeof(int));
	p->fixe = (int *) malloc(81*sizeof(int));
	p->lib = (int *) malloc(27*sizeof(int));
	return p;
}

void suddel(sud *s) {
	free(s->tb);
	free(s->fixe);
	free(s->lib);
	free(s);
}

sud * copie(sud *s) {
	int i;
	sud *s2=nouveau();
	for(i=0;i<81;i++) {
		s2->tb[i] = s->tb[i];
		s2->fixe[i] = s->fixe[i];
	}
	for(i=0;i<27;i++) {
		s2->lib[i] = s->lib[i];
	}
        return s2;
}


void avance(sud *s, int u, int aff, int maxsols) {
	int i, b, lig, col, box, v;
	if(maxsols>0 && s->nsolutions>=maxsols) return;
	if(u==81) {
		s->nsolutions++;
		/*
		if(s->nsolutions%100000==0) { 
			printf("%d\r",s->nsolutions);
			fflush(stdout);
		}
		*/
		if(aff) affiche(s, aff);
		return;
	} else if(s->fixe[u]==1) {
		avance(s,u+1, aff, maxsols);
	} else {
		lig=u/9; 
		col=u%9; 
		box=3*(lig/3)+(col/3);
		v = (s->lib[lig]| s->lib[9+col] | s->lib[18+box]) ;
		for(i=1;i<=9;i++) {
			b = m[i];
			if((v&b) != b) {
				s->lib[lig]     |= b;
				s->lib[9+col]   |= b;
				s->lib[18+box]  |= b;
				s->tb[u] = i;
				avance(s, u+1, aff, maxsols);
				s->lib[lig]     -= b;
				s->lib[9+col]   -= b;
				s->lib[18+box]  -= b;
				//s->tb[u] = 0;
			}
		}
	}
	
}

void aleatoire(sud *s, int u, int aff, int maxsols) {
        int i, b, lig, col, box, v, bij[9];
        if(maxsols>0 && s->nsolutions>=maxsols) return;
        if(u==81) {
                s->nsolutions++;
                if(aff) affiche(s, aff);
                return;
        } else if(s->fixe[u]==1) {
                aleatoire(s,u+1, aff, maxsols);
        } else {
		for(i=0;i<9;i++) bij[i]=i+1;
                for(i=8;i>0;i--) {
                  int r, z;
                  r=(int) (((i+1.0)*rand())/(RAND_MAX+1.0));
                  z=bij[i];
                  bij[i]=bij[r];
                  bij[r]=z;
                }
                lig=u/9;
                col=u%9;
                box=3*(lig/3)+(col/3);
                v = (s->lib[lig]| s->lib[9+col] | s->lib[18+box]) ;
                for(i=1;i<=9;i++) {
                        int ii=bij[i-1];
                        b = m[ii];
                        if((v&b) != b) {
                                s->lib[lig]     |= b;
                                s->lib[9+col]   |= b;
                                s->lib[18+box]  |= b;
                                s->tb[u] = ii;
                                aleatoire(s, u+1, aff, maxsols);
                                s->lib[lig]     -= b;
                                s->lib[9+col]   -= b;
                                s->lib[18+box]  -= b;
                                //s->tb[u] = 0;
                       }
		}
	}
}
void affiche(sud *s, int aff) {
	int i;
	if(s->nsolutions>0)printf("solution %d :\n", s->nsolutions);
	else printf("proposition :\n");
	for(i=0;i<81;i++) {
		printf("%d ",s->tb[i]);
		if((i+1)%27==0)printf("\n\n");
		else if((i+1)%9==0)printf("\n");
		else if((i+1)%3==0)printf(" ");
	}
	//for(i=0;i<81;i++) { printf("%d",s->tb[i]); }
	//printf("\n--\n");
}

void lecture(sud *s, char *st) {
	int i;
	unsigned char *q;
	s->chiffres = 0;
	s->nsolutions = 0;
	for(i=0, q=st;*q!='\x0' && i<81;i++, q++) {
		int c = *q - '0';
		if(1<=c && c<=9 ) {
			s->tb[i]=c; s->fixe[i]=1; s->chiffres++;
		} else {
			s->tb[i]=0; s->fixe[i]=0;
		}
	}
	for(i=0;i<27;i++) {
		s->lib[i] = 0;
	}
	for(i=0;i<81;i++) {
		int d, lig= i/9, col=i%9, box=3*(lig/3)+(col/3);
		if(s->tb[i]!=0) {
			d = m[s->tb[i]];
			s->lib[lig] += d;
			s->lib[9+col] += d;
			s->lib[18+box] += d;
		}
	}
}


int main(int argc, char *argv[]) {
	int i;
	sud *s;
        srand(time(NULL));

	s = nouveau();
        if(argc==1) {
          lecture(s,"");
          aleatoire(s, 0, 1, 1);
	} else {
          for(i=1;i<argc;i++) {
	    lecture(s, argv[1]);
 	    avance(s, 0, 1, 0);
	    printf("Nombre de solutions : %d\n",s->nsolutions);
          }
	}
	return 0;
}