/***************************************************************************
 *   sudoku.c - programek pro fanousky SUDOKU                              *
 *   Copyright (C) 2005 Marek Sterzik                                      *
 *   marek_sterzik@volny.cz                                                *
 *                                                                         *
 *   Toto je svobodny software; muzete jej sirit nebo menit pod            *
 *   podminkami stanovenymi licenci GNU GPL ve verzi 2 nebo (dle uvazeni)  *
 *   jakekoliv dalsi verze.                                                *
 *                                                                         *
 *   Software je siren v nadeji, ze bude uzitecny, ale BEZ JAKEKOLIV       *
 *   ZARUKY.                                                               *
 *                                                                         *
 *   Pro blizsi informace viz GNU GPL licenci. Viz soubor COPYING.         *
 *                                                                         *
 *  ---------------------------------------------------------------------  *
 *                                                                         *
 *   Preklad:   gcc -o sudoku sudoku.c                                     *
 *   Instalace: cp sudoku /usr/loca/bin/                                   *
 *                                                                         *
 *   Nektere veci nejsou naprogramovany prilis citelne, ale opravovat to   *
 *   zatim nebudu...                                                       *
 ***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <unistd.h>
#include <getopt.h>
#include <time.h>
#include <sys/time.h>

/*integer*/
#define MAXLSIZE 4
#define LSIZE_DEFAULT 3
#define N_DEFAULT 1
/*boolean*/
#define SOLVE_DEFAULT 1
#define RANDOM_DEFAULT 0
#define REDUCE_DEFAULT 0

#define SUDOKU_VERSION "1.0"

#define MAXSIZE (MAXLSIZE*MAXLSIZE)

#define MSG_MSG 1
#define MSG_WARN 2
#define MSG_ERR 3

/*vystup zpravy*/
int msg(int type,char *message,...)
{
	va_list list;
	char *st;
	char buf[1025];
	switch(type)
	{
	case MSG_WARN: st="WARNING";break;
	case MSG_ERR: st="ERROR";break;
	case MSG_MSG:
	default: st="MESSAGE"; break;
	}
	va_start(list,message);
	vsnprintf(buf,1024,message,list);
	va_end(list);
	fprintf(stderr,"%s: %s\n",st,buf);
	return 0;
}


typedef int BOARD[MAXSIZE][MAXSIZE]; /*BOARD je hraci pole*/

/*seznam hracich poli*/
struct BOARDINFO{
	BOARD sboard;
	struct BOARDINFO * next;
};
struct BOARDINFO *boards=NULL; /*prvni prvek seznamu*/
struct BOARDINFO *b_last=NULL; /*posledni prvek seznamu*/

BOARD board; /*vlastni hraci plat*/
int avail[MAXSIZE][MAXSIZE]; /*pocet stupnu volnosti na hracim poli*/
/*seznam volnych cisel pro dane pole; hodnota v poli ma vyznam poctu blokujicich policek*/
int what[MAXSIZE][MAXSIZE][MAXSIZE];

int LSIZE, SIZE;

/*prida do seznamu (k vytisknuti ci dalsimu zpracovani) hraci pole*/
int addboard()
{
	struct BOARDINFO *bi;
	bi=(struct BOARDINFO *)malloc(sizeof(struct BOARDINFO));
	if(!bi) return 0;
	memcpy(bi->sboard,board,sizeof(BOARD));
	bi->next=NULL;
	if(b_last!=NULL){b_last->next=bi;b_last=bi;}
	else boards=b_last=bi;
	return 1;
}

/*uvolni seznam s vysledky*/
int freeboards()
{
	struct BOARDINFO *bi,*next;
	bi=boards;
	while(bi!=NULL) {
		next=bi->next;
		free(bi);
		bi=next;
	}
	return 1;
}

/*nacte stavove pole*/
int loadboard(FILE *fi)
{
	int i,j;
	char buf[11];
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++) {
			if(fi!=NULL)fscanf(fi,"%10s ",buf);
			else strcpy(buf,"-");
			if(!strcmp(buf,"-")) {
				board[i][j]=-1;
			} else {
				board[i][j]=atoi(buf);
				if(board[i][j]<=0 || board[i][j]>SIZE) return 0;
				board[i][j]--;
			}
		}
	return 1;
}

/*vytiskne jeden vysledek*/
int showboard(FILE *fo,BOARD *board)
{
	int i,j,k,s;
	if(fo==NULL)return 1;
	for(i=0;i<SIZE;i++) {
		for(j=0;j<SIZE;j++) {
			if(j>0)fprintf(fo," ");
			if((*board)[i][j]<0)fprintf(fo,"-");
			else fprintf(fo,"%d",(*board)[i][j]+1);
		}
		fprintf(fo,"\n");
	}
	fprintf(fo,"\n");
	return 1;
}

