数独解题

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

//这是数独的题目
const int a_title[9][9] = {
	0,0,0, 0,5,0, 6,0,0,
	0,8,1, 0,6,0, 0,0,3,
	3,0,0, 2,0,8, 4,0,0,
	0,0,2, 6,0,0, 0,9,0,
	0,1,0, 0,8,0, 0,4,7,
	0,0,0, 5,0,3, 0,0,6,
	0,0,6, 0,7,0, 0,1,0,
	0,0,4, 0,0,0, 0,0,0,
	0,0,0, 0,3,0, 9,0,0,
};

//计算用数独的结果
int a[9][9];

//检测dat这个数值,符合不符合数独的行列要求
int check(int x, int y, int dat)
{
	int i;
	for (i=0; i<9; i++) {
		if (a[x][i] == dat || a[i][y] == dat) {
			return 0;
		}
	}
	return 1;
}

/* 获得比check_dat大的,下一个符合3*3要求的值
 * 也就是3*3里面没填写部分,比check_dat大的数值
 */ 
int get_3_3_dat(int x, int y, int dat)
{
	int i, j;

	x = x / 3 * 3;
	y = y / 3 * 3;

__start:
	if (++dat > 9) {
		return 0;
	}

	for (i=0; i<3; i++) {
		for (j=0; j<3; j++) {
			if (a[x+i][y+j] == dat) {
				goto __start;
			}
		}
	}

	return dat;
}

//打印计算好的数独结果
void display(void)
{
	int x, y;

	for (x=0; x<9; x++) {
		for (y=0; y<9; y++) {
			printf("%d,", a[x][y]);
		}
		printf("\n");
	}
}

int sudoku_calc(int start_x, int start_y)
{
	int x, y, dat = 0;

	y = start_y;
	for (x = start_x; x<9; x++) {
		for (; y<9; y++) {
			if (a[x][y] == 0) {						//=0表示需要添入
				while (dat < 9) {					//检测上次添入的数是否小于9
					a[x][y] = 0;					//这个位置是要添入的位置,先清楚掉
					dat = get_3_3_dat(x, y, dat);	//找个3*3能添入的数据
					if (dat == 0) {					//=0说明没有找到
						a[x][y] = 0;
						return 0;					//返回填写失败
					}

					if (check(x, y, dat) == 0) {	//检测找出来的值,满足不满足横纵向要求
						continue;					//不满足,需要在3*3里面找到下一个可以添入的,重新计算
					}

					a[x][y] = dat;					//总算知道正确的了,添入表格中
					
					if (sudoku_calc(x, y)) {		//查找下一个位置,可以添入的
						return 1;					//后续的添入成功,返回当前填写成功
					}
				}
				a[x][y] = 0;
				return 0;							//所有数字都添入失败,所以返回添入失败
			}		
		}
		y = 0;
	}
	return 1;
}

int main(void)
{
	memcpy(a, a_title, sizeof(a));
	sudoku_calc(0, 0);
	display();
}