Question

C语言怎么实现解决一个数独啊~~菜鸟求C语言大神给代码和思路><~~好的给追加分!!

C语言怎么实现解决一个数独...
我的思路是先定义一个数组
然后81个循环改变每个变量的值= =
当然我觉得这个执行肯定太慢……跪求解~

Answer 1

这是用递归方法写的代码
摘自http://blog.sina.com.cn/s/blog_61c5b01f0100nrta.html
我测试过一些案例
初始数据必须是正确的，一些极端情况会卡很久才有结果
一般能够很快给出所有解
#include<stdio.h>

int result=0; //结果数

int main()
{
int a[9][9];
void Sudoku(int a[9][9],int n);
printf("请输入数独中的原始数据，没有数据的用0代替。\n");
for(int i=0;i<9;i++)
{
printf("请输入第%d行的9个数：",i+1);
for(int j=0;j<9;j++)
scanf("%d",&a[i][j]);
}
printf("数独的解为：\n\n");
Sudoku(a,0);
if(result==0)
printf("此数独无解!");
return 0;
}

//输出可行的解
void print(int a[9][9])
{
result++;
printf("第%d个填法为：\n",result);
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
printf("%d ",a[i][j]);
if((j==2)||(j==5))
printf(" ");
}
printf("\n");
if((i==2)||(i==5))
printf("\n");
}
printf("\n");
}

//判断是否可以将第i行、第j列的数设为k
bool check(int a[9][9],int i,int j,int k)
{
int m,n;
//判断行
for(n=0;n<9;n++)
{
if(a[i][n] == k)
return false;
}
//判断列
for(m=0;m<9;m++)
{
if(a[m][j] == k)
return false;
}
//判断所在小九宫格
int t1=(i/3)*3,t2=(j/3)*3;
for(m=t1;m<t1+3;m++)
{
for(n=t2;n<t2+3;n++)
{
if(a[m][n] == k)
return false;
}
}
//可行，返回true
return true;
}

//数独求解函数
void Sudoku(int a[9][9],int n)
{
int temp[9][9];
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
temp[i][j]=a[i][j];
}
i=n/9; j=n%9; //求出第n个数的行数和列数
if(a[i][j] != 0) //已经有原始数据
{
if(n == 80) //是最后一个格子，输出可行解
print(temp);
else //不是最后一个格子，求下一个格子
Sudoku(temp,n+1);
}
else //没有数据
{
for(int k=1;k<=9;k++)
{
bool flag=check(temp,i,j,k);
if(flag) //第i行、第j列可以是k
{
temp[i][j]=k; //设为k
if(n == 80)
print(temp);
else
Sudoku(temp,n+1);
temp[i][j]=0; //恢复为0，判断下一个k
}
}
}
}

Answer 2

数独的排列是有规律的。
你去搜一下数独的排列规律
有了这个规律， 根本不用穷举法。
直接一个个数填充到该排的位置即可。！

Answer 3

不慢，我是思路也大概是这样的，一个数一个数的试，一般1万步循环，加循环内的一个函数大概每次执行1000步不到的样子，几乎是秒杀。

Answer 4

对不起,数独的解法只有搜索。LZ可以查阅一下NOIP2009第四题靶形数独的解题报告

Answer 5

网上这样的代码多了是，搜搜就行了嘛~~