#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

char error[114] = "";
void print(int a[9][9]) {
	
	int i,j;
	for(i=0; i<=9; i++) {
		if(i%3 == 0)
			printf("|-----------------------|\n");
		if(i >= 9) break;
		printf("| ");
		for(j=0; j<9; j++) {
			if(a[i][j] > 0)
				printf("%d ",a[i][j]);
			else printf(". ");
			if((j+1)%3 == 0)
				printf("| ");
		}
		printf("\n");
	}
}

void generate(int a[9][9]) {
	memset(a, 0, sizeof(int) * 81);
	
	int i;
	int x,y,z;
	int t[10];
	for(i = 0; i < 9; i++) {
		if(i%3 == 0)
			memset(t, 0, sizeof(t));
		x = rand() % 9;
		do {
			y = rand() % 9;
		}while(x == y);
		do {
			z = rand() % 9;
		}while(x == z || y == z);
		do {
			a[i][x] = rand() % 9 + 1;
		}while(t[a[i][x]]);
		t[a[i][x]] = 1;
		do {
			a[i][y] = rand() % 9 + 1;
		}while(t[a[i][y]]);
		t[a[i][y]] = 1;
		do {
			a[i][z] = rand() % 9 + 1;
		}while(t[a[i][z]]);
		t[a[i][z]] = 1;
	}
	
}

int isSudoku(int a[9][9], const char* error) {
	int t[10], i, j, x, y, sx, sy;
	
	for(i=0; i<9; i++) {
		memset(t, 0, sizeof(t));
		for(j=0; j<9; j++) {
			if(t[a[i][j]]) {
				sprintf(error, "The number %d in the row %d has been used!\n",
					a[i][j], i+1);
				return 0;
			}
			t[a[i][j]] = 1;
			t[0] = 0;
		}
	}
	
	for(j=0; j<9; j++) {
		memset(t, 0, sizeof(t));
		for(i=0; i<9; i++) {
			if(t[a[i][j]]) {
				sprintf(error, "The number %d in the col %d has been used!\n",
					a[i][j], j+1);
				return 0;
			}
			t[a[i][j]] = 1;
			t[0] = 0;
		}
	}
	
	for(x=0; x<2; x++)
	for(y=0; y<2; y++) {
		memset(t, 0, sizeof(t));
		sx = x*3; sy = y*3;
		for(i=sx; i<sx+3; i++)
		for(j=sy; j<sy+3; j++) {
			if(t[a[i][j]]) {
				sprintf(error, "The number %d in the block %d has been used!\n",
					a[i][j], x*3+y+1);
				return 0;
			}
			t[a[i][j]] = 1;
			t[0] = 0;
		}
	}
	
	return 1;
}

int _solve(int* it, int a[9][9]) {
//	printf("%d\n", (void*)it - (void*)a);
	int k; int* next = it;
	
	if(it >= (int*)a + 81) return 1;
	
	do {
		next++;
	}
	while(*next > 0);
			
	for(k=1; k<=9; k++) {
		*it = k;
		if(isSudoku(a,error)) {
//			print(a);
			if(_solve(next, a)) // call stack
				return 1;
		}
	}
	// erase
	*it = 0;
	return 0;
}

int solve(int a[9][9]) {
	int* it = a;
	while(*it > 0)
		it++;
	return _solve(it, a);
}

int main() {
	srand(time(0));
	int a[9][9] = {{5, 3, 0, 0, 7, 0, 0, 0, 0}, 
{6, 0, 0, 1, 9, 5, 0, 0, 0}, 
{0, 9, 8, 0, 0, 0, 0, 6, 0}, 
{8, 0, 0, 0, 6, 0, 0, 0, 3}, 
{4, 0, 0, 8, 0, 3, 0, 0, 1}, 
{7, 0, 0, 0, 2, 0, 0, 0, 6}, 
{0, 6, 0, 0, 0, 0, 2, 8, 0}, 
{0, 0, 0, 4, 1, 9, 0, 0, 5}, 
{0, 0, 0, 0, 8, 0, 0, 7, 9}};
//	generate(a);
	
	int valid = isSudoku(a, error);
	
	printf("The original Sudoku matrix:\n");
	print(a);
	
	if(valid) {
		printf("True:Valid initial Sudoku matrix!\n");
	}
	else {
		printf("False:Invalid initial Sudoku matrix!\n      %s", error);
	}
	
	if(valid && solve(a)) {
		printf("The solution of Sudoku matrix:\n");
		print(a);
	}
	else {
		printf("No solution!");
	}
}