/*vytiskne vsechny ulozene vysledky*/
int showallboards(FILE *fo)
{
	struct BOARDINFO *bi,*next;
	bi=boards;
	while(bi!=NULL) {
		showboard(fo,&bi->sboard);
		bi=bi->next;
	}
	return 1;
}

/*upravi stupne volnosti policka (i,j) tak ze jej blokuje/blokovalo cislo k *
 * w==0 - cislo k jej nove zacina blokovat                                  *
 * w==1 - cislo k jej prestava blokovat                                     */
int testboard(int i,int j,int k,int w)
{
	if(w) {
		if(what[i][j][k]>0) {
			what[i][j][k]--;
			if(what[i][j][k]==0)
				avail[i][j]++;

		}
		return 1;
	} else {
		if(what[i][j][k]==0)
			avail[i][j]--;
		what[i][j][k]++;
		if(avail[i][j]<=0){return 0;}
		if(board[i][j]>=0 && what[i][j][board[i][j]]>0)return 0;
		return 1;
	}
}

/*upravi stupne volnosti pri obsazeni (w==0) nebo uvolneni (w==1) policka (i,j)*/
int update_board(int i,int j,int w)
{
	int k;
	int zi,zj;
	int ri,rj;
	int rv;
	int size;
	rv=1;
	zi=i-(i%LSIZE); zj=j-(j%LSIZE);
	size=SIZE;
	k=0;
	while(k<size) {
		ri=i;rj=k;
		if(rj!=j && !testboard(ri,rj,board[i][j],w))rv=0; /*radky*/
		ri=k;rj=j;
		if(ri!=i && !testboard(ri,rj,board[i][j],w))rv=0; /*sloupce*/
		ri=zi+k/LSIZE;rj=zj+k%LSIZE;
		if(ri!=i && rj!=j && !testboard(ri,rj,board[i][j],w))rv=0; /*ctverecky*/
		if(w==0 && rv==0) {
			w=1;
			size=k+1;
			k=0;
		}
		else
			k++;
	}
	return rv;
}

/*pripravi prvotni stupne volnosti*/
int make_avail()
{
	int i,j,k;
	int zi,zj;
	int ri,rj;
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++) {
			avail[i][j]=SIZE;
			for(k=0;k<SIZE;k++)
				what[i][j][k]=0;
		}
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++)
			if(board[i][j]>=0 && !update_board(i,j,0))return 0;
	return 1;
}

/*najde nevyplnene policko s minimalnim stupnem volnost - zatim implementovano provizorne*/
int find_min(int *ii,int *jj)
{
	int i,j,min,rv;
	rv=0;
	for(i=0;i<SIZE;i++)
		for(j=0;j<SIZE;j++)
			if(board[i][j]<0) {
				if(!rv || avail[i][j]<min) {
					min=avail[i][j];
					*ii=i;
					*jj=j;
				}
				rv=1;
			}
	return rv;
}

/*generuje nahodnou permutaci*/
int * rndperm(int size)
{
	int i,j,k;
	int *perm;
	perm=(int *)malloc(size*sizeof(int));
	for(i=0;i<size;i++)
		perm[i]=i;
	for(i=0;i<size;i++) {
		j=rand()%(size-i);
		k=perm[i];
		perm[i]=perm[i+j];
		perm[i+j]=k;
	}
	return perm;
}

/*vlastni vypocet hry:                                         *
 * N - pocet reseni, ktera se maji najit (postupne se snizuje) *
 * random - pokud se ma pracovat nahodne (mirne pomalejsi)     *
 * add - jestli se ma vysledek pridat do seznamu (varianta     *
 *        add==0 je vhodna pro testovani poctu reseni          */
int calc_sudoku(int *N,int random,int add)
{
	int i,j,k,l;
	int *rnd_perm;
	if(*N==0)return 0;
	if(!find_min(&i,&j)) { 
		if(add && !addboard())
			msg(MSG_WARN,"Cannot add board to list");
		if((*N)>0)(*N)--;
		return 0;
	}
	if(avail[i][j]<1)return 0;
	rnd_perm=NULL;
	if(random)rnd_perm=rndperm(SIZE);
	for(l=0;l<SIZE;l++)
	{
		if(rnd_perm)k=rnd_perm[l];
		else k=l;
		
		if(what[i][j][k]==0)
		{
			board[i][j]=k;
			if(update_board(i,j,0)) {
				calc_sudoku(N,random,add);
				update_board(i,j,1);
			}
			board[i][j]=-1;
			if(*N==0) {
				if(rnd_perm)free(rnd_perm);
				return 0;
			}
		}
	}
	if(rnd_perm)free(rnd_perm);
	return 0;
}

