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

#define MATRIX_ROW (3)
#define MATRIX_COLUMN (3)
#define NUMBER_OF_ROW (9)
#define NUMBER_OF_COLUMN (9)
#define NUMBER_OF_ELEMENTS (9)

typedef struct _SUDOKU_CELL
{
	int current;
	int nCandidates;
	int candidates[NUMBER_OF_ELEMENTS + 1];
} SUDOKU_CELL;

typedef struct _SUDOKU_PLANE
{
	int unsolved;
	SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN];
} SUDOKU_PLANE;

void Reset_SudokuPlane(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0,k = 0;
	memset(plane,0,sizeof(SUDOKU_PLANE));
	plane->unsolved = NUMBER_OF_ELEMENTS * NUMBER_OF_ELEMENTS;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			plane->cell[i][j].nCandidates = NUMBER_OF_ELEMENTS;
			for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
			{
				plane->cell[i][j].candidates[k] = 1;
			}
		}
	}
	return;
}

void Input_SudokuCell(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int rIndex,int cIndex,int n)
{
	int i = 0,j = 0;
	int rBase = 0,cBase = 0;
	if (cell[rIndex][cIndex].current || n == 0)
		return;
	rBase = MATRIX_ROW * (rIndex / MATRIX_ROW);
	cBase = MATRIX_COLUMN * (cIndex / MATRIX_COLUMN);
	cell[rIndex][cIndex].current = n;
	cell[rIndex][cIndex].nCandidates = 1;
	memset(cell[rIndex][cIndex].candidates,0,sizeof(int)*(NUMBER_OF_ELEMENTS + 1));
	cell[rIndex][cIndex].candidates[n] = 1;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		if (i == rIndex)
			continue;
		if (cell[i][cIndex].candidates[n])
		{
			cell[i][cIndex].candidates[n] = 0;
			cell[i][cIndex].nCandidates -= 1;
		}
	}
	for(i = 0;i < NUMBER_OF_COLUMN;++i)
	{
		if (i == cIndex)
			continue;
		if (cell[rIndex][i].candidates[n])
		{
			cell[rIndex][i].candidates[n] = 0;
			cell[rIndex][i].nCandidates -= 1;
		}
	}
	for(i = 0;i < MATRIX_ROW;++i)
	{
		for(j = 0;j < MATRIX_COLUMN;++j)
		{
			if (((rBase + i) == rIndex) && ((cBase + j) == cIndex))
				continue;
			if (cell[rBase + i][cBase + j].candidates[n])
			{
				cell[rBase + i][cBase + j].candidates[n] = 0;
				cell[rBase + i][cBase + j].nCandidates -= 1;
			}
		}
	}
	return;
}

void Input_SudokuPlane(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0;
	int cnt = 0;
	int n[NUMBER_OF_COLUMN] = {0};
	static char * const format = "%d,%d,%d,%d,%d,%d,%d,%d,%d";
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		cnt +=
		fscanf(
		stdin,
		format,
		&n[0],
		&n[1],
		&n[2],
		&n[3],
		&n[4],
		&n[5],
		&n[6],
		&n[7],
		&n[8]);
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			if (n[j])
			{
				Input_SudokuCell(plane->cell,i,j,n[j]);
				plane->unsolved -= 1;
			}
		}
	}
	return;
}

void Show_SudokuPlane(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0,k = 0;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		fprintf(stdout,"\n");
		if (i % MATRIX_ROW == 0)
		{
			fprintf(stdout,"+");
			for(k = 0;k < (NUMBER_OF_COLUMN/MATRIX_COLUMN);++k)
			{
				for(j = 0;j < MATRIX_COLUMN;++j)
					fprintf(stdout,"---");
				fprintf(stdout,"+");
			}
			fprintf(stdout,"\n");
		}
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			if (j == 0)
				fprintf(stdout,"|");
			if (plane->cell[i][j].current)
				fprintf(stdout," %d ",plane->cell[i][j]);
			else
				fprintf(stdout,"   ");
			if ((j + 1) % MATRIX_COLUMN == 0)
				fprintf(stdout,"|");
		}
	}
	fprintf(stdout,"\n");
	fprintf(stdout,"+");
	for(k = 0;k < (NUMBER_OF_COLUMN/MATRIX_COLUMN);++k)
	{
		for(j = 0;j < MATRIX_COLUMN;++j)
			fprintf(stdout,"---");
		fprintf(stdout,"+");
	}
	fprintf(stdout,"\n");
	return;
}

