700万小时搞定最小数独问题 | 科学人 | 果壳网 科技有意思
700万小时搞定最小数独问题
本文作者:sqybi
刚刚迈入 2012 年，数学界就有一个不大不小的收获。三位爱尔兰数学家发表了一篇论文，证明了数独至少需要 17 个初始数字才有唯一解。这个问题很难吗？其实一点也不，计算机才花了 700 万小时的 CPU 时间（CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度）就搞定了这道数独题。这 700 万个小时它了做了什么？是三位数学家的方法很笨才导致算了这么久吗？实际上，这个时间已经不算长了。看看死理性派的详细介绍你就知道了。
数独游戏和长久以来的世界难题
18 世纪末，瑞士数学家欧拉发明了一种叫做“拉丁方阵（Latin Square）”的游戏。虽然最初这个游戏并没有风靡起来，但随着时间的推移，在 20 世纪 70 年代的美国，这个游戏以“数字拼图（Number Place）”的名字迅速流行起来，之后逐渐流传到日本、英国，到现在已经成为了红遍全球的智力游戏。
数独游戏基本规则是这样的：在一个九宫格中给出一些初始数字。玩家需要在九宫格内填入缺失的数字（1 - 9），保证：
每一行的 9 个数字各不相同
每一列的 9 个数字各不相同
每一个用粗线标识出的 3 × 3 的小正方形内 9 个数字也各不相同
虽然规则非常简单，但其中包含的信息却毫不简单。数学家 Bertram Felgenhauer 在 2005 年证明，数独的解共有 9! × 722 × 27 × 27,704,267,971 种不同的可能组合，上面这个乘式的最后一个数还是一个质数。
一个经典的数独。图像来源：wikipedia
而如此多变的变化，无疑也给数学家们出了不少难题。其中一个被讨论了很久的问题是， 至少给定多少个初始数字，数独才会有唯一解？ 此前已经有人给出了一些包含 17 个初始数字的数独，并利用计算机证明了其解是唯一的（对于某个给定了 17 个初始数字的数独，计算机枚举了所有可能的排列情况，只找到一个解），从而证明了 17 个初始数字的数独是可以存在唯一解的。但是长久以来都没有人知道， 16 个初始数字的数独是否存在唯一解。终于，在 2012 的元旦，都柏林大学（University College Dublin）的数学家们给出了 答案：16 个初始数字的数独不存在唯一解。
有没有解试出来
消息一出，媒体争相报道，报道中不乏复杂的算法、超级计算机等“虽然不知道在说什么，但看起来很厉害”的词汇。事实上，研究人员用来证明这个问题的方法用一个字就可以总结，那就是——试。
解决这个问题几位数学家最初的想法非常可爱： 只要把每一种有 16 个初始数字的数独都尝试着填一遍，自然就知道答案了。
但很可惜，因为数独的组合实在是太多了，所以即使是现在最快的计算机，也不可能在我们的有生之年穷尽所有的组合。因此，必须用一些数学的方法来减少尝试的次数，这个想法才能够实现。
他们发现，数独虽然有很多种可能的组合，但是其中一些其实是等价的。如下图，可以看到交换第一列和第二列对整个数独并没有影响。实际上任意一个合法数独的解交换两列后，都可以构成一个新的合法数独，而这个新数独和原数独就可以看做是等价的。
两种等价的数独组合
三位数学家总结了数独的 4 种等价变换：
⒈ 列与列的重新排列（例如上图）
⒉ 行与行的重新排列
⒊ 数字 1 到 9 的重新排列。如把原先是 1 的位置都填上 2，然后把原先是 2 的位置都填上……直到把原先是 9 的位置都填上 1 等
⒋ 网格的变换。如整个数独顺时针旋转90度，整个数独做镜像对称等
在 2006 年已经有数学家证明，排除以上几种重复后，数独总共有 5,475,730,538 个等价类。因为每个等价类里的任意一种情况都可以通过这个等价类中的其它情况经由以上 4 种变换得到，所以对每个等价类来说，我们只要考虑一种情况即可。如此一来，有非常多的组合都被我们直接排除了，计算量大大减小。
让枚举量少一点，再少一点
虽然等价类的数量已经降低到了可以接受的范围，但问题还远没有结束。因为在选择了某个等价类中的一种情形之后，我们还需要验证这个情形的 81 个数字中是否可以选出 16 个，使得以这 16 个数为初始数字的数独有唯一解。
如果检查所有的可能情况，对于每一个等价类，我们要检查的次数就是：
这显然很不幸：好不容易通过排除等价变换的方法把计算量减下去，怎么能在这里再加回来呢！所以这又需要数学家再做一些工作，把 3.4 × 10 16 这个数减小，让枚举量少一点，再少一点。
因此，几位数学家利用了 “不可避免集”的概念：如下图所示，如果表示颜色的 4 个数字中任何一个都没有在初始数字中给出，那么这个数独一定没有唯一解——因为在没有给出的情况下这 4 个数字都是由玩家填进去的，玩家既可以以左图的方式填入这 4 个数字，也可以以右图的方式填入，而得到的两个解都是合法的。具有这种属性的数个方格就叫做不可避免集，一旦出现了不可避免集，我们就必须要在其中至少选出一个格子用来填写初始数字。
不可避免集
不可避免集大大化简计算量
在论文中，数学家们采用了 Ed Russell 总结的一套不可避免集的模板，总共记录了 525 种不同的不可避免集。因为一开始所说的 4 种等价变换对不可避免集也适用，所以他们对不可避免集进行了一些标准化的处理，以保证这 525 种不可避免集互相之间不能通过 4 种等价变换得到。
此时，枚举算法就被改造成这样：数学家给所有的不可避免集都设定一个状态，分为“被击中”或“未被击中”两种。初始时九宫格 81 个方格内都没有填入数字，所有不可避免集的初始状态均为“未被击中”。之后开始每次选择一个最小的未被击中的不可避免集，枚举其中的每个格子。即每次选择不可避免集中的一个格子填充初始数字，直至试完不可避免集中的所有空格。同时将这个不可避免集标记为“被击中”状态，每次枚举都有 4 种可能。
● 如果这个格子也出现在了其它不可避免集中，那么将这些被涉及到的不可避免集也标记为“被击中”状态；
● 如果枚举了 16 个格子后还有不可避免集未被击中，说明以这 16 个格子为初始状态的数独一定没有唯一解；
● 恰好枚举了 16 个格子后所有的不可避免集全部被击中；
● 如果枚举了不到 16 个格子后所有不可避免集已经全部被击中，则从剩下的所有格子中再枚举几个格子使初始填充了数字的格子达到 16 个。
完成上面这个工作后，就要用解数独的程序来验证所有枚举的情况是否有唯一解。为了进一步加快枚举速度，数学家们还加入了一些可行性剪枝和最优化剪枝，如提前判断“当前情况下已经不可能击中所有不可避免集”并终止枚举等。
在这一系列优化之后，算法的复杂度终于降低到了可以接受的范围内。但即使这样，整个计算过程还是耗费了 700 万小时的 CPU 时间。幸而这个算法最终给出了一个确定的结果：所有仅包含 16 个初始数字的数独，都不存在唯一解！
暴力与美学的结合
当然，上述结果的正确性还有待其他科学家进一步验证，因为算法耗时极高，所以验证过程也需要花费比较长的时间。但无论这次 3 位数学家给出的结论正确与否，随着验算结果的公布，这个问题终将得到一个解答。
粗略看来，这个算法的实现是非常暴力和机械化的：尝试每一种可能的情况。但是在实现的过程中，数学家们又在借助于数学的力量，不断地试图减少枚举的数量，最终将不可能的事情化为了现实。怪不得西澳大利亚大学的数学家 Gordon Royle 这样评价道：“这个挑战性的问题让人们把计算的能力和数学的技巧发挥到了极限，这就像是在攀登最高耸的山峰。”
现在关于数独的 puzzle 越来越难越来越精彩了。你做过的最难的数独是什么？在这里抛一块砖：
参考资料： There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
你可能感兴趣
看不懂。？
这个答案给我。
你们这些人类都在用计算机做神马啊！
求17个数字的数独。。
700万小时我还是利用这个时间去冬眠吧
经济学爱好者
为什么最后一题只有16个数？
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：为什么最后一题只有16个数？因为有附加条件。。。
求非穷举证明的方法~
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：求非穷举证明的方法~如果有的话就不用这么累了！
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：700万小时我还是利用这个时间去冬眠吧700万小时是CPU时间。。。有好多好多的CPU们一起努力工作呢☆
什么叫“700 万小时的 CPU 时间”700万小时是29.17万天是0.08万年是800年啊
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：什么叫“700 万小时的 CPU 时间”700万小时是29.17万天是0.08万年是800年啊CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度。。。如果有10000个CPU同时运行代码，那么700万小时的CPU时间只要一个月就可以跑完了。
的回应：这个答案给我。
的回应：求17个数字的数独。。你去找
的回应：为什么最后一题只有16个数？你来都来了，就不能推荐一下么……
声明不是我解出来的
经济学爱好者
的回应：因为有附加条件。。。也就是说，看起来是限制条件，其实反而提供了额外信息，降低了复杂度。
“让枚举量少一点，再少一点”里的图中右边那货也是合法的？
的回应：声明不是我解出来的用PS稍微写好看一点……慢了五分钟解出来啊
的回应：“让枚举量少一点，再少一点”里的图中右边那货也是合法的？THX 哎呀 谢谢谢谢 马上来改
楼主最后一题
的回应：声明不是我解出来的原来我慢了好多啊引用
的回应：用PS稍微写好看一点……慢了五分钟解出来啊
理论物理学硕士在读，维基百科小组管理员
LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题
的回应：LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题DLX =v=
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：DLX =v=引用
的回应：LZ可以参考一下信息学奥赛里的相关资料，这里积累了很多关于数独的问题想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的
的回应：想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的 ForbiddenYou don't have permission to access /works/dlxcn/ on this server.Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.
配图让数独控伤不起啊，有木有....
计算机科学与工程专业本科生，口琴控，动漫迷
的回应：ForbiddenYou don't have permission to access /works/dlxcn/ on this server.Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.Ctrl+F5刷新下呢。。。我貌似设置了不能外链。。。囧
理论物理学硕士在读，维基百科小组管理员
的回应：想当初那篇论文还是我翻译的。。。哈哈哈口胡了，其实是吴豪同学完成了最主要的工作，我只是帮忙翻译一小部分然后校对一下啥的。。。顺便@ 下楼上的童鞋
如果有兴趣的话可以看一下这篇Knuth的论文 这个算法用在解数独上效果还是不错的 2个月前刚刚参加完信息学竞赛，现在已经淡出了……顺便看到一眼……想起来了，等将来有机会我会看的，嗯
的回应：你们这些人类都在用计算机做神马啊！难道你不是人类吗？
显示所有评论
(C)2017果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号&&&&
违法和不良信息举报邮箱：&&&&举报电话：写了一个解数独游戏的matlab代码~方法比较笨~求大神指教【附代码_matlab吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：176,397贴子：
写了一个解数独游戏的matlab代码~方法比较笨~求大神指教【附代码收藏
一时突发奇想~写了段代码~~各位大神不要笑我~~感觉理论上应该可以解所有的题目~自测了20个左右包括最高难度的都没问题~希望有兴趣的吧友帮忙测试一下（个人感觉挺有意思的）有什么问题我会修改代码~~游戏规则在二楼~代码在三楼~希望吧里各位大神能提些意见~~目前只是简单的代码~如果没有BUG我还准备加GUI上去~~各位吧友多帮帮忙哈~~~
免费下载官方MATLAB中文试用版,让工程师和科学家更高效地进行科学计算.
数独的游戏规则很简单，9x9个格子里，已有若干数字，其它宫位留白，玩家需要自己按照逻辑推敲出剩下的空格里是什么数字，使得每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每个行列及每个小九宫格里都只能出现一次。 　　做这种游戏不需要填字谜那样的语言技巧和文化知识，甚至也不需要复杂的数学能力。因为它根本不需要加减乘除运算。当然，你也千万别小看它，并不是那么容易被“制服”的。当你握笔沉思的时候，这9个数字很可能让你头痛不已，脉搏加快，恼火不已。不过，当你成功填完所有数字的时候，你肯定会感到欣喜若狂。有数独迷宣称，做此类游戏，一名大学教授很可能不敌一名工厂工人。 (搬运自百度百科)
附上代码~~~x=zeros(9,9);x(1,5)=5;x(1,6)=7;x(1,8)=8;x(2,1)=3;x(3,3)=2;x(3,4)=9;x(3,7)=4;x(4,1)=2;x(4,4)=8;x(4,6)=9;x(4,7)=3;x(5,1)=4;x(5,9)=7;x(6,3)=7;x(6,4)=4;x(6,6)=6;x(6,9)=8;x(7,3)=6;x(7,6)=2;x(7,7)=7;x(8,9)=5;x(9,2)=9;x(9,4)=3;x(9,5)=1;%需要解开的数独矩阵~待填的都填0%x_temp=x;%for xi=1:9%
for xj=1:9%
x(xi,xj)=input('');%
end%endx_temp=x;%%
while length(find(x_temp==0))&=1
x_flag=x_%第一一个标志来判断依次循环后是否能填入数
a=find(x_temp==0);%找出未待填的位置%%
j=ceil(a/9);%分别求出所在行和列
i=mod(a,9);
i(find(i==0))=9;%%%将待填的空可填入的数据存入ept_temp中，不能填的数据位填0
for k=1:length(a)
ept_temp(k,:)=1:9;
hang=find(x_temp(i(k),:)&0);
ept_temp(k,x_temp(i(k),hang))=0;
lie=find(x_temp(:,j(k))&0);
ept_temp(k,x_temp(lie,j(k)))=0;
zheng=x_temp(3*(ceil(i(k)/3)-1)+1:3*(ceil(i(k)/3)-1)+3,3*(ceil(j(k)/3)-1)+1:3*(ceil(j(k)/3)-1)+3);
num=zheng(find(zheng&0));
ept_temp(k,num)=0;
end%%%按行搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
hang_ept=ept(find(i==k),:);
temp1=sum(hang_ept,1);
if(temp1(q)==q)
temp=find(i==k);
fprintf(1,'%d hang %d lie fill %d\n',k,j( temp(find(hang_ept(:,q)&0))),q);
x_temp(k,j( temp(find(hang_ept(:,q)&0))))=q;
end%%%按列搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
lie_ept=ept(find(j==k),:);
temp2=sum(lie_ept,1);
if(temp2(q)==q)
temp=find(j==k);
fprintf(1,'%d hang %d lie fill %d\n',i(temp(find(lie_ept(:,q)&0))),k,q);
x_temp(i(temp(find(lie_ept(:,q)&0))),k)=q;
end%%%按小方块搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
kj=ceil(k/3);
ki=mod(k,3);
ki(find(ki==0))=3;
zheng_ept=ept(find(i&=(3*(ki-1)+1)&i&=(3*(ki-1)+3)&j&=(3*(kj-1)+1)&j&=(3*(kj-1)+3)),:);
temp3=sum(zheng_ept,1);
if(temp3(q)==q)
temp=find(i&=(3*(ki-1)+1)&i&=(3*(ki-1)+3)&j&=(3*(kj-1)+1)&j&=(3*(kj-1)+3));
fprintf(1,'%d hang %d lie fill %d\n',i(temp(find(zheng_ept(:,q)&0))),j(temp(find(zheng_ept(:,q)&0))),q);
x_temp(i(temp(find(zheng_ept(:,q)&0))),j(temp(find(zheng_ept(:,q)&0))))=q;
end%%%遍历所有空格的可填入数据，找到只有一个可填入数据的点并填入该数据
for k=1:length(a)
if(length(find(ept(k,:)&0))==1)
fprintf(1,'num %d fill %d\n',a(k),find(ept(k,:)&0));
x_temp(a(k))=find(ept(k,:)&0);
clear ept_%%%经过一次循环如果x_temp没变化则不能填满数据~~报错
if(x_flag==x_temp)
error('Error!!Can not fill all block!!');
fprintf(1,'----------------------------------------------------------------------------\n');endfprintf(1,'Finish!!\n');fprintf(1,'*******************************************************************************\n');x=x_x
请吧里大神指教~~~
这是自带的初始题目~~x =
0运行结果如下~~1 hang 9 lie fill 34 hang 5 lie fill 79 hang 1 lie fill 78 hang 2 lie fill 28 hang 4 lie fill 78 hang 2 lie fill 24 hang 5 lie fill 7num 34 fill 5num 40 fill 7----------------------------------------------------------------------------9 hang 3 lie fill 55 hang 6 lie fill 59 hang 3 lie fill 55 hang 6 lie fill 58 hang 5 lie fill 6----------------------------------------------------------------------------7 hang 5 lie fill 93 hang 6 lie fill 35 hang 4 lie fill 17 hang 5 lie fill 9num 22 fill 1----------------------------------------------------------------------------2 hang 5 lie fill 42 hang 6 lie fill 12 hang 9 lie fill 92 hang 6 lie fill 1num 39 fill 8----------------------------------------------------------------------------9 hang 9 lie fill 2num 20 fill 8----------------------------------------------------------------------------5 hang 2 lie fill 85 hang 2 lie fill 8----------------------------------------------------------------------------7 hang 1 lie fill 84 hang 2 lie fill 6----------------------------------------------------------------------------4 hang 8 lie fill 53 hang 9 lie fill 6num 8 fill 1num 76 fill 4----------------------------------------------------------------------------2 hang 4 lie fill 61 hang 1 lie fill 62 hang 7 lie fill 57 hang 9 lie fill 11 hang 1 lie fill 62 hang 7 lie fill 5num 3 fill 5num 79 fill 1----------------------------------------------------------------------------1 hang 3 lie fill 92 hang 8 lie fill 26 hang 2 lie fill 56 hang 1 lie fill 96 hang 2 lie fill 51 hang 4 lie fill 21 hang 3 lie fill 96 hang 2 lie fill 51 hang 4 lie fill 2num 6 fill 9num 11 fill 7num 28 fill 2----------------------------------------------------------------------------1 hang 2 lie fill 43 hang 8 lie fill 76 hang 5 lie fill 37 hang 2 lie fill 38 hang 3 lie fill 43 hang 8 lie fill 71 hang 2 lie fill 45 hang 3 lie fill 33 hang 8 lie fill 7num 12 fill 1num 23 fill 3num 55 fill 1num 69 fill 1----------------------------------------------------------------------------6 hang 7 lie fill 27 hang 8 lie fill 48 hang 8 lie fill 35 hang 5 lie fill 29 hang 6 lie fill 48 hang 8 lie fill 35 hang 5 lie fill 29 hang 6 lie fill 48 hang 8 lie fill 3num 41 fill 2num 53 fill 8num 60 fill 2num 70 fill 4----------------------------------------------------------------------------8 hang 7 lie fill 99 hang 7 lie fill 89 hang 7 lie fill 85 hang 8 lie fill 99 hang 7 lie fill 88 hang 7 lie fill 9num 62 fill 9num 72 fill 6----------------------------------------------------------------------------5 hang 7 lie fill 65 hang 7 lie fill 65 hang 7 lie fill 6num 59 fill 6----------------------------------------------------------------------------Finish!!******************************************************************************* x =
看过的帮忙顶一下哈~~~
这位高人，你可以把从“;%需要解开的数独矩阵~待填的都填0”，这里开始的之后每一句是用来干什么，讲一下给大家听听吗？跪求详细讲解。当然做购买也是可以的，再次跪求楼主、、、
Q币、Q点、银行，各种渠道都可以，价格你说了算。我的QQ：
恩~现在比较忙~等晚上我把每句注释都加上在叫你吧~~ 不用买哈~~
学特色小吃哪家好? 找苏味轩 包教包会 一费到底 学2送2 自己创业做老板!
只是写来玩的~不用买~我晚上加上注释再发上来~~
完全看不懂 小白路过
单步跑一跑就能看明白了~~
我上次那个程序编译码后跟无编译码的误码率几乎一样，是啥问题啊，是不是调制解调的问题啊，我的老师叫我改用QAM来试试，我想用amodce函数，可是他的使用里面说输入的信号必须是偶数列 该咋改啊，求指导
%每个符号的比特数
%编码后码字长度
MSG=randint(L,1);
%随机产生L比特信号
TP=gftuple([-1:N-1]',M);
%产生加罗华域元素
PG=rspoly(N,K);
%产生生成式
[CODE,ADDED]=rsenco(MSG,TP,K);
MSG=[MSG;zeros(ADDED,1)];
BPCODE = amodce(CODE,1,'qam');
CODE_NO=awgn(BPCODE,SNR,'measured','linear');%加入高斯噪声
CODE_NOI=ademodce(CODE_NO,1,'qam');
[DEC,ERR,CCODE,ERR_C]=rsdeco(CODE_NOI,TP,K);%译码
[codenum,coderate]=biterr(CODE,CCODE');
%输出信道传输后误码率
%disp(['Error rate in the received code is:',num2str(coderate)])
[msgnum,msgrate]=biterr(DEC,MSG);
%输出译码纠错后误码率
%disp(['Error rate after decoding is:',num2str(msgrate)])
超级感谢，我该怎么谢你呢、、、，可算遇到高手了，麻烦您了。。
膜拜~ 求大神救命 ，有事先出去下。
这个跟调制方式应该没有关系吧？而且amodce是模拟调制啊~~你要传的是数字信号。。感觉主要应该是编码译码的问题~我改了一下你看看我这边的版本看不了你用的这些函数的用法~不知道你的CCODE,ERR_C是代表什么~~L=44000;M=4; %每个符号的比特数 N=2^M-1; %编码后码字长度 K=N-4; %信息长度 MSG=randint(L,1); %随机产生L比特信号 TP=gftuple([-1:N-1]',M); %产生加罗华域元素 PG=rspoly(N,K); %产生生成式 [CODE,ADDED]=rsenco(MSG,TP,K);%编码 MSG=[MSG;zeros(ADDED,1)]; %调整长度%CODE_NOI=awgn(CODE,3,'measured','linear');%CODE_NOI(find(CODE_NOI&0.5))=0;%CODE_NOI(find(CODE_NOI&=0.5))=1;for SNR=1:12
BPCODE = dmodce(CODE,1,1,'psk',2); %PSK调制，发送
CODE_NO=awgn(BPCODE,SNR,'measured','linear');%加入高斯噪声
CODE_NOI=ddemodce(CODE_NO,1,1,'psk',2);%接收,BPSK解调
[DEC,ERR,CCODE,ERR_C]=rsdeco(CODE_NOI,TP,K);%译码
[codenum,coderate(SNR)]=biterr(CODE,CODE_NOI);
%输出信道传输后误码率
%disp(['Error rate in the received code is:',num2str(coderate)])
[msgnum,msgrate(SNR)]=biterr(DEC,MSG);
%输出译码纠错后误码率
%disp(['Error rate after decoding is:',num2str(msgrate)])endsemilogy(1:12,coderate);hold onsemilogy(1:12,msgrate,'r');hold off
CCODE表示被纠正的码字 ERR_C表示CCODE中的错误数
诶~奇怪 LZ改了啥？咋不一样了呢
还是LZ最好，我的老师把题目丢给我就不见人了，难得问下他叫我改调制方式，害我研究一天的QAM，还弄不出来，欺骗我感情，深深伤了我的心啊，LZ赛高~
[codenum,coderate(SNR)]=biterr(CODE,CODE_NOI);这句改了~没有用CCODE和CODE比较~而是用解调的信号直接。。。
毕设老师都差不多~几乎不管事。。
请问你们那里有没有到晚上了啊 ，跪求楼主详解、、、求求楼主、解解小弟的燃眉之急，谢谢、
LZ正解。。。。我最早的程序就是用CCODE和CCODE_NOI比较的，后面改来改去不知啥时候就给改成那个了。。。一直没发现,LZ威武。
LZ是学生吗？还是工作了？
已经好了哈~~不好意思哈昨天晚上没有发~~%x=zeros(9,9);%x(1,5)=5;x(1,6)=7;x(1,8)=8;x(2,1)=3;%x(3,3)=2;x(3,4)=9;x(3,7)=4;x(4,1)=2;%x(4,4)=8;x(4,6)=9;x(4,7)=3;x(5,1)=4;%x(5,9)=7;x(6,3)=7;x(6,4)=4;x(6,6)=6;%x(6,9)=8;x(7,3)=6;x(7,6)=2;x(7,7)=7;%x(8,9)=5;x(9,2)=9;x(9,4)=3;x(9,5)=1;%需要解开的数独矩阵~待填的都填0x=zeros(9,9);x(1,5)=7;x(1,9)=1;x(2,1)=6;x(2,2)=4;x(2,6)=2;x(2,9)=9;x(3,3)=8;x(4,1)=8;x(4,3)=3;x(4,4)=5;x(5,3)=4;x(5,5)=8;x(5,7)=9;x(6,6)=9;x(6,7)=7;x(6,9)=6;x(7,7)=3;x(8,1)=9;x(8,4)=1;x(8,8)=6;x(8,9)=2;x(9,1)=5;x(9,5)=4;%x_temp=x;%for xi=1:9%
for xj=1:9%
x(xi,xj)=input('');%
end%endx_temp=x;%将x的值赋给x_temp对x_temp进行处理x保留初始值%%
while length(find(x_temp==0))&=1
%如果x_temp中为0的个数大于0（未填完）则继续循环
%将x_temp的值赋给x_flag如果依次循环后x_flag=x_temp则说明循环未对x_temp进行改变，即不能解开该题
a=find(x_temp==0);
%找出未待填的位置此时返回的值是1到81之间的数组成的数组%%
j=ceil(a/9);
%用a除9并向上取整就可得到未填数据素在列数的向量
i=mod(a,9);%将a模9得到i
i(find(i==0))=9;%将i中为0的数改为9就可得到未填数据所在的行数向量%%%将待填的空可填入的数据存入ept_temp中，不能填的数据位填0
for k=1:length(a)
%对于所有未填的数据进行循环
ept_temp(k,:)=1:9;
%对每个未填数据建立一个ept_temp向量用来存放在该点可填入的数据
%初始值为1到9
hang=find(x_temp(i(k),:)&0);
%找出该未填数据点所在行数
ept_temp(k,x_temp(i(k),hang))=0;
%将该行上已填的数据在该数据的ept_temp向量中清0
%表示改点不能再填入该行上已有的数据
lie=find(x_temp(:,j(k))&0);
%找出该未填数据点所在列数
ept_temp(k,x_temp(lie,j(k)))=0;
%将该列上已填的数据在该数据的ept_temp向量中清0
%表示改点不能再填入该列上已有的数据
zheng=x_temp(3*(ceil(i(k)/3)-1)+1:3*(ceil(i(k)/3)-1)+3,3*(ceil(j(k)/3)-1)+1:3*(ceil(j(k)/3)-1)+3);
%找出改点所在的9宫格
num=zheng(find(zheng&0));
%找出9宫格中已填的数据
ept_temp(k,num)=0;
%将九宫格内已填的数据在该数据的ept_temp向量中清0
%表示该点不能再填入所在九宫格中已有的数据
%经过这个循环可得到一个length(a)行9列的ept_temp矩阵，用来表示每个未填的点可填入的数据%%%按行搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
ept=ept_%将ept_temp的值赋给ept后面对ept进行处理
%对1到9行进行循环
hang_ept=ept(find(i==k),:);
%找出每一行未填数据点的所有可填入数据矩阵
temp1=sum(hang_ept,1);
%将该矩阵对列求和
%下面这个循环是遍历所得向量如果得到的向量在第q个位置上的值仍为q说明只能在一个位置填入i则找出该点并填入i
if(temp1(q)==q)
temp=find(i==k);
fprintf(1,'%d hang %d lie fill %d\n',k,j( temp(find(hang_ept(:,q)&0))),q);
x_temp(k,j( temp(find(hang_ept(:,q)&0))))=q;
end%%%按列搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
%对1到9列进行循环
lie_ept=ept(find(j==k),:);
%找出每一行未填数据点的所有可填入数据矩阵
temp2=sum(lie_ept,1);
%将该矩阵对列求和
%下面这个循环是遍历所得向量如果得到的向量在第q个位置上的值仍为q说明只能在一个位置填入i则找出该点并填入i
if(temp2(q)==q)
temp=find(j==k);
fprintf(1,'%d hang %d lie fill %d\n',i(temp(find(lie_ept(:,q)&0))),k,q);
x_temp(i(temp(find(lie_ept(:,q)&0))),k)=q;
end%%%按九宫格搜索找到具有唯一可填入数据的空格~并在那里填入这个数据
%对1到9的九宫格进行循环
kj=ceil(k/3);
%求出九宫格的列
ki=mod(k,3);
ki(find(ki==0))=3;
%求出九宫格的行
zheng_ept=ept(find(i&=(3*(ki-1)+1)&i&=(3*(ki-1)+3)&j&=(3*(kj-1)+1)&j&=(3*(kj-1)+3)),:);
%找出该九宫格内未填数据点的所有可填入数据矩阵
temp3=sum(zheng_ept,1);
%将该矩阵对列求和
%下面这个循环是遍历所得向量如果得到的向量在第q个位置上的值仍为q说明只能在一个位置填入i则找出该点并填入i
if(temp3(q)==q)
temp=find(i&=(3*(ki-1)+1)&i&=(3*(ki-1)+3)&j&=(3*(kj-1)+1)&j&=(3*(kj-1)+3));
fprintf(1,'%d hang %d lie fill %d\n',i(temp(find(zheng_ept(:,q)&0))),j(temp(find(zheng_ept(:,q)&0))),q);
x_temp(i(temp(find(zheng_ept(:,q)&0))),j(temp(find(zheng_ept(:,q)&0))))=q;
end%%%遍历所有空格的可填入数据，找到只有一个可填入数据的点并填入该数据
for k=1:length(a)
%遍历所有数据点的可填入数据向量
if(length(find(ept(k,:)&0))==1)
%如果在某一数据点可填入数据个数为1则在该位置填入此数据
fprintf(1,'num %d fill %d\n',a(k),find(ept(k,:)&0));
x_temp(a(k))=find(ept(k,:)&0);
clear ept_%%%经过一次循环如果x_temp没变化则不能填满数据~~报错
if(x_flag==x_temp)
error('Error!!Can not fill all block!!');
fprintf(1,'----------------------------------------------------------------------------\n');end%能推出大循环说明x_temp中所有未填的数据点都已经填满数据fprintf(1,'Finish!!\n');fprintf(1,'*******************************************************************************\n');x=x_%将x_temp赋给xx你看看这样可以不？
昨天跟理论误码率比较感觉差距比较大~应该不是调制的问题~感觉应该是数据比较的问题~~所以就改了一下。。。没什么威武的~~只不过是我敢随便改程序罢了
也是大四再做毕设额~~很羡慕LZ这样能有实际的东西做啊~~我的老师一直让我研究理论~~整天推公式~~郁闷
额 我要是理论研究我会疯的，看见公式头都晕。
登录百度帐号推荐应用}