/*vraci pocet reseni dane hry - 0 - zadne; 1 - prave jedno; 2 - vice reseni*/
int num_of_solutions(struct BOARDINFO *bi)
{
	int N;
	memcpy(board,bi->sboard,sizeof(BOARD));
	if(!make_avail())return 0;
	N=2;
	calc_sudoku(&N,0,0);
	if(N>=2)return 0;
	else if(N==1)return 1;
	else return 2;
}

struct ij_info
{
	int i,j;
};

/*takova hodne odporne naprogramovana funkce:-)
 * Preji prijemne krece pri cteni...*/
int reduceallboards(int random)
{
	struct BOARDINFO *bi;
	int n,nn,i,j,k,b,index;
	int perm;
	struct ij_info *iji,*iji_act;
	for(bi=boards,index=0;bi!=NULL;bi=bi->next,index++)
	{
		nn=num_of_solutions(bi);
		if(nn==0)msg(MSG_WARN,"board %d has no solution",index+1);
		else if(nn>1) msg(MSG_WARN,"board %d has more solution",index+1);
		else
		{
			iji=(struct ij_info *)malloc(sizeof(struct ij_info)*SIZE*SIZE);
			if(!iji) msg(MSG_ERR,"cannot reduce: allocation error");
			else
			{
				n=0;
				for(i=0;i<SIZE;i++)
					for(j=0;j<SIZE;j++)
					{
						
						if(bi->sboard[i][j]>=0)
						{
							iji[n].i=i;
							iji[n].j=j;
							n++;
						}
					}
				while(n>0)
				{
					if(random) perm=rand()%n;
					else perm=0;
					iji_act=iji+perm;
					b=bi->sboard[iji_act->i][iji_act->j];
					bi->sboard[iji_act->i][iji_act->j]=-1;
					if(num_of_solutions(bi)!=1)
						bi->sboard[iji_act->i][iji_act->j]=b;
					n--;
					memcpy(iji_act,iji+n,sizeof(struct ij_info));
				}
				free(iji);
			}
		}
		
	}
}

int version(char *name)
{
	if(!name)name="sudoku";
	fprintf(stderr,"sudoku v%s\n",SUDOKU_VERSION);
	fprintf(stderr,"\n");
	fprintf(stderr,"compile flags: ");
	fprintf(stderr,"MAXLSIZE=%d; ",MAXLSIZE);
	fprintf(stderr,"LSIZE_DEFAULT=%d; ",LSIZE_DEFAULT);
	fprintf(stderr,"N_DEFAULT=%d; ",N_DEFAULT);
	fprintf(stderr,"SOLVE_DEFAULT=%s; ",SOLVE_DEFAULT?"true":"false");
	fprintf(stderr,"RANDOM_DEFAULT=%s; ",RANDOM_DEFAULT?"true":"false");
	fprintf(stderr,"REDUCE_DEFAULT=%s; ",REDUCE_DEFAULT?"true":"false");
	fprintf(stderr,"\n");
	return 0;

}

int help(char *name)
{
	fprintf(stderr,"ussage: %s [-i infile | -e] [-o outfile] [-S size] [-s|-d] [-n n] [-r] [-R] [-h|-v]\n",name);
	fprintf(stderr,"	-i infile   --input=infile    specify input file (default stdin)\n");
	fprintf(stderr,"	-e          --empty           input file is empty stream\n");
	fprintf(stderr,"	-o outfile  --output=outfile  specify output file (default stdout)\n");
	fprintf(stderr,"	-S size     --size=n          specify the board size\n");
	fprintf(stderr,"	-s          --solve           solve\n");
	fprintf(stderr,"	-d          --dont-solve      don't solve\n");
	fprintf(stderr,"	-n n        --count=n         show n matches (use \"-n all\" for all matches)\n");
	fprintf(stderr,"	-r          --random          print matches in random order\n");
	fprintf(stderr,"	-R          --reduce          reduce solved boards to minimum\n\n");
	fprintf(stderr,"	-h          --help            display this help\n");
	fprintf(stderr,"        -v          --version         display version info\n\n\n");
	fprintf(stderr,"examples:\n");
	fprintf(stderr,"solve a simple 2-sized board and print one random result:\n");
	fprintf(stderr,"	echo \"1 2 - - - - 1 2 - - - - - - - -\" | %s -S 2 -s -n 1 -r\n",name);
	fprintf(stderr,"generate one random board:\n");
	fprintf(stderr,"	%s -e  -n 1 -r -R\n",name);
	fprintf(stderr,"\n");
	return 0;
}
static struct option long_options[] = {
	{"infile",1,0,'i'},
	{"outfile",1,0,'o'},
	{"empty",0,0,'e'},
	{"size",1,0,'S'},
	{"solve",0,0,'s'},
	{"dont-solve",0,0,'d'},
	{"count",1,0,'n'},
	{"random",0,0,'r'},
	{"reduce",0,0,'R'},
	{"help",0,0,'h'},
	{"version",0,0,'v'},
	{0,0,0,0}
};