int method1(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0,k = 0;
	int n = 0;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			if (plane->cell[i][j].current == 0 && plane->cell[i][j].nCandidates == 1)
			{
				++n;
				for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
				{
					if (plane->cell[i][j].candidates[k])
					{
						Input_SudokuCell(plane->cell,i,j,k);
						plane->unsolved -= 1;
						break;
					}
				}
			}
		}
	}
	return n;
}

int find_cell_with_value(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int rIndex,int cIndex,int n,int left,int top,int width,int height,int *row,int *col)
{
	int i = 0,j = 0;
	int find = 0;
	for(i = 0;i < height;++i)
	{
		for(j = 0;j < width;++j)
		{
			if (((top + i) == rIndex) && ((left + j) == cIndex))
				continue;
			if (cell[top + i][left + j].current == 0 && cell[top + i][left + j].candidates[n])
			{
				find = 1;
				if (row)
					*row = top + i;
				if (col)
					*col = left + j;
				goto _find;
			}
		}
	}
_find:
	return find;
}

int method2(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0,k = 0;
	int n = 0;
	int rBase = 0,cBase = 0;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			rBase = MATRIX_ROW * (i / MATRIX_ROW);
			cBase = MATRIX_COLUMN * (j / MATRIX_COLUMN);
			if (plane->cell[i][j].current == 0)
			{
				for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
				{
					if (plane->cell[i][j].candidates[k])
					{
						if (!find_cell_with_value(plane->cell,i,j,k,0,i,NUMBER_OF_COLUMN,1,NULL,NULL))
						{
							++n;
							Input_SudokuCell(plane->cell,i,j,k);
							plane->unsolved -= 1;
							break;
						}
						else if (!find_cell_with_value(plane->cell,i,j,k,j,0,1,NUMBER_OF_ROW,NULL,NULL))
						{
							++n;
							Input_SudokuCell(plane->cell,i,j,k);
							plane->unsolved -= 1;
							break;
						}
						else if (!find_cell_with_value(plane->cell,i,j,k,cBase,rBase,MATRIX_COLUMN,MATRIX_ROW,NULL,NULL))
						{
							++n;
							Input_SudokuCell(plane->cell,i,j,k);
							plane->unsolved -= 1;
							break;
						}
					}
				}
			}
		}
	}
	return n;
}

int find_nset(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int rIndex,int cIndex,int left,int top,int width,int height,char f[NUMBER_OF_ROW][NUMBER_OF_COLUMN])
{
	int i = 0,j = 0;
	int n = 0;
	memset(f,0,sizeof(char)*(NUMBER_OF_ROW * NUMBER_OF_COLUMN));
	for(i = 0;i < height;i++)
	{
		for(j = 0;j < width;++j)
		{
			if (((top + i) == rIndex) && ((left + j) == cIndex))
				continue;
			if (cell[top + i][left + j].current == 0 &&
				!memcmp(cell[rIndex][cIndex].candidates,cell[top + i][left + j].candidates,sizeof(int)*(NUMBER_OF_ELEMENTS + 1)))
			{
				++n;
				f[top + i][left + j] = 1;
			}
		}
	}
	++n;
	return n;
}

int method3(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0,k = 0,l = 0,m = 0;
	int rBase = 0,cBase = 0;
	int n = 0;
	char f[NUMBER_OF_ROW][NUMBER_OF_COLUMN] = {0};
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		for(j = 0;j < NUMBER_OF_COLUMN;++j)
		{
			rBase = MATRIX_ROW * (i / MATRIX_ROW);
			cBase = MATRIX_COLUMN * (j / MATRIX_COLUMN);
			if (plane->cell[i][j].current == 0)
			{
				if (plane->cell[i][j].nCandidates == find_nset(plane->cell,i,j,0,i,NUMBER_OF_COLUMN,1,f))
				{
					++n;
					for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
					{
						if (plane->cell[i][j].candidates[k])
						{
							for(l = 0;l < NUMBER_OF_COLUMN;++l)
							{
								if (l == j)
									continue;
								if (!f[i][l] && plane->cell[i][l].candidates[k])
								{
									plane->cell[i][l].candidates[k] = 0;
									plane->cell[i][l].nCandidates -= 1;
								}
							}
						}
					}
				}
				if (plane->cell[i][j].nCandidates == find_nset(plane->cell,i,j,j,0,1,NUMBER_OF_ROW,f))
				{
					++n;
					for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
					{
						if (plane->cell[i][j].candidates[k])
						{
							for(l = 0;l < NUMBER_OF_ROW;++l)
							{
								if (l == i)
									continue;
								if (!f[l][j] && plane->cell[l][j].candidates[k])
								{
									plane->cell[l][j].candidates[k] = 0;
									plane->cell[l][j].nCandidates -= 1;
								}
							}
						}
					}
				}
				if (plane->cell[i][j].nCandidates == find_nset(plane->cell,i,j,cBase,rBase,MATRIX_COLUMN,MATRIX_ROW,f))
				{
					++n;
					for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
					{
						if (plane->cell[i][j].candidates[k])
						{
							for(l = 0;l < MATRIX_ROW;++l)
							{
								for(m = 0;m < MATRIX_COLUMN;++m)
								{
									if (((rBase + l) == i) && ((cBase + m) == j))
										continue;
									if (!f[rBase + l][cBase + m] && plane->cell[rBase + l][cBase + m].candidates[k])
									{
										plane->cell[rBase + l][cBase + m].candidates[k] = 0;
										plane->cell[rBase + l][cBase + m].nCandidates -= 1;
									}
								}
							}
						}
					}
				}
			}
		}
	}
	return n;
}

