搜索
Kakuro数独模型的建立求解模型包括三个重要的子模型1：建立一个数学模型对kakuro中可能出现的和数进行所有可能的拆分；2：建立一个数学模型对一个已知的kakuro求解；3：产生有唯一解的kakuro；由于第二步对kakuro的求解采用面向对象的工具软件，所以第二步和第一步是相互独立的。在第三步的产生过程中，我们只是粗略地考虑了如何产生不同等级的kakuro和保证kakuro有唯一解。对等级的划分我们还另外进行了讨论。在第三步模型的建立中要用到第一个和第二个模型。一.对Kakuro数独进行求解1.通解方法--人工试探法现在我们必须做的第一件事是考虑怎样解决Kakuro。我们现在使用逻辑推理法和一点数学来解决题目要求的数模题，这里应用的方法将会被应用到我们产生kakuro的模型中。根据以下方法可以确保最终得到数独的解，而且通过手工运算的时间基本可以控制在2个小时，不论难易程度，所以此方法可以作为取得数独答案的一般解法。1、要解题，可以很快就看到提示的线索组合。以右图为例，注意左下侧的空格组里，有一个提示码4（由上往下的加总）以及提示码3（向右的加总），两回交叠的区块里标有一个“A”。2、只有1、2相加能得到3，1、3相加得到4，所以“A”只能是1、2、3其中一个数字。但是，如果放3，提示码3那一列，就会得出一个不可能的组合，即3、0，如果放2，提示码4的那一列则会变成2、2相加，也算犯规。所以“A”只可能是“1”。（该情况出现的可能往往不多，除了较简单的数独题，但这是一个必要的过程，而且在随后的过程中要反复使用此方法。）依照这样的逻辑推论，如果“A”等于1，它上面的空格就是3（因为1+3=4），而它右边的空格就会是2。2上方的两个空格依此逻辑解出。2相同道理，右上侧的空格组里，提示码3（由上往下加总）及提示码4（向右的加总），两回交叠的区块里标有一个“B”。跟step2的判断方式一样，所以“B”只能是“1”。依照这样的逻辑推论，如果“B”长等于1，它下面的空格就是2（因为1+2=3），而它左边的空格就会是3。3下方的空格依此逻辑解出。解开其余的谜底，就只需要简单的数字运算而已.3、审视各个横列、竖列及根据其和罗列出的可能的数字结果，若发现某一个数字在各个横列、竖列出现的次数仅一次，则可以确定该空格的解为此数字。并根据第二条的方法排除与此空格相关列或方格中相同的数字。4、审视各个横列、竖列中罗列的各个可能的结果，找出相对称的两个数组合的空格（或3个、4个及其以上个数的组合），并确定这两个空格（或3个、4个及其以上个数的组合）的数字只可能为这两个数字，即两个数字在这两个空格的位3置可以交换，但不可能到该行、该列的其他位置。根据此结果可以排除相关列罗列出相关数字的可能，并缩小范围。（该步骤处理的难度相对复杂，需要在积累一定经验的基础上进行，也是最终求解的关键）5、反复使用2、3、4提到的步骤，逐步得到一个一个空格的解，并将先前罗列的各种可能的结果一个一个排除，使可能的范围越来越小，直至得到最后结果。2.通过数学软件求解,建立数独问题的数学模型现在以8×10的数独图为例介绍。程序输入，一个8×10的输入矩阵.算法的主要思想如下：首先将线索格里的数据进行拆分；接着根据被拆分的数被”回”限制的个数，选出合适的组合；然后据此确定出可以确定的数；再尽量减少未定格子的变量，试探，回溯，最终求解。为了随时调用线索格里的提示码的分解组合，对于8×10的数独，其每行每列数的和均小于45而大于3，建立一C语言程序将其可能的组合全部求出.其源程序如下：#includestdio.h#includestring.hlongres[1024];voidfen(longn,longm)//n是需要拆分的数，m是拆分的个数。{4longrest;inti,j;for(i=1;i=n;i++)//从1开始尝试拆分。{if(ires[m-1])//拆分的数大于前一个，保证不重复。(第一个是0，虚拟的，不计入结果){res[m]=i；;//将这个数计入结果中。rest=n-i;//剩下的数是n-i。if(rest==0&&m1)//如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。{for(j=1;j=m;j++){if(res[m]10.0)printf(%ld,res[j]);}printf(\n);}else{fen(rest,m+1);//否则将剩下的数进行进度为m+1拆分。}res[m]=0;//取消本次结果，进行下一次拆分。}}}intmain(){longn;printf(Inputn:);scanf(%ld,&n);while(n0.1&&n45.1){memset(res,0,sizeof(res));Total=0;fen(n,1);return0;}}}运行这个程序，可以得出3～45之间的整数拆分结果。其结果如下（其中前面表示被拆分的数，后面的表明差分结果。由于拆分的结果必须在1～9之间，故写在一起的几位数为一种拆分结果.）：31241351423561524123716253412481726351251349182736451261352341019283746127136145235123411293847561281371462362451235123948571291381471562372463451236124513495867,1391481572382472563461237124613451459681491581672392482573473561238124712561346234515697815916824925826734835745612391248125713471356234612345167916917825926834935836745712491258126713481357145623472356123461789179269278359368458467125912681349135813671457234823572456123471235618189279369378459468567126912781359136814581467234923582367245734561234812357124561928937946947856812791369137814591468156723592368245824673457123491235812367124571345620389479569578128913791469147815682369237824592468256734583467123591236812458124671345723456214895796781389147915691578237924692478256834593468356712369123781245912468125671345813467234571234562258967914891579167823892479256925783469347835684567123791246912478125681345913468135672345823467123457236891589167924892579267834793569357845681238912479125691257813469134781356814567234591234581234672478916892589267934893579367845694578124891257912678134791356913578145682346923478123459123468123567251789268935893679457946781258912679134891357913678145691457823479235692357824568345671234691234781235681245672627893689458946795678126891358913679145791467823489235792367824569245783456812347912356912357812456813456727378946895679127891368914589146791567823589236792457924678345693457812348912357912367812456912457813456823456728478956891378914689156792368924589246792567834579346781235891236791245791246781345691345782345681234567295789147891568923789246892567934589346793567812368912458912467912567813457913467823456923457812345683067891578924789256893468935679456781237891246891256791345891346791356782345792346781234569123457863116789257893478935689456791247891256891346891356791456782345892346792356781234579123467832267893578945689125789134789135689145679234689235679245678123458912346791235678333678945789126789135789145689234789235689245679345678123468912356791245678344678913678914578923578924568934567912347891235689124567913456783556789146789236789245789345689123578912456891345679234567836156789246789345789123678912457891345689234567912345678372567893467891246789134578923456891234567938356789125678913467892345789123456893913567892346789123457894014567892356789123467894124567891235678942345678912456789433456789442345678945123456789该部分视图保存于附录.算法流程(1)设置初始化的方案（给变量赋初值，读入已知数据等）；程序输入，一个8×10的输入矩阵，有数字的地方就是指定的数字（线索格的数字以0|0的形式输入），没有数字的地方，实格子输入为00，空格子为0。(2)变换方式去试探，若全部试完则转(7)；(3)判断此法是否成功，不成功则转(2)；(4)试探成功则前进一步再试探。；(5)正确方案还未找到则转(2)；(6)已找到一种方案则记录；(7)退回一步（回溯），若未退到头则转(2)；(8)已退到头则结束；算法应用举例:1.我们建立一个由0和1组成的一维未知数数组（0代表该处数值已知或不可填，1代表数值已知）和一个每一个原胞内含1～9的另一个候选数数组我们在这里使用两个一维的数组并且它的第一个元素为零。第一个一维数组用来存放横向元素的和，第二个一维数组用来存放竖向元素的和。然后我们用前面给出的算法对给定已知条件的kakuro求解，举个简单的例子。举例简单的4*4例子：7我们先建立两个如下数组：011111110;01234567891234567891234567891234567891234567891234567891234567890;还有两个和值数组(横向优先):1-17,