#include <stdio.h>
#include <stdlib.h>
#include <math.h>



int RandomSudoku(){}
void GenerateInitialArray(){}
int CheckInitialArray(int n){}
int GlobalStructure(){}
int CallMainRoutine(int i, int j){}
int MainRoutine(int i,int j){}
int FillThisPosition(int i, int j){}
int FillLatterPosition(int i, int j){}
int CheckSquare(int c,int d){}
int CheckLine(int c,int d){}
int CheckColumn(int c,int d){}
int CheckSizeOfSquare(int n){}
void DisplayResult(){}





int main(){
	int debug = 0;
	int debug2 = 0; // special problem
	int debug3 = 0; 
	int debug4 = 0; // special problem
	int debug5 = 0; // gives DisplayResult and activates debug
	int debug6 = 0; // prints the array if var_of_CallMainRoutine == 7,8
	int var_for_idiots = 0;
	int var_for_RandomSudoku = 0;
	long int loop_count=0;
	int i = 0;
	int j = 0;
	int a = 0;
	int b = 0;
	int n = 9;
	int x = 4;
	int y; //  number of filled boxes at start
	char awnser = '\0';
	char awnser2 = '\0';
	int init_array[n][n]; 
	int position_array[n][n];
	int array[n][n];
	FILE *input;
	
	
	

	

	
	

	// create initial array
	/*
				int list_array[81]={2,0,0,0,8,9,0,7,0,
									0,3,0,0,0,0,0,4,0,
									0,0,0,0,0,4,0,0,9,
									0,9,0,0,7,0,0,0,0,
									0,2,1,0,0,0,3,8,0,
									0,0,0,0,4,0,0,5,0,
									5,0,0,7,0,0,4,0,0,
									0,1,0,0,0,0,0,9,0,
									0,6,0,4,5,0,0,0,0};
					for(i=0;i<n;i++){
						for(j=0;j<n;j++){
							init_array[i][j] = list_array[i*n+j];
						}
					}
	
	int list_array[256]={0,0,0,0,8,9,0,0,0,0,0,0,0,0,0,0,
		 				 0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
		 				 0,0,2,0,0,4,0,0,9,0,0,0,0,0,0,0,
		 				 0,9,0,0,7,0,0,0,0,0,0,0,0,0,0,0,
						 0,2,1,0,0,0,3,8,0,0,0,0,0,0,0,0,
						 0,0,0,0,4,0,0,5,0,0,0,0,0,0,0,0,
						 5,0,0,7,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,9,0,0,0,0,0,0,0,0,
						 0,6,0,4,5,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
						 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,};
				 

	int init_array[n][n];
	init_array[0][0]=0;
	init_array[0][1]=0;
	init_array[0][2]=0;
	init_array[0][3]=0;
	init_array[1][0]=4;
	init_array[1][1]=0;
	init_array[1][2]=2;
	init_array[1][3]=0;
	init_array[2][0]=2;
	init_array[2][1]=0;
	init_array[2][2]=4;
	init_array[2][3]=3;
	init_array[3][0]=0;
	init_array[3][1]=4;
	init_array[3][2]=1;
	init_array[3][3]=2;
	*/


	


	
		
	// figure out the size of the sub-squares the array consists of
	int CheckSizeOfSquare(int n){
		int i;
		for(i=1;i<10;i++){
			if(i*i == n)
				return(i);
		}
	}
	int size_of_square = CheckSizeOfSquare(n);
	if(debug)
		printf("\n size of squares: %d\n", size_of_square);
	
	
	// check-routines for squares, lines and columns:
	int CheckSquare(int c,int d){
		int square_line;
		int square_column;
		// assign the corresponding line of squares to the line c
		square_line = (int)floor(c/size_of_square);
		// assign the corresponding column of squares to the column d
		square_column = (int)floor(d/size_of_square);
		int i;
		int j;
		for(i=0;i<size_of_square;i++){
			for(j=0;j<size_of_square;j++){
				loop_count++;
				if(!(square_line * size_of_square + i == c && square_column * size_of_square + j == d)){
					if( (array[square_line * size_of_square + i][square_column * size_of_square + j] == array[c][d]) 
						&& (array[square_line * size_of_square + i][square_column * size_of_square + j] != 0) ){
						return(0);
					}
				}
			}		
		}
		return(1);
	}
	
	int CheckLine(c,d){
		int j;
		for(j=0;j<n;j++){
			loop_count++;
			if(j != d){
				if( (array[c][j] == array[c][d]) && (array[c][j] != 0) )
					return(0);
			}
		}
		return(1);
	}
	
	int CheckColumn(c,d){
		int i;
		for(i=0;i<n;i++){
			loop_count++;
			if(i != c){
				if( (array[i][d] == array[c][d]) && (array[i][d] != 0) )
					return(0);
			}
		}
		return(1);
	}
			
	
	
	
	
	void DisplayResult(){    // show final array
		printf("\n");
		printf("\n");
		printf("final array:\n");
		printf("\n");
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				printf(" %d",array[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
	
	
	
	
	// if fill_count runs to n and even n is not a valid number for the current position, FillLatterPosition will
	// step back and try another number for this latter field.
	int FillLatterPosition(int c, int d){
		int var_for_fill_count;
		if(d != 0){
			a = c;
			b = d-1;
			if( (array[a][b] != n) && (position_array[a][b]) ){
				if(debug){
					printf("\n FLP returned 3");
				}
				return(3);
			}
			else{
				if(position_array[a][b]){
					array[a][b] = 0;
					if(debug){
						printf("\n FLP returned 2");
					}
					return(2);
				}
				if(!(position_array[a][b])){
					if(debug){
						printf("\n position_array[%d][%d] is false\n",a,b);
						printf("\n FLP returned 4");
					}
					return(4);
				}
			}
		}
		if(d == 0){
			if(c != 0){
				a = c-1;
				b = n-1;
				if( (array[a][b] != n) && (position_array[a][b]) ){
					if(debug){
						printf("\n FLP returned 3");
					}
					return(3);
				}
				else{
					if(position_array[a][b]){
						array[a][b] = 0;
						if(debug){
							printf("\n FLP returned 2");
						}
						return(2);
					}
					if(!(position_array[a][b])){
						if(debug){
							printf("\n position_array[%d][%d] is false\n",a,b);
							printf("\n FLP returned 4");
						}
						return(4);
					}
				}
			}
			else{
				if(debug){
					printf("FLP returned 5");
				}
				return(5);
			}
		}
	}
	
	
	
	// this function fills the position [c][d] of the array and checks the validity.
	int FillThisPosition(c,d){
		int fill_count;
		for(fill_count=array[c][d]+1;fill_count<=n;fill_count++){
			array[c][d] = fill_count;
			int var_square = CheckSquare(c,d);
			int var_line = CheckLine(c,d);
			int var_column = CheckColumn(c,d);
			if(var_square == 1){
				if(var_line == 1){
					if(var_column == 1){
						array[c][d] = fill_count;
						if(debug){
							printf("\n %d assigned to array[%d][%d]\n",array[c][d],c,d);
						}
						return(1);
					}
					else
						if(debug){
							printf("\n FTP: column failed,  array[%d][%d]: %d \n",c,d,fill_count);
						}
				}
				else
					if(debug){
						printf("\n FTP: line failed,  array[%d][%d]: %d \n",c,d,fill_count);
					}
			}
			else
				if(debug){
					printf("\n FTP: square failed,  array[%d][%d]: %d \n",c,d,fill_count);
				}
		}
		array[c][d] = 0;		
		return(0);
	}
	
	int MainRoutine(i,j){
		if(position_array[i][j]){
			int var_for_FillThisPosition = FillThisPosition(i,j);
			if(var_for_FillThisPosition == 0){
				int var_for_FillLatterPosition = FillLatterPosition(i,j);
				if(var_for_FillLatterPosition == 2)
					return(6);
				if(var_for_FillLatterPosition == 3)
					return(3);
				if(var_for_FillLatterPosition == 4)
					return(4);
				if(var_for_FillLatterPosition == 5)
					return(5);
			}
			if(var_for_FillThisPosition == 1){
				if( (i == n-1) && (j == n-1) )
					return(1);
				else
					return(0);
			}
		}
		else{
			if( (i == n-1) && (j == n-1) )
				return(1);
			else
				return(0);
		}
	}
	
	
	
	
	
	int CallMainRoutine(int i, int j){
		int var_for_MainRoutine = MainRoutine(i,j);
		if(debug){
			printf("\n ########################## MainRoutine returned with %d\n", var_for_MainRoutine);
		}
		if(var_for_MainRoutine == 0){
			return(6);
		}
		if(var_for_MainRoutine == 1){
			return(1);
		}
		if(var_for_MainRoutine == 3){
			if(debug){
				printf("\n a=%d  b=%d\n",a,b);
			}
			return(3);
		}
		if(var_for_MainRoutine == 4){
			return(7);
		}
		if(var_for_MainRoutine == 5){
			if(debug3){
				printf("\n ########################## MainRoutine returned with %d\n  loops: %d", var_for_MainRoutine, loop_count);
			}
			//printf(" \n The initial configuration does not allow any solution! \n");
			return(5);
		}
		if(var_for_MainRoutine == 6){
			return(8);
		}
		
	}
	
	
	
	int CheckInitialArray(int n){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(var_for_idiots == 1)
					return(2);
				int var_square = CheckSquare(i,j);
				int var_line = CheckLine(i,j);
				int var_column = CheckColumn(i,j);
				if( (var_square != 1) || (var_line != 1) || (var_column != 1) ){
					return(0);
				}
				else{
					if((i == n-1) && (j == n-1))
						return(1);
				}
			}
		}
	}
	
	
	

int GlobalStructure(){
	// Check validity of initial array
	int var_for_CheckInitialArray = CheckInitialArray(n);
	if(var_for_CheckInitialArray == 0){
		if(debug3){
			printf("var_for_CheckInitialArray = 0");
		}
		if(var_for_RandomSudoku == 1)
			return(1);
		else
			printf(" \n The initial configuration does not allow any solution! \n");
	}
	if(var_for_CheckInitialArray == 1){
		int k;
		// Main loop of programm:
		for(k=0;k<(n*n);k++){
			if(debug2){
				if(loop_count > 10003660){
					DisplayResult();
					return(0);
				}
			}
			i = (int)floor(k/n);
			j = k-i*n;
			if(debug4){
				if( (i == 1) && (j == 0) && (array[1][0] == 9) && (array[0][7] == 0) ){
					DisplayResult();
					return(0);
				}
				printf("\n i = %d   j = %d \n",i,j);
			}
			if(debug){
				if(loop_count > 9999999)
					printf("CallMainRoutine started with (%d,%d)  -------- number of loops: %d\n",i,j,loop_count);
			}
			int var_for_CallMainRoutine = CallMainRoutine(i,j);
			if(debug5){
				if( (loop_count > 31000) && (loop_count < 32000) ){
					DisplayResult();
					debug = 1;
				}				
			}
			if(debug){
				printf("\n CallMainRoutine returned with %d \n", var_for_CallMainRoutine);
				printf("\n a = %d   b = %d \n",a,b);
			}
			if( (var_for_CallMainRoutine == 3) ){
				k--;
				k--;
			}
			if( (var_for_CallMainRoutine == 7) ){
				if(debug6)
					DisplayResult();
				if(debug){
					printf("\n CallMainRoutine returned with 7\n");
				}
				if(k > 0){
					if( (a == 0) && (b == 0) ){
						if(debug3){
							printf("\n CallMainRoutine returned with %d \n", var_for_CallMainRoutine);
						}
						if(var_for_RandomSudoku == 1)
							return(1);
						else
							printf(" \n The initial configuration does not allow any solution! \n");
						return(0);
					}
					k--;
					k--;
					int r = (int)floor(k/n);
					int s = k-r*n;
					while(position_array[r][s] == 0){
						if(debug){
							printf("\n r = %d   s = %d \n",r,s);
						}
						k--;
						r = (int)floor(k/n);
						s = k-r*n;
						if(debug){
							printf("\n r = %d   s = %d \n",r,s);
						}		
					}
					k--;
				}
				else{
					if( (a == 0) && (b == 0) ){
						if(debug3){
							printf("\n CallMainRoutine returned with %d \n", var_for_CallMainRoutine);
						}
						if(var_for_RandomSudoku == 1)
							return(1);
						else
							printf(" \n The initial configuration does not allow any solution! \n");
					}
					DisplayResult();
					return(0);
				}
			}
			if( (var_for_CallMainRoutine == 8) ){
				if(debug6)
					DisplayResult();
				if(k > 0){
					if( (a == 0) && (b == 0) ){
						if(debug3){
							printf("\n CallMainRoutine returned with %d \n", var_for_CallMainRoutine);
						}
						if(var_for_RandomSudoku == 1)
							return(1);
						else
							printf(" \n The initial configuration does not allow any solution! \n");
						return(0);
					}
					k--; //array[a][b] (=0)
					k--;
					int r = (int)floor(k/n);
					int s = k-r*n;
					while(position_array[r][s] == 0){
						k--;
						r = (int)floor(k/n);
						s = k-r*n;							
					}
					k--;
				}
			}
			if(var_for_CallMainRoutine == 1){
					DisplayResult();
					return(0);
			}
			if(var_for_CallMainRoutine == 5){
					if(var_for_RandomSudoku == 1)
						return(1);
					else
						printf(" \n The initial configuration does not allow any solution! \n");
					return(0);
			}
		}
	}
	if(var_for_CheckInitialArray == 2){
		printf("\n       User fault !!\n\n       Come on, try again, ..... jerk.\n");
	}
}
		






	int RandomSudoku(){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				init_array[i][j] = 0;
			}
		}
		int random_num;
		int count = 0;
		srand(time(NULL));  //starting number for the calculation of all following random numbers
		/*
			for(i=0;i<n;i++){
				j = (int)floor(x/9);
				while(j >= 0){
					random_num = rand()%n;
					if(random_num <= 2){
						init_array[i][random_num] = rand()%n+1;
						count++;
					}
					if(count == x)
						break;
				}
			}
		*/
		/*
			for(i=0;i<n;i++){
				for(j=0;j<n;j++){
					random_num = rand()%(n*n)+1;
					if(random_num <= x){
						init_array[i][j] = rand()%n+1;
						count++;
					}
					if(count == x)
						break;
				}
				if(count == x)
					break;
			}
		*/
			
				for(j=0;j<n;j++){
						init_array[0][j] = rand()%n+1;
						init_array[8][j] = rand()%n+1;
						int var_square = CheckSquare(i,j);
						int var_line = CheckLine(i,j);
						int var_column = CheckColumn(i,j);
						if( (var_square != 1) || (var_line != 1) || (var_column != 1) ){
							init_array[0][j] = 0;
							init_array[8][j] = 0;
						}
						else
							count++;
					if(count == x)
						break;
				}
		
		// save positions of initial numbers of initial array
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(init_array[i][j] == 0)
					position_array[i][j]=1;
				else
					position_array[i][j]=0;
			}
		}
		// never touch the initial array
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				array[i][j]=init_array[i][j];
			}
		}
		return(1);
	}
	

	
	
	
	
	void GenerateInitialArray(){
		int n_square;
		printf("\n    Take Sudoku problem from sudokuin.txt ? (y/n)  ");
		char awnser;
		scanf("%c", &awnser);
		switch(awnser){
			case 'n':
				n_square = n*n;
				printf("\n    How many boxes shall be filled? (0..%d)  ", n_square);
				scanf(" %d", &y);
				var_for_RandomSudoku = RandomSudoku();
				break;
			case 'y':
				input = fopen("c:\\djgpp\\bin\\sudokuin.txt", "r");
				int c = 0;
				int k = 0;
				if(input != NULL){
					for(k = 0;k<(n*n);k++){
						i = (int)floor(k/n);
						j = k-i*n;
						if( j == (n-1) )
							fscanf(input, "%d \n", &c);
						else
							fscanf(input, "%d ", &c);
						init_array[i][j] = c;
					}
				// show initial array
					printf("\n");
					printf("\n");
					printf("initial array:\n");
					printf("\n");
					for(i=0;i<n;i++){
						for(j=0;j<n;j++){
							printf(" %d",init_array[i][j]);
						}
						printf("\n");
					}
					printf("\n");
				// save positions of initial numbers of initial array
					for(i=0;i<n;i++){
						for(j=0;j<n;j++){
							if(init_array[i][j] == 0)
								position_array[i][j]=1;
							else
								position_array[i][j]=0;
						}
					}
				// never touch the initial array
					for(i=0;i<n;i++){
						for(j=0;j<n;j++){
							array[i][j]=init_array[i][j];
						}
					}
				}
				else
					printf("\n\n    Can't read c:/djgpp/bin/sudokuin.txt !\n    Here is one solution of an empty sudoku.");
				fclose(input);
				break;
			default:
				var_for_idiots = 1;
				break;
		}
		return;
	}
	
	
	
	
	
	
	
	
	// whole program:
	int test_count = 1;
	GenerateInitialArray();
	int var_for_GlobalStructure = GlobalStructure();
	//printf("var_for_RandomSudoku = %d", var_for_RandomSudoku);
	//printf("\n GlobalStructure returned with %d\n", var_for_GlobalStructure);
	while(var_for_GlobalStructure == 1){
		test_count++;
		if( (test_count == 5000) || (test_count == 10000) || (test_count == 20000) || (test_count == 50000))
			printf("\n\n number of tested initial configurations: %d", test_count);
		var_for_RandomSudoku = RandomSudoku();
		var_for_GlobalStructure = GlobalStructure();
		//printf("\n GlobalStructure in while-loop returned with %d\n", var_for_GlobalStructure);
	}
	if(var_for_idiots == 0)
		printf("\n number of tests: %d\n\n", loop_count);
	if(var_for_RandomSudoku == 1){
		printf("\n");
		printf("\n");
		printf("initial array:\n");
		printf("\n");
		int random_num;
		int counter = 0;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(counter < y){
					random_num = rand()%1000;
					int store = (int)1000*y/(n*n);
					if(random_num < store){
						counter++;
						printf(" %d",array[i][j]);
					}
					else
						printf(" 0");
				}
				else
					printf(" 0");
			}
			printf("\n");
		}
		printf("\n\n number of tested initial configurations: %d\n", test_count);
		
	}
	return(0);
	
}