int main(int argc,char **argv)
{
	FILE *fi,*fo,*f;
	char *mod;
	int solve,o,N,NN,random,reduce;
	int opt_ind;
	struct timeval tv;
	gettimeofday(&tv,NULL);
	srand(tv.tv_usec);
	fi=stdin;
	fo=stdout;
	LSIZE=LSIZE_DEFAULT;
	solve=SOLVE_DEFAULT;
	N=N_DEFAULT;
	random=RANDOM_DEFAULT;
	reduce=REDUCE_DEFAULT;

	while((o=getopt_long(argc,argv,"dehi:n:o:rRsS:",long_options,&opt_ind))!=-1)
	{
		switch(o)
		{
		case 'h':
		case 'v':
			if(o=='h')help(argv[0]);
			else version(argv[0]);
			if(fi!=NULL && fi!=stdin)fclose(fi);
			if(fo!=NULL && fo!=stdout)fclose(fo);
			return 0;
		case 'e':
			if(fi!=stdin){ msg(MSG_WARN,"input file defined, ignoring"); break;}
			fi=NULL;
			break;
		case 'i':
			mod="r";
			if(fi!=stdin){ msg(MSG_WARN,"input file defined, ignoring"); break;}
			goto l1;
		case 'o':
			mod="w";
			if(fo!=stdout){ msg(MSG_WARN,"output file defined, ignoring"); break; }
l1:
			if(!strcmp(optarg,"-"))f=((o=='i')?stdin:stdout);
			else f=fopen(optarg,mod);
			if(!f)
			{
				if(fi!=NULL && fi!=stdin)fclose(fi);
				if(fo!=NULL && fo!=stdout)fclose(fo);
				msg(MSG_ERR,"cannot open input/output file");
				return 1;
			}
			if(o=='i')fi=f;
			else fo=f;
			break;
		case 'R':
			reduce = !reduce;
			break;
		case 'r':
			random = !random;
			break;
		case 's':
			solve=1;
			break;
		case 'd':
			solve=0;
			break;
		case 'n':
			if(!strcmp(optarg,"all"))N=-1;
			else N=atoi(optarg);
			if(N<-1)msg(MSG_WARN,"invalid parameter: -n");
			if(N<0)N=-1;
			break;
		case 'S':
			LSIZE=atoi(optarg);
			if(LSIZE<=0 || LSIZE>MAXLSIZE)
			{
				if(fi!=NULL && fi!=stdin)fclose(fi);
				if(fo!=NULL && fo!=stdout)fclose(fo);
				msg(MSG_ERR,"invalid size");
				return 1;
			}
		}
	}
	if(optind<argc)
	{
		if(fi!=NULL && fi!=stdin)fclose(fi);
		if(fo!=NULL && fo!=stdout)fclose(fo);
		help(argv[0]);
		return 1;
	}
	
	SIZE=LSIZE*LSIZE;
	if(!loadboard(fi))
	{
		msg(MSG_ERR,"invalid input");
		if(fi!=NULL && fi!=stdin)fclose(fi);
		if(fo!=NULL && fo!=stdout)fclose(fo);
		return 1;
	}
	if(fi!=NULL && fi!=stdin && fclose(fi))msg(MSG_WARN,"cannot close input stream");
	if(!make_avail())
	{
		msg(MSG_WARN,"bad input: no solution");
		return 1;
	}
	if(solve)
	{
		NN=N;
		calc_sudoku(&N,random,1);
		if(NN>0 && NN==N)
		{
			msg(MSG_ERR,"no solution");
			if(fo!=NULL && fo!=stdout)fclose(fo);
			return 1;
		}
	}
	else
	{
		if(!addboard())
			msg(MSG_ERR,"Internal error: cannot allocate memory");
	}
	if(reduce)reduceallboards(random);
	showallboards(fo);
	freeboards();
	if(fo!=NULL && fo!=stdout && fclose(fo))msg(MSG_WARN,"cannot close output stream");
	return 0;
}