我们知道,每个宫内必须包含数字9,第1宫以及第3宫中都包含数字9,并且第1宫的9位于第3行。
第3宫的9位于第2行,这也就意味着第2宫的9不能在第2行和第3行,所有第2宫的9只能放置在第2宫第1行的空格内。
2.双向扫看法:同样的技巧也可以扩展到相互垂直的行与列中。让我们想一下第3宫中1应该放在哪里。在这个例子中,第1行以及第2行已经有1了,那么第3宫中只有底部的俩个空格可以填1。不过,方格g4已经有1了,所有第g列不能再有1。
所以i3是该宫唯一符合条件填上数字1的地方。
3.寻找候选法:通常地,一个方格只能有一个数字的可能性,因为剩下的其他8个数字都已经被相关的行列宫所排除了。我们看一下下面例子中b4这个方格。b4所在的宫中已经存在了数字3,4,7,8,1和6位于同一行,5和9位于同一列,排除上述所有数字,b4只能填上2。
4数字排除法:排除法是一个相对繁杂的寻找数字的方法。我们可以从c8中的1间接推出e7和e9必须包含数字1,不管这个1在哪个方格,我们可以确认的是,第e列的数字1肯定在第8宫内,所以第2宫内中间这一列就不可能存在数字1。因此,第2宫的数字一必须填在d2处。
一、步骤:
1.对每一个空格,根据规则推断它可能填入的数字,并存储它的所有可能值;
2.根据可能值的个数,确定填写的顺序。比如说,有些空格只有一种可能,那必然是正确的结果,首先填入。
3.将所有只有一种可能的空格填写完毕以后,回到步骤1,重新确定剩下空格的可能值;
4.当没有只有一种可能的空格时(即每个空格都有两种以上可能),按照可能值个数从小到大的顺序,使用深度(广度)优先搜索,完成剩下空格。
二、例程:
#include <windows.h>#include <stdio.h>
#include <time.h>
char sd[81]
bool isok = false
//显示数独
void show()
{
if (isok) puts("求解完成")
else puts("初始化完成")
for (int i = 0 i < 81 i++)
{
putchar(sd[i] + '0')
if ((i + 1) % 9 == 0) putchar('\n')
}
putchar('\n')
}
//读取数独
bool Init()
{
FILE *fp = fopen("in.txt", "rb")
if (fp == NULL) return false
fread(sd, 81, 1, fp)
fclose(fp)
for (int i = 0 i < 81 i++)
{
if (sd[i] >= '1' && sd[i] <= '9') sd[i] -= '0'
else sd[i] = 0
}
show()
return true
}
//递归解决数独
void force(int k)
{
if (isok) return
if (!sd[k])
{
for (int m = 1 m <= 9 m++)
{
bool mm = true
for (int n = 0 n < 9 n++)
{
if ((m == sd[k/27*27+(k%9/3)*3+n+n/3*6]) || (m == sd[9*n+k%9]) || (m == sd[k/9*9+n]))
{
mm = false
break
}
}
if (mm)
{
sd[k] = m
if (k == 80)
{
isok = true
show()
return
}
force(k + 1)
}
}
sd[k] = 0
}
else
{
if (k == 80)
{
isok = true
show()
return
}
force(k + 1)
}
}
int main()
{
system("CLS")
if (Init())
{
double start = clock()
force(0)
printf("耗时%.0fms", clock() - start)
}
else puts("初始化错误")
getchar()
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)