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

#define DISPLAY

class cellT {
  private:
  public:
	unsigned char	Tate[9], Yoko[9], Masu[9];
	int				number;
	cellT();
};

cellT::cellT()
{
	int	i;
	for (i = 0; i < 9; i++) Tate[i] = Yoko[i] = Masu[i] = 0;
	number = 0;
}

class SudokuT {
  private:
	cellT	cell[9][9];
	int		mcx(int x, int y, int m);	// cell[x][y]が含まれるマスのm番目cellのx
	int		mcy(int x, int y, int m);	// cell[x][y]が含まれるマスのm番目cellのy
  public:
	void fixed(int x, int y, int num);
	void defixed(int x, int y, int num);
	bool fixable(int x, int y, int z);
	void display(void);
	bool finished(void);
	bool checkNext(void);
	bool estimation(void);	// 再帰呼び出し
};

// このマスにこの数字(z = number - 1)を入れることは可能か？
bool SudokuT::fixable(int x, int y, int z)
{
	if ((cell[x][y].Tate[z] == 0) &&
		(cell[x][y].Yoko[z] == 0) &&
		(cell[x][y].Masu[z] == 0)) return true;
	return false;
}

bool SudokuT::estimation(void)
{
	int		x, y, z, num;
	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			if (cell[x][y].number > 0) continue;
			for (z = 0; z < 9; z++) {
				if (fixable(x, y, z)) {
#ifndef NODISPLAY
					printf("[%d, %d]を%dにしてみる\n", x + 1, y + 1, z + 1);
#endif
					fixed(x, y, z + 1);
					if (estimation() == true) return true;
#ifndef NODISPLAY
					printf("[%d, %d]は%dではなさそう\n", x + 1, y + 1, z + 1);
#endif
					defixed(x, y, z + 1);
				}
			}
			return false;
		}
	}
	if (finished()) return true;
	return false;
}


bool SudokuT::finished(void)
{
	int		x, y, m, num;
	// とりあえず全て埋まっている？（冗長）
	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			if (cell[x][y].number == 0) return false;
		}
	}
	// 縦チェック
	for (x = 0; x < 9; x++) {
		for (num = 1; num <= 9; num++) {
			bool flag = false;
			for (y = 0; y < 9; y++) if (cell[x][y].number == num) flag = true;
			if (!flag) return false;
		}
	}
	// 横チェック
	for (y = 0; y < 9; y++) {
		for (num = 1; num <= 9; num++) {
			bool flag = false;
			for (x = 0; x < 9; x++) if (cell[x][y].number == num) flag = true;
			if (!flag) return false;
		}
	}
	// マスチェック
	for (x = 0; x < 9; x += 3) {
		for (y = 0; y < 9; y += 3) {
			for (num = 1; num <= 9; num++) {
				bool flag = false;
				for (m = 0; m < 9; m++) if (cell[mcx(x, y, m)][mcy(x, y, m)].number == num) flag = true;
				if (!flag) return false;
			}
		}
	}
	return true;
}


int SudokuT::mcx(int x, int y, int m)
{
	// 左上のアドレス
	x = (x / 3) * 3;
	y = (y / 3) * 3;
	// そこから算出
	x += m % 3;
	y += m / 3;
	return x;
}

int SudokuT::mcy(int x, int y, int m)
{
	// 左上のアドレス
	x = (x / 3) * 3;
	y = (y / 3) * 3;
	// そこから算出
	x += m % 3;
	y += m / 3;
	return y;
}

void SudokuT::display(void)
{
	int	x, y;
	printf("+-+-+-+-+-+-+-+-+-+\n");
	for (y = 0; y < 9; y++) {
		for (x = 0; x < 9; x++) {
			if (cell[x][y].number == 0)	printf("| ");
			  else						printf("|%d", cell[x][y].number);
		}
		printf("|\n");
		if ((y == 2) || (y == 5) || (y == 8)) printf("+-+-+-+-+-+-+-+-+-+\n");
	}
}

void SudokuT::fixed(int x, int y, int num)
{
	int		tate, yoko, masu;
	if (cell[x][y].number != 0) {
		printf("Error: Already fixed here! [%d, %d] = %d -> %d\n", x + 1, y + 1, cell[x][y].number, num);
		exit(1);
	}
	cell[x][y].number = num;
	for (tate = 0; tate < 9; tate++) cell[x][tate].Tate[num -1] = 1;
	for (yoko = 0; yoko < 9; yoko++) cell[yoko][y].Yoko[num -1] = 1;
	for (masu = 0; masu < 9; masu++) cell[mcx(x, y, masu)][mcy(x, y, masu)].Masu[num - 1] = 1;
#ifndef NODISPLAY
	display();
#endif
}

void SudokuT::defixed(int x, int y, int num)
{
	int		tate, yoko, masu;
	cell[x][y].number = 0;
	for (tate = 0; tate < 9; tate++) cell[x][tate].Tate[num -1] = 0;
	for (yoko = 0; yoko < 9; yoko++) cell[yoko][y].Yoko[num -1] = 0;
	for (masu = 0; masu < 9; masu++) cell[mcx(x, y, masu)][mcy(x, y, masu)].Masu[num - 1] = 0;
#ifndef NODISPLAY
	display();
#endif
}

bool SudokuT::checkNext(void)
{
	bool 	flag = false;
	int		x, y, z, number;
	for (y = 0; y < 9; y++) {
		for (x = 0; x < 9; x++) {
			int	cnt;
			if (cell[x][y].number > 0) continue;
			for (z = cnt = 0; z < 9; z++) {
				if ((cell[x][y].Tate[z] == 0) &&
					(cell[x][y].Yoko[z] == 0) &&
					(cell[x][y].Masu[z] == 0)) {
					number = z + 1;
					cnt++;
				}
			}
			if (cnt == 1) {
				printf("[%d, %d]は%d\n", x + 1, y + 1, number);
				fixed(x, y, number);
				flag = true;
			}
		}
	}
	return flag;
}

void main (void)
{
	SudokuT		Sudoku;
	FILE		*fp;

	// 初期設定値読み込み
	printf("---Start---\n");
	if ((fp = fopen("initial.csv", "rt")) == NULL) exit(1);
	printf("---Loading initial.csv---\n");
	while (!feof(fp)) {
		char 	str[128];
		int		x, y, z, ptr;
		for (y = 0; y < 9; y++) {
			if (fgets(str, 127, fp) == NULL) break;
			for (x = 0, ptr = 0; x < 9; x++) {
				if (str[ptr] == ',') {
					ptr++;
					continue;
				}
				z = str[ptr++] - '0';
				if ((z > 0) && (z <= 9)) Sudoku.fixed(x , y, z);
				ptr++;
			}
		}
	}
	printf("---Loading finished---\n");
	fclose(fp);
	printf("---CheckDefaultFixedNumber---\n");
	while (Sudoku.checkNext());
	printf("---DefalutFixedNumber finished---\n");
	if (!Sudoku.finished()) {
		Sudoku.display();
		printf("Push any key to estimate blank cells\n");
		getch();
		printf("---EstimationStart----\n");
		Sudoku.estimation();
		printf("---EstimationFinished----\n");
	}
	if (Sudoku.finished()) {
		printf("Final check is passed.\n");
		Sudoku.display();
	} else {
		printf("NO RESULT!!!!\n");
	}
	getch();
}