用回溯法求解数独，有多个解的数独只求出其中一个！错误的数独会产生无法预料的结果！
第二段程序已解决错误数独的无法预料程序结果的问题！
没有对输入的待解数独进行一般性验证（同一行、一列以及同一个小九宫格都不能出现重复数字）
算法利用回溯的思想：
从第一个空白处开始，找到其候选解（排除同行、同列以及同一小九宫格的所有出现过的数字，剩下未出现的数字都是候选解）的第一个值填入数独。
对第二个空白执行第一步（前面所填入的数字对此空白处有影响）。
当出现某个空白的候选解个数为0时，就开始回溯，找到第一个候选解多于一个的，将其在使用的候选解设为不可取（本程序取值为-1），找到其下一个候选解，继续上面的步骤！
直到所有空白处填满，运算完成，输出结果！
#include&&stdio.h&
#include&&malloc.h&
typedef&struct&node
int&value[10];
int&findvalue(int&sudoku[9][9],&Node&*&node);
int&main(void)
int&sudoku[9][9]&=&{{3,&4,&0,&0,&0,&2,&0,&7,&5},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&5,&0,&0,&0,&0,&0,&4,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&0,&0,&8,&0,&0,&2,&0,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&0,&0,&6,&0,&0,&0,&9,&4},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&0,&0,&2,&0,&9,&0,&0,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{4,&9,&0,&0,&0,&8,&0,&0,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&0,&9,&0,&0,&7,&0,&0,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{0,&3,&0,&0,&0,&0,&0,&5,&0},
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{2,&7,&0,&9,&0,&0,&0,&1,&3}};
int&i,&j,&k&=&0,&num_of_empty&=&0;
int&index,&temp&=&0;
//计算所给数独中待填入的空白数
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
if(sudoku[i][j]==0)
num_of_empty++;
//为回溯栈分配空间
Node&*&node_stack&=&(Node&*)malloc(sizeof(struct&node)&*&num_of_empty);
//回溯法求解数独
while(num_of_empty)
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
if(sudoku[i][j]==0)
//初始化栈中存储候选值的数组
for(index=0;&index&10;&index++)
(node_stack&+&k)-&value[index]&=&0;
(node_stack&+&k)-&col&=&i;
(node_stack&+&k)-&row&=&j;
sudoku[i][j]&=&findvalue(sudoku,&node_stack&+&k);
if(sudoku[i][j]==-1)
sudoku[i][j]&=&0;
while((node_stack&+&k)-&value[0]==1)
sudoku[(node_stack&+&k)-&col][(node_stack&+&k)-&row]&=&0;
num_of_empty++;
(node_stack&+&k)-&value[0]--;
i&=&(node_stack&+&k)-&
j&=&(node_stack&+&k)-&
for(index=1;&index&10;&index++)
if((node_stack&+&k)-&value[index]==0)
(node_stack&+&k)-&value[index]&=&-1;
for(index=1;&index&10;&index++)
if((node_stack&+&k)-&value[index]==0)
sudoku[i][j]&=&
//当栈空，说明数独错误，无解
printf("此数独无解！\n");
free(node_stack);
num_of_empty--;
free(node_stack);
//打印数独
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
printf("%2d&",&sudoku[i][j]);
printf("\n");
int&findvalue(int&sudoku[9][9],&Node&*&node)
int&m,&n,&i&=&node-&col,&j&=&node-&
for(m=1;&m&10;&m++)
if(node-&value[sudoku[i][m-1]]==0)
node-&value[sudoku[i][m-1]]&=&sudoku[i][m-1];
if(node-&value[sudoku[m-1][j]]==0)
node-&value[sudoku[m-1][j]]&=&sudoku[m-1][j];
for(m=0;&m&3;&m++)
for(n=0;&n&3;&n++)
if(node-&value[sudoku[i/3*3+m][j/3*3+n]]==0)
node-&value[sudoku[i/3*3+m][j/3*3+n]]&=&sudoku[i/3*3+m][j/3*3+n];
for(m=1;&m&10;&m++)
if(node-&value[m]==0)
node-&value[0]++;
for(m=1;&m&10;&m++)
if(node-&value[m]==0)
if(node-&value[0]==0)
return&-1;
做了下改进：将各个步骤独立成函数，加入了待解数独的前期一般性检查，还有部分代码优化
#include&&stdio.h&
#include&&stdlib.h&
#define&BOOL&int
#define&FALSE&1
#define&TRUE&0
typedef&struct&node
int&value[10];
int&findvalue(int&sudoku[9][9],&Node&*&node);
BOOL&general_inspection(int&sudoku[9][9]);
int&blank_num(int&sudoku[9][9]);
Node&*&mem_alloc(int&num_of_empty);
void&trace(int&sudoku[9][9],&Node&*&node_stack,&int&num_of_empty);
void&print_sudoku(int&sudoku[9][9]);
int&main(void)
int&sudoku[9][9]&=&{{3,&4,&1,&0,&0,&2,&0,&7,&5},
{0,&5,&0,&0,&0,&0,&0,&4,&0},
{0,&0,&0,&8,&0,&0,&2,&0,&0},
{0,&0,&0,&6,&0,&0,&0,&9,&4},
{0,&0,&0,&2,&0,&9,&0,&0,&0},
{4,&9,&0,&0,&0,&8,&0,&0,&0},
{0,&0,&9,&0,&0,&7,&0,&0,&0},
{0,&3,&0,&0,&0,&0,&0,&5,&0},
{2,&7,&0,&9,&0,&0,&0,&1,&3}};
int&num_of_
//为回溯栈分配空间
Node&*&node_
if(general_inspection(sudoku))
printf("此数独存在错误！请检查\n");
print_sudoku(sudoku);
num_of_empty&=&blank_num(sudoku);
node_stack&=&mem_alloc(num_of_empty);
trace(sudoku,&node_stack,&num_of_empty);
print_sudoku(sudoku);
BOOL&general_inspection(int&sudoku[9][9])
int&temp[10]&=&{0,&0,&0,&0,&0,&0,&0,&0,&0,&0};
int&i,&j,&m,&n;
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
if(sudoku[i][j]!=0)
//检查所在行
for(m=0;&m&10;&m++)
temp[m]&=&0;
for(m=0;&m&9;&m++)
if(sudoku[i][m]!=0)
if(temp[sudoku[i][m]]==0)
temp[sudoku[i][m]]&=&1;
return&FALSE;
//检查所在列
for(m=0;&m&10;&m++)
temp[m]&=&0;
for(m=0;&m&9;&m++)
if(sudoku[m][j]!=0)
if(temp[sudoku[m][j]]==0)
temp[sudoku[m][j]]&=&1;
return&FALSE;
//检查所在九宫格
for(m=0;&m&10;&m++)
temp[m]&=&0;
for(m=0;&m&3;&m++)
for(n=0;&n&3;&n++)
if(sudoku[i/3*3+m][j/3*3+n]!=0)
if(temp[sudoku[i/3*3+m][j/3*3+n]]==0)
temp[sudoku[i/3*3+m][j/3*3+n]]&=&1;
return&FALSE;
return&TRUE;
int&blank_num(int&sudoku[9][9])
//计算所给数独中待填入的空白数
int&i,&j,&num&=&0;
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
if(sudoku[i][j]==0)
Node&*&mem_alloc(int&num_of_empty)
Node&*&node_stack&=&(Node&*)malloc(sizeof(struct&node)&*&num_of_empty);
if(node_stack==NULL)
printf("内存分配失败！\n");
return&node_
void&trace(int&sudoku[9][9],&Node&*&node_stack,&int&num_of_empty)
int&i,&j,&index,&k&=&0;
//回溯法求解数独
while(num_of_empty)
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
if(sudoku[i][j]==0)
(node_stack&+&k)-&col&=&i;
(node_stack&+&k)-&row&=&j;
sudoku[i][j]&=&findvalue(sudoku,&node_stack+k);
if(sudoku[i][j]==-1)
sudoku[i][j]&=&0;
while((node_stack&+&k)-&value[0]==0)
//当栈空，说明数独错误，无解
printf("此数独无解！\n");
//free(node_stack); //为啥这里一释放内存，就弹出debug&assertion&failed窗口啊！
sudoku[(node_stack&+&k)-&col][(node_stack&+&k)-&row]&=&0;
num_of_empty++;
for(index=1;&index&10;&index++)
if((node_stack&+&k)-&value[index]==0)
sudoku[(node_stack&+&k)-&col][(node_stack&+&k)-&row]&=&
(node_stack&+&k)-&value[index]&=&1;
(node_stack&+&k)-&value[0]--;
num_of_empty++;
i&=&(node_stack&+&k)-&
j&=&(node_stack&+&k)-&
num_of_empty--;
//栈空间使用结束，释放
free(node_stack);
node_stack=NULL;
int&findvalue(int&sudoku[9][9],&Node&*&node)
int&m,&n,&i&=&node-&col,&j&=&node-&
//初始化栈中存储候选值的数组
for(m=0;&m&10;&m++)
node-&value[m]&=&0;
for(m=1;&m&10;&m++)
node-&value[sudoku[i][m-1]]&=&1;
node-&value[sudoku[m-1][j]]&=&1;
for(m=0;&m&3;&m++)
for(n=0;&n&3;&n++)
node-&value[sudoku[i/3*3+m][j/3*3+n]]&=&1;
//node-&value[0]记录候选值个数，前面的循环可能会修改掉它，需要重新赋0值
node-&value[0]&=&0;
for(m=1;&m&10;&m++)
if(node-&value[m]==0) node-&value[0]++;
for(m=1;&m&10;&m++)
if(node-&value[m]==0)
node-&value[m]&=&1;
node-&value[0]--;
//返回候选值m，若无候选值可用，返回错误标记-1
return&-1;
void&print_sudoku(int&sudoku[9][9])
//打印数独
for(i=0;&i&9;&i++)
for(j=0;&j&9;&j++)
printf("%2d&",&sudoku[i][j]);
printf("\n");
程序当时跑是没有问题的，还是希望能贴出比较具体的错误信息！
& 开源中国(OSChina.NET) |
开源中国社区(OSChina.net)是工信部
指定的官方社区求大神解答_数独吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：43,853贴子：
求大神解答收藏
题目抄完才发现只有8行。。。
这是欺负我没玩过数独？
贴吧拳王争霸赛中累计获取300场胜利,
你在逗我？
有一种旧版'最难题'的感觉......
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或求个数独答案 抄在纸上了_百度知道
求个数独答案 抄在纸上了
jpg" esrc="http://a.hiphotos.jpg" target="_blank" title="点击查看大图" class="ikqb_img_alink"><img class="ikqb_img" src="/zhidao/wh%3D450%2C600/sign=38d9e280be315cebb881e725/d52abce36d3d539bd09://a.com/zhidao/wh%3D600%2C800/sign=f3a295a9dddc8aabce36d3d539bd09.baidu.baidu&nbsp./zhidao/pic/item/d52abce36d3d539bd09://a.<img class="ikqb_img" src="http./zhidao/wh%3D450%2C600/sign=/zhidao/pic//zhidao/wh%3D600%2C800/sign=2fc33f02cd6ce2a7c7d37/ff4faae238.baidu.hiphotos答案在下面．<a href="http.jpg" esrc="http://e://e.baidu://e.hiphotos
提问者评价
太给力了，你的回答完美解决了我的问题！
来自团队：
其他类似问题
为您推荐：
数独的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁6699人阅读
【Algorithm】（1）
【Java SE】（10）
算法，数独问题用概率算法中的拉斯维加斯算法实现数独问题的生成用回溯法实现对数独问题的求解
注：数独问题与数度难题的区别是数度难题只有一个解，而数独问题的解有一个或多个。
Introduction :
标准的数独游戏是在一个 9 X 9 的棋盘上填写 1 – 9 这 9 个数字，规则是这样的：
棋盘分成上图所示的 9 个区域（不同颜色做背景标出，每个区域是 3 X 3 的子棋盘），在每个子棋盘中填充 1 – 9 且不允许重复 ，下面简称块重复每一行不许有重复&#20540; ，下面简称行重复每一列不许有重复&#20540; ，下面简称列重复
如上红色框出的子区域中的亮黄色&#26684;子只能填 8。
扩展阅读：
随机生成数独问题，如果做成一个数独小游戏的话可以按游戏难易程度生成，比如有简单、中等、困难三个程度求解数独问题，根据生成的数独问题或者用户输入的数独问题求解出所有答案或者求解出不超过MAX个答案，因为某个问题可能含有上十万个解，用MAX约束找到MAX个答案后就不再找其它的答案
有一种求解数独问题的方案是“候选数字法”，就是在待填充的&#26684;子中填写不会造成行重复、列重复、块重复的数字，有的时候存在多个这样的数字，那么我们可以随机选取一个，如果待填充的&#26684;子中填写任何一个数字都会造成某种重复的发生，则说明这个问题没有解，也就是这不是一个数独问题。如上图中红色框出区域的下面一个区域的红色&#26684;子中可以填写的数字为 4、8、9，那么它的候选数字就是4、8、9，你可以随机选一个填入。当所有的&#26684;子填充完后数独问题就解决了。
根据上述的这种候选数字法，我们可以用它来生成数独问题以及求解数独问题。
关于生成数独问题：
循环遍历 9 X 9 的数独&#26684;子，在遍历到的当前&#26684;子的候选数字中随机选取一个数字填入，如果当前&#26684;子没有了候选数字则清空所有已经填好的&#26684;子，重新再来。这是一个最简单的也是最容易理解的概率方法了。伪码如下：
1: int[][] sudoku = new int[9][9]; //数独棋盘
2: while(true) {
clearSudoku(); //清空所有已填数字, 每个&#26684;子置 0
for(int row = 0; row & 9; row&#43;&#43;) {
for(int col = 0; col & 9; col&#43;&#43;) {
//getCandidates(row, col) 获取当前&#26684;子的候选数字
//randomCandidate() 随机选取一个候选数字
if(getCandidates(row, col) != NULL) //如果有候选数字
sudoku[row][col] = randomCandidate(getCandidates(row, col));
goto //跳转到label那里清空&#26684;子重新来过
关于求解数独问题：
同上， 不过这次不是采用随机算法，因为随机算法没法保证把所有的解都求出。利用回溯法把所有可能的情况都遍历，那么就可以求出所有的解。我们考虑下面的一个实例：
初始时，sudoku[0][0]&#26684;子的候选数字为2， 3，5， 6，如图标出，sudoku[4][0]的为2，4，5，其它如图。那么我们在填充sudoku[0][0]的时候不能按照随机来了，因为我们需要把所有的情况遍历的话，需要按一定顺序来，也就是从2开始来，因为一旦某个&#26684;子填充了一个候选数字后，其它&#26684;子的候选数字会发生变化，假设sudoku[0][0]填充了2，那么与sudoku[0][0]在同一行、同一列、同一块内的&#26684;子的候选数字就不能再有2了，sudoku[4][0]、sudoku[6][0]等都应该将原来含有的2给删掉。
我们遍历着填写候选数字，当遇到某个&#26684;子的候选数字不存在的时候，我们应该回溯了，我们回到上一&#26684;，填写另一个候选数字。比如上图，我们按照这样的顺序来：
sudoku[0][0]填写2，sudoku[4][0]候选为(4,5)，sudoku[6][0]候选为(3, 5)，sudoku[7][0]候选为(4, 5, 6)，sudoku[8][0]候选为(5, 6)；sudoku[4][0]填写4，sudoku[6][0]候选为(3, 5)，sudoku[7][0]候选为(5, 6)，sudoku[8][0]候选为(5, 6)；sudoku[6][0]填写5，sudoku[7][0]候选为(6)，sudoku[8][0]候选为(6)；那么sudoku[7][0]填了6之后sudoku[8][0]就没有候选数字可填了
至于如何遍历所有的情况，我们可以这样来：
把候选数字都按大小从小到大排序，用一个栈记录已经选取过的候选数字在这个序列中的序号，每一次选取候选数字就入栈，每一次回溯就出栈。另外需要注意的是每一次改变&#26684;子数字的操作都需要更新候选数字。伪码如下（注意，这只是表达思想，代码在如果按执行顺序来是有误的）：
3: while(true) {
if(candidates[row][col] != NULL) {
//当前&#26684;子填写第idx个候选数字, idx = 0,1,2,3...
sudoku[row][col] = candidates[row][col](idx);
//如果所有的&#26684;子都填了，那么就把这个解保存起来，然后回溯
if(allBlanked()) {
solutions.add();
backtrace(row, col);
//idx入栈以记录已经填过的候选数字
s.push(idx);
//更新候选数字
updateCandidates();
//填写下一行
next(row, col);
else {//如果没有了候选数字就回到上一&#26684;填过的位置
backtrace(row, col);
//回溯到原点就结束
if(s.isEmpty()) {
//获取上一&#26684;填写的数字的序号,这次应该填写下一个候选数字了,即序号加1
idx = s.pop() &#43; 1;
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
42: Solution: 4
52: Solution: 5
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
42: Solution: 4
52: Solution: 5
62: Solution: 6
72: Solution: 7
82: Solution: 8
1: New game:
12: Solution: 1
22: Solution: 2
32: Solution: 3
45: Solution: 235
55: Solution: 236
65: Solution: 237
Implementations : （代码是大二学期末的算法分析课程实习上写的，纯原创，当时用Qt写过一个界面设计了一个数独游戏，但是出于当时时间紧张没有做得很好，所以这里就不贴了，等以后有空完善好了再在Qt栏目里面贴出来，因为当时的代码存在小漏洞，这个版本修改了那个漏洞，原博文出于我的网易博客，因为今天是10月的最后一天了，再不加一篇博文，首页的那个“恒”就没了 = =！）
Qt游戏的那个截图：
Java源码：
Java测试源码：
@Ggicci 本文属于个人学习笔记，如有错误，希望您能指正！转载请注明出处，谢谢 :) [CSDN博客]
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：63468次
排名：千里之外
原创：24篇
评论：13条
(1)(4)(4)(4)(4)(9)求数独题答案：0093045 ...060000
ORZGIRL2451
963 485 217812 793 645745 612 389354 826 971671 539 428289 174 563498 251 736136 947 852527 368 194
为您推荐：
其他类似问题
扫描下载二维码