int method4_sub1(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int rIndex)
{
	int i = 0,j = 0,k = 0;
	int rBase = 0,cBase = 0;
	int n = 0;
	const int nBlock = (NUMBER_OF_ROW / MATRIX_ROW) * (NUMBER_OF_COLUMN / MATRIX_COLUMN);
	int nHitBlock = 0;
	int block[(NUMBER_OF_ROW / MATRIX_ROW) * (NUMBER_OF_COLUMN / MATRIX_COLUMN)] = {0};
	for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
	{
		nHitBlock = 0;
		memset(block,0,sizeof(int)*nBlock);
		for(i = 0;i < NUMBER_OF_COLUMN;++i)
		{
			if (cell[rIndex][i].current == 0 && cell[rIndex][i].candidates[k])
			{
				if (block[MATRIX_ROW*(rIndex / MATRIX_ROW) + (i / MATRIX_COLUMN)] == 0)
					block[MATRIX_ROW*(rIndex / MATRIX_ROW) + (i / MATRIX_COLUMN)] += 1;
			}
		}
		for(i = 0; i< nBlock;++i)
			nHitBlock += block[i];
		if (nHitBlock == 1)
		{
			for(i = 0;i < nBlock;++i)
			{
				if (block[i])
				{
					rBase = MATRIX_ROW * (i / MATRIX_ROW);
					cBase = MATRIX_COLUMN * (i % MATRIX_ROW);
					for(i = 0;i < MATRIX_ROW;++i)
					{
						for(j = 0;j < MATRIX_COLUMN;++j)
						{
							if ((rBase + i) == rIndex)
								continue;
							if (cell[rBase + i][cBase + j].current == 0 &&
								cell[rBase + i][cBase + j].candidates[k])
							{
								++n;
								cell[rBase + i][cBase + j].candidates[k] = 0;
								cell[rBase + i][cBase + j].nCandidates -= 1;
							}
						}
					}
					break;
				}
			}
		}
	}
	return n;
}

int method4_sub2(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int cIndex)
{
	int i = 0,j = 0,k = 0;
	int rBase = 0,cBase = 0;
	int n = 0;
	const int nBlock = (NUMBER_OF_ROW / MATRIX_ROW) * (NUMBER_OF_COLUMN / MATRIX_COLUMN);
	int block[(NUMBER_OF_ROW / MATRIX_ROW) * (NUMBER_OF_COLUMN / MATRIX_COLUMN)] = {0};
	int nHitBlock = 0;
	for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
	{
		nHitBlock = 0;
		memset(block,0,sizeof(int)*nBlock);
		for(i = 0;i < NUMBER_OF_ROW;++i)
		{
			if (cell[i][cIndex].current == 0 && cell[i][cIndex].candidates[k])
			{
				if (block[MATRIX_ROW*(i / MATRIX_ROW) + (cIndex / MATRIX_COLUMN)] == 0)
					block[MATRIX_ROW*(i / MATRIX_ROW) + (cIndex / MATRIX_COLUMN)] += 1;
			}
		}
		for(i = 0;i < nBlock;++i)
		{
			nHitBlock += block[i];
		}
		if (nHitBlock == 1)
		{
			for(i = 0;i < nBlock;++i)
			{
				if (block[i])
				{
					rBase = MATRIX_ROW * (i / MATRIX_ROW);
					cBase = MATRIX_COLUMN * (i % MATRIX_ROW);
					for(i = 0;i < MATRIX_ROW;++i)
					{
						for(j = 0;j < MATRIX_COLUMN;++j)
						{
							if ((cBase + j) == cIndex)
								continue;
							if (cell[rBase + i][cBase + j].current == 0 &&
								cell[rBase + i][cBase + j].candidates[k])
							{
								++n;
								cell[rBase + i][cBase + j].candidates[k] = 0;
								cell[rBase + i][cBase + j].nCandidates -= 1;
							}
						}
					}
					break;
				}
			}
		}
	}
	return n;
}

