《借助计算机快速解决数论问题》由会员分享，可在线阅读，更多相关《借助计算机快速解决数论问题（12页珍藏版）》请在金锄头文库上搜索。
1、借助计算机快速解决数论问题一、解数独引言与问题背景：下面是一道信息学奥赛NOIP 的提高组复赛题靶形数独的方格同普通数独一样，在9 格宽 9 格高的大九宫格中有9 个 3 格宽 3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中， 有一些数字是已知的， 根据这些数字， 利用逻辑推理， 在其他的空格上填入1 到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。上图具体的分值分布是：最里面一格为10 分，外面的一圈每个格子为9 分，再外面一圈每个格子为8
2、 分，外面一圈每个格子为7分，最外面一圈每个格子为6 分，如上图所示。比赛的要求是： 每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。分析问题对于这种解数独，我认为应该用穷举算法（如果有更好的算法请告诉我）。也就是每次在格内由19 列出来，然后进行检测是否可以放置，然后递归到下一个格子。就这一题而言， 我开始想到了贪心算法， 就是每个格子由 91 递减，但是格子的顺序是由中间开始螺旋向外伸开，这样只要完成数独一次，就可以达到目的。但是，这样所使用的寻路算法在实际编译过程中占用了大
3、量时间，于是贪心算法失败，改用穷举法。使用穷举，就免了寻路这一步，但是要做很多次才能达到目的。说一下程序的理念。首先由第一格开始，每一格用for 循环 19 ，如果其中有一位数可以填入这个格子，那就向右递归到下一个格子。重复刚才的动作，直到最后一个格子都完成了，那么整个数独就完成了。经过测试，这样的算法快很多。下面将展示完整 C 语言程序代码。完整代码如下经运行通过#include“stdio.h“ int num99=0; int findx(int x,int y) if(y=8)return x+1; else return x; int findy(int x,int y) if(y=
4、8)return 0; else return y+1; void print() int x,y; for(x=0;x0;i-) if(cando(i,x,y)=1) numxy=i; if(n=80)print();if(i=1)return 0; work(n+1,findx(x,y),findy(x,y); numxy=0; int main() /freopen(“1.txt“,“r“,stdin); /freopen(“2.txt“,“w“,stdout); int x=4,y=4,i,t; for(i=0;i int number654; int select65; int ar
5、ray34; int count; int selecount; int larray165; int lcount1; main() int i,k,flag,cc=0,i1,i3; printf(“There are magic squares with invertable primes as follow:n“); for(i=123;i=1;j-,num/=10) numberij=num%10; copy_num(int i) int j; for(j=1;j=0(*p)+) ; if(*p=*pcount) *p=0; return 0; if(num!=larrayn-2*p)
6、 return 0; return 1; find1(int i) int num,j; for(num=0,j=0;j=0j+) ; if(j=count) j=0; return 0; if(num=numberj0) return 1; else return 0; p_array(void) int i,j; for(i=0;i void main() int aNN,i,j,k; for(i=0;iN-1) /* 当列数加到最后一行，返回到第一行*/ j=0; if(aij=0) aij=k; else i=i+2; j=j-1; aij=k; for(i=0;i void main
7、() int aNN=0,i=0,j,k; j=(N-1)/2; i=0; for(k=1;kN-1) j=0; else if(!aij) aij=k+; i=i-1;j=j+1; else i=i+2;j=j-1; for(i=0;iN;i+) for(j=0;jN;j+) printf(“%5d“,aij); printf(“nn“); /*这个算法简洁得让人感动,可以轻松算出任意阶数的宫格*/ 其他思路简述：基础摒除法基础摒除法就是利用1 9 的数字在每一行、每一列、每一个九宫格都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。实际寻找解的过程为：寻找九
8、宫格摒除解：找到了某数在某一个九宫格可填入的位置只余一个的情形；意即找到了该数在该九宫格中的填入位置。寻找列摒除解：找到了某数在某列可填入的位置只余一个的情形；意即找到了该数在该列中的填入位置。寻找行摒除解：找到了某数在某行可填入的位置只余一个的情形；意即找到了该数在该行中的填入位置。唯一解法当某行已填数字的宫格达到8 个,那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解 . 当某列已填数字的宫格达到8 个,那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为列唯一解. 当某九宫格已填数字的宫格达到8 个,那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数
9、字了。成为九宫格唯一解. 唯余解法唯余解法就是某宫格可以添入的数已经排除了8 个,那么这个宫格的数字就只能添入那个没有出现的数字. 区块摒除法区块摒除法是基础摒除法的提升方法,是直观法中使用频率最高的方法之一. 余数测试法所谓余数测试法就是在某行或列,九宫格所填数字比较多,剩余 2 个或 3 个时,在剩余宫格添入值进行测试的解题方法. 隐性唯一候选数法当某个数字在某一列各宫格的候选数中只出现一次时，那么这个数字就是这一列的唯一候选数了这个宫格的值就可以确定为该数字这时因为，按照数独游戏的规则要求每一列都应该包含数字19，而其它宫格的候选数都不含有该数，则该数不可能出现在其它的宫格，那么就只能出
10、现在这个宫格了对于唯一候选数出现行,九宫格的情况，处理方法完全相同。三链数删减法找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3 个的情形，进而将这 3 个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。隐性三链数删减法在某行，存在三个数字出现在相同的宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数那么这三个宫格的候选数中的其它数字都可以排除当隐形三链数出现在列，九宫格，处理方法是完全相同的矩形顶点删减法矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶点删减法在识别时比较不容易找到，所以最好先使用其它的方法。三链列删减法三链
11、列删减法是矩形顶点删减法的扩展，如果不清除矩形顶点删减法，可以参考矩形顶点删减法，以便于更容易理解本节内容。利用 “ 找出某个数字在某三列仅出现在相同三行的情形，进而将该数字自这三行其他宫格候选数中删减掉” ； 或“ 找出某个数字在某三行仅出现在相同三列的情形，进而将该数字自这三列其他宫格候选数中删减掉” 的方法就叫做三链列删减法。关键数删减法在进入到解题后期，利用前面讲到的唯一候选数法、隐性唯一候选数法、区块删减法、数对删减法、隐性数对删减法、三链数删减法、隐性三链数删减法、矩形顶点删减法、三链列删减法都无法有进展的时候，可以考虑使用关键数删减法。关键数删减法就是在后期找到一个数，这个数在行（或列，九宫格）仅出现两次的数字。我们假定这个数在其中一个宫格类，继续求解，如果发生错误，则确定我们的假设错误。如果继续求解仍然出现困难，不妨假设这个数在另外一个宫格，看能不能得到错误。这就是关键数删减法.
