数独问题的解决

前些日子,有人网上说解决了什么最难数独什么的，然后下面一片欢呼 — 我看了下所谓题目，无非一个普通的9*9的小题目而已，机器完全可以轻松遍历。感觉很不可思议 — 在这种信息时代，计算机能轻松遍历的东西，就不算什么难题，让人闲暇时候玩玩就算了，拿来当作学术成就什么来炫耀，实在有些。。。坐什么观什么了。

正事做着，debug 很烦恼，所以随便写个数独的解决来调节下身心健康。

数独有规则如下：

9*9 空格中，填入 1~9 这 9 个数字某个

每行，每列的9个数字不可重复。

将 9*9 的区域分为 3*3 个 3*3 格的区域，每个区域内部不可重复

实现如下:

1. 每行不可重复

在初始化的时候，未填写的位置是 0, 所以不会影响到别的数据。

然后就是行坐标不变，列坐标一个一个试探，如果都不相同说明是可以用的。

int Horizontal(int a[9][9],int abscissa,int ordinate,int test)
{
int i;
for(i=0;i<9;i++)
if(a[abscissa][i] == test)return 0;
return 1;
}

2. 每列不可重复

每列不可重复其实和每行不可重复是相似的，只是一个是行坐标不变，一个是列坐标。

int Vertical(int a[9][9],int abscissa,int ordinate,int test)
{
int i;
for(i=0;i<9;i++)
if(a[i][ordinate] == test) return 0;
return 1;
}

3. 小区域不可重复

首先检查待测试的代码所在区域(其实就是横向3个区域，纵向3个区域)。

然后比较和前两个一样。

int Area(int a[9][9],int abscissa,int ordinate,int test)
{
int i,j;
int absMin = (abscissa/3)*3;
int absMax = (abscissa/3+1)*3;
int ordMin = (ordinate/3)*3;
int ordMax = (ordinate/3+1)*3;
for(i=absMin;i<absMax;i++)
for(j=ordMin;j<ordMax;j++)
if(test == a[i][j]) return 0;
return 1;
}

4. 递归试探

传入的是一个已经填写了一半的数组和一个offset，offset的值是0~80共81个，如果超过这个，说明完美完结了，否则继续判断。

如果是非0,则递归自己，填写下个offset，否则从1~9逐个试探是否可以填写。若可以，填写，否则清0本次数据，测试下个。直到可以或者终于确定这条路走不痛，返回是或者否。

inline int AllDone(int a[9][9],int abscissa,int ordinate,int test)
{
if(!Horizontal(a,abscissa,ordinate,test)) return 0;
if(!Vertical(a,abscissa,ordinate,test)) return 0;
if(!Area(a,abscissa,ordinate,test)) return 0;
return 1;
}

int nextData(int a[9][9],int offset)
{
if(offset >= 81) return 1;
int i;
int abs = offset/9;
int ord = offset%9;
if(a[abs][ord]!=0)
{
return nextData(a,offset+1);
}
for(i=1;i<10;i++)
{
if(AllDone(a,abs,ord,i))
{
a[abs][ord] = i;
if(nextData(a,offset+1))
{
return 1;
}
}
a[abs][ord] = 0;
}
return 0;
}

5. 输出

如题。输出就是个简单的控制。

每行输出9个，输出9行即可。

int output(int a[9][9])
{
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return 1;
}

6. main函数

main函数读取9*9个数字，然后递归开搞。

如果无法搞，显示无解，否则显示解。

int main()
{
int a[9][9];
int i;
int j;
memset(a,0,sizeof(a));
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
scanf("%d",&a[i][j]);
}
}
if(nextData(a,0))
{
printf("get result:\n");
output(a);
}else
{
printf("no result.\n");
}
return 0;
}

当然，参数列表什么的，有些没有用到，回头再改，反正不是在做的正事。

输出测试

[yu@argcandargv-com Sudoku]$ make run
INPUT:
0 0 0 0 0 0 4 5 0
0 0 7 0 0 0 3 0 0
1 0 9 0 6 0 0 0 0
3 0 0 0 0 0 0 0 0
5 0 0 4 0 0 0 0 0
0 0 0 0 7 0 0 0 9
0 0 1 2 0 0 0 0 0
0 0 0 3 0 0 0 0 0
0 0 6 0 0 0 0 0 7
OUTPUT:
get result:
8 6 3 7 9 2 4 5 1
2 5 7 1 8 4 3 9 6
1 4 9 5 6 3 8 7 2
3 9 8 6 2 1 7 4 5
5 7 2 4 3 9 6 1 8
6 1 4 8 7 5 2 3 9
9 8 1 2 4 7 5 6 3
7 2 5 3 1 6 9 8 4
4 3 6 9 5 8 1 2 7

CORRECT?

工程位置如下:

Github:https://github.com/yuikns/Sudoku

有人有兴趣，可以拿过去玩玩。

需要说明的是, 这个纯粹是暴力跑. 有很多方法可以很容易优化, 只是没有做而已.

此外, leetcode 有一道题也是讲数独的, 我为此准备了一个解在此处.