资源简介
舞蹈链算法求解数独
代码片段和文件信息
#include
#include
#include
#include
#include
#include
FILE *ofp;
int result=0; //结果数
//输出可行的解
void Sudoku（int a[9][9]int n）;
void print（int a[9][9]）
{
result++;
printf（“第%d个填法为：\n“result）;
fprintf（ofp“第%d个填法为：\n“result）;
for（int i=0;i<9;i++）
{
for（int j=0;j<9;j++）
{
printf（“%d “a[i][j]）;
fprintf（ofp“%d “a[i][j]）;
if（（j==2）||（j==5））
{
printf（“ “）;
fprintf（ofp“ “）;
}
}
printf（“\n“）;
fprintf（ofp“\n“）;
if（（i==2）||（i==5））
{
printf（“\n“）;
fprintf（ofp“\n“）;
}
}
printf（“\n“）;
fprintf（ofp“\n“）;
//getchar（）;
}
//判断是否可以将第i行、第j列的数设为k
bool check（int a[9][9]int iint jint k）
{
int mn;
//判断行
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）*3t2=（j/3）*3;
for（m=t1;m
{
for（n=t2;n
{
if（a[m][n] == k）
return false;
}
}
//可行，返回true
return true;
}
//数独求解函数
void Sudoku（int a[9][9]int n）
{
int temp[9][9];
int ij;
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（tempn+1）;
}
else //没有数据
{
//尝试填入1-9数字
for（int k=1;k<=9;k++）
{
bool flag=check（tempijk）;
if（flag） //第i行、第j列可以是k
{
temp[i][j]=k; //设为k
if（n == 80）
{
print（temp）;
}
else
Sudoku（tempn+1）;
temp[i][j]=0; //恢复为0，判断下一个k
}
}
}
}
char *ReadData（FILE *fp char *buf）
{
return fgets（buf 1024 fp）;//读取一行到buf
}
int main（）
{
int a[9][9]={0};
FILE *fp;
char *buf *p;
LARGE_INTEGER freq t0 t1;
QueryPerformanceFrequency（&freq）;
buf=（char*）malloc（1024*sizeof（char））;
fp=fopen（“input1.txt“ “r“）;
ofp=fopen（“output.txt““w“）;
printf（“数独的解为：\n\n“）;
while（true）
{
int i=0 j=0 k=0;
if（!p）//文件读取结束则跳出循环
break;
for （i = 0; i < 9; ++i）
{
p=ReadData（fp buf）;//每次调用文件指针fp会自动后移一行
if（!p）//文件读取结束则跳出循环
break;
printf（“%s“buf）;
fprintf（ofpbuf）;
for （j = 0; j < 9; ++j）
{
a[i][j]=buf[j]-‘0‘;
}
}
fprintf（ofp“\n“）;
QueryPerformanceCounter（&t0）;
Sudoku（a0）;
QueryPerformanceCounter（&t1）;
_int64 time = （（（t1.QuadPart-t0.QuadPart）*1000000）/freq.QuadPart）;
printf（“%dus\n“time）;
fprintf（ofp“%dus\n“time）;
p=ReadData（fp buf）;//输入每组间的数字
if（result==0）
printf（“此数独无解!“）;
result=0;
}
fclose（fp）;
fclose（ofp）;
return 0;
}属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 1926144 2016-12-12 23:26 求解数独\数独所有解\Debug\shudu_all.bsc
文件 180274 2017-01-04 20:51 求解数独\数独所有解\Debug\shudu_all.exe
文件 190216 2017-01-04 20:51 求解数独\数独所有解\Debug\shudu_all.ilk
文件 18538 2017-01-04 20:51 求解数独\数独所有解\Debug\shudu_all.obj
文件 3566388 2016-12-13 21:30 求解数独\数独所有解\Debug\shudu_all.pch
文件 467968 2017-01-04 20:51 求解数独\数独所有解\Debug\shudu_all.pdb
文件 0 2016-12-12 23:26 求解数独\数独所有解\Debug\shudu_all.sbr
文件 148480 2017-01-04 21:08 求解数独\数独所有解\Debug\vc60.idb
文件 77824 2017-01-04 20:51 求解数独\数独所有解\Debug\vc60.pdb
文件 1017 2016-12-08 21:59 求解数独\数独所有解\input1.txt
文件 1017 2016-12-11 23:42 求解数独\数独所有解\input4.txt
文件 5924 2017-01-04 21:08 求解数独\数独所有解\output.txt
文件 3161 2017-01-04 21:18 求解数独\数独所有解\shudu_all.cpp
文件 3437 2016-12-13 20:37 求解数独\数独所有解\shudu_all.dsp
文件 526 2016-12-13 21:56 求解数独\数独所有解\shudu_all.dsw
文件 41984 2017-01-04 21:18 求解数独\数独所有解\shudu_all.ncb
文件 48640 2017-01-04 21:18 求解数独\数独所有解\shudu_all.opt
文件 252 2017-01-04 21:02 求解数独\数独所有解\shudu_all.plg
文件 531684 2017-01-04 21:12 求解数独\数独求解.docx
文件 6414 2017-01-04 21:16 求解数独\舞蹈链\danceli
文件 3437 2016-12-22 21:11 求解数独\舞蹈链\danceli
文件 526 2016-12-22 22:02 求解数独\舞蹈链\danceli
文件 41984 2017-01-04 21:18 求解数独\舞蹈链\danceli
文件 48640 2017-01-04 21:18 求解数独\舞蹈链\danceli
文件 1151 2017-01-04 21:16 求解数独\舞蹈链\danceli
文件 1934336 2016-12-17 23:01 求解数独\舞蹈链\Debug\danceli
文件 221230 2017-01-04 21:16 求解数独\舞蹈链\Debug\danceli
文件 220692 2017-01-04 21:16 求解数独\舞蹈链\Debug\danceli
文件 23582 2017-01-04 21:16 求解数独\舞蹈链\Debug\danceli
文件 3570680 2016-12-22 21:15 求解数独\舞蹈链\Debug\danceli
............此处省略18个文件信息
- 上一篇：MP3音乐txt文件转16进制代码工具
- 下一篇：逻辑与计算机设计基础实验报告
川公网安备 51152502000135号
评论
共有 条评论