int method4_sub3(SUDOKU_CELL cell[NUMBER_OF_ROW][NUMBER_OF_COLUMN],int rIndex,int cIndex)
{
	int i = 0,j = 0,k = 0;
	int rBase = 0,cBase = 0;
	int n = 0;
	int row[NUMBER_OF_ROW] = {0};
	int column[NUMBER_OF_COLUMN] = {0};
	int nHitRow = 0;
	int nHitColumn = 0;
	for(k = 1;k <= NUMBER_OF_ELEMENTS;++k)
	{
		nHitRow = 0;
		nHitColumn = 0;
		memset(row,0,sizeof(row));
		memset(column,0,sizeof(column));
		rBase = MATRIX_ROW * (rIndex / MATRIX_ROW);
		cBase = MATRIX_COLUMN * (cIndex / MATRIX_COLUMN);
		for(i = 0;i < MATRIX_ROW;++i)
		{
			for(j = 0;j < MATRIX_COLUMN;++j)
			{
				if (cell[rBase + i][cBase + j].current == 0 &&
					cell[rBase + i][cBase + j].candidates[k])
				{
					if (row[rBase + i] == 0)
					{
						row[rBase + i] += 1;
					}
					if (column[cBase + j] == 0)
					{
						column[cBase + j] += 1;
					}
				}
			}
		}
		for(i = 0;i < NUMBER_OF_ROW;++i)
			nHitRow += row[i];
		for(i = 0;i < NUMBER_OF_COLUMN;++i)
			nHitColumn += column[i];
		if (nHitRow == 1)
		{
			for(i = 0;i < NUMBER_OF_ROW;++i)
			{
				if (row[i])
				{
					for(j = 0;j < NUMBER_OF_COLUMN;++j)
					{
						if (cBase <= j && j < (cBase + MATRIX_COLUMN))
							continue;
						if (cell[i][j].current == 0 && cell[i][j].candidates[k])
						{
							++n;
							cell[i][j].candidates[k] = 0;
							cell[i][j].nCandidates -= 1;
						}
					}
					break;
				}
			}
		}
		else if (nHitColumn == 1)
		{
			for(j = 0;j < NUMBER_OF_COLUMN;++j)
			{
				if (column[j])
				{
					for(i = 0;i < NUMBER_OF_ROW;++i)
					{
						if (rBase <= i && i < (rBase + MATRIX_ROW))
							continue;
						if (cell[i][j].current == 0 && cell[i][j].candidates[k])
						{
							++n;
							cell[i][j].candidates[k] = 0;
							cell[i][j].nCandidates -= 1;
						}
					}
					break;
				}
			}
		}
	}
	return n;
}

int method4(SUDOKU_PLANE *plane)
{
	int i = 0,j = 0;
	int n = 0;
	for(i = 0;i < NUMBER_OF_ROW;++i)
	{
		n += method4_sub1(plane->cell,i);
	}
	for(i = 0;i < NUMBER_OF_COLUMN;++i)
	{
		n += method4_sub2(plane->cell,i);
	}
	for(i = 0;i < MATRIX_ROW;++i)
	{
		for(j = 0;j < MATRIX_COLUMN;++j)
		{
			n += method4_sub3(plane->cell,MATRIX_ROW*i,MATRIX_COLUMN*j);
		}
	}
	return n;
}

int Solve_SudokuPlane(SUDOKU_PLANE *plane)
{
	int cnt = 0;
	while(plane->unsolved)
	{
		for(;;)
		{
			if (!method1(plane))
				break;
		}
		for(;;)
		{
			if (!method2(plane))
				break;
		}
		method3(plane);
		method4(plane);
		if (++cnt > 800)
			break;
	}
	return (plane->unsolved == 0);
}

int isSolved(SUDOKU_PLANE *plane)
{
	return (plane->unsolved == 0);
}

int main(int argc,char **argv)
{
	SUDOKU_PLANE plane;
	Reset_SudokuPlane(&plane);
	Input_SudokuPlane(&plane);
	Show_SudokuPlane(&plane);
	fprintf(stdout,"Thinking... Please wait...\n");
	Solve_SudokuPlane(&plane);
	Show_SudokuPlane(&plane);
	if (!isSolved(&plane))
	{
		fprintf(stdout,"Sorry but, I cannot solve this Sudoku...\n");
		fprintf(stdout,"It is difficult for me to solve this Sudoku !\n");
	}
	return 0;
}