《数学建模最终论文c题》由会员分享，可在线阅读，更多相关《数学建模最终论文c题（21页珍藏版）》请在金锄头文库上搜索。
1、Kakuro数独模型的建立求解模型包括三个重要的子模型1：建立一个数学模型对kakuro中可能出现的和数进行所有可能的拆分；2：建立一个数学模型对一个已知的kakuro求解；3：产生有唯一解的kakuro；由于第二步对kakuro的求解采用面向对象的工具软件，所以第二步和第一步是相互独立的。在第三步的产生过程中，我们只是粗略地考虑了如何产生不同等级的kakuro和保证kakuro有唯一解。对等级的划分我们还另外进行了讨论。在第三步模型的建立中要用到第一个和第二个模型。一.对Kakuro数独进行求解1.通解方法-人工试探法 现在我们必须做的第一件事是考虑怎样解决Kakuro。我们现在使用逻辑推理
2、法和一点数学来解决题目要求的数模题，这里应用的方法将会被应用到我们产生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相加
3、，也算犯规。所以“A”只可能是“1”。（该情况出现的可能往往不多，除了较简单的数独题，但这是一个必要的过程，而且在随后的过程中要反复使用此方法。） 依照这样的逻辑推论，如果“A”等于1，它上面的空格就是3（因为1+3=4），而它右边的空格就会是2。2上方的两个空格依此逻辑解出。相同道理，右上侧的空格组里，提示码3（由上往下加总）及提示码4（向右的加总），两回交叠的区块里标有一个“B”。跟step2的判断方式一样，所以“B”只能是“1”。依照这样的逻辑推论，如果“B”长等于1，它下面的空格就是2（因为1+2=3），而它左边的空格就会是3。3下方的空格依此逻辑解出。解开其余的谜底，就只需要简单的数
4、字运算而已. 3、审视各个横列、竖列及根据其和罗列出的可能的数字结果，若发现某一个数字在各个横列、竖列出现的次数仅一次，则可以确定该空格的解为此数字。并根据第二条的方法排除与此空格相关列或方格中相同的数字。 4、审视各个横列、竖列中罗列的各个可能的结果，找出相对称的两个数组合的空格（或3个、4个及其以上个数的组合），并确定这两个空格（或3个、4个及其以上个数的组合）的数字只可能为这两个数字，即两个数字在这两个空格的位置可以交换，但不可能到该行、该列的其他位置。根据此结果可以排除相关列罗列出相关数字的可能，并缩小范围。（该步骤处理的难度相对复杂，需要在积累一定经验的基础上进行，也是最终求解的关键
5、） 5、反复使用2、3、4提到的步骤，逐步得到一个一个空格的解，并将先前罗列的各种可能的结果一个一个排除，使可能的范围越来越小，直至得到最后结果。 2. 通过数学软件求解,建立数独问题的数学模型现在以810的数独图为例介绍。程序输入，一个810的输入矩阵. 算法的主要思想如下：首先将线索格里的数据进行拆分；接着根据被拆分的数被”回”限制的个数，选出合适的组合；然后据此确定出可以确定的数；再尽量减少未定格子的变量，试探，回溯，最终求解。为了随时调用线索格里的提示码的分解组合，对于810的数独，其每行每列数的和均小于45而大于3，建立一C语言程序将其可能的组合全部求出.其源程序如下：#includ
6、e #include long res1024;void fen(long n, long m) /n是需要拆分的数，m是拆分的个数。long rest;int i,j;for(i=1;iresm-1) /拆分的数大于前一个，保证不重复。(第一个是0，虚拟的，不计入结果)resm=i； ;/将这个数计入结果中。rest=n-i; /剩下的数是n-i。if(rest=0&m1) /如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。for(j=1;j=m;j+)if(resm0.1&n45.1)memset(res,0,sizeof(res);Total=0;fen(n,
7、1);return 0;运行这个程序，可以得出345之间的整数拆分结果。其结果如下（其中前面表示被拆分的数，后面的表明差分结果。由于拆分的结果必须在19之间，故写在一起的几位数为一种拆分结果.）：3 124 13 5 14 236 15 24 123 7 16 25 34 124 8 17 26 35 125 1349 18 27 36 45 126 135 23410 19 28 37 46 127 136 145 235 123411 29 38 47 56 128 137 146 236 245 123512 39 48 57 129 138 147 156 237 246 345 12
8、36 124513 49 58 67, 139 148 157 238 247 256 346 1237 1246 134514 59 68 149 158 167 239 248 257 347 356 1238 1247 1256 1346 234515 69 78 159 168 249 258 267 348 357 456 1239 1248 1257 1347 1356 2346 1234516 79 169 178 259 268 349 358 367 457 1249 1258 1267 1348 1357 1456 2347 2356 1234617 89 179 269
9、278 359 368 458 467 1259 1268 1349 1358 1367 1457 2348 2357 2456 12347 1235618 189 279 369 378 459 468 567 1269 1278 1359 1368 1458 1467 2349 2358 2367 2457 3456 12348 12357 1245619 289 379 469 478 568 1279 1369 1378 1459 1468 1567 2359 2368 2458 2467 3457 12349 12358 12367 12457 1345620 389 479 569
10、 578 1289 1379 1469 1478 1568 2369 2378 2459 2468 2567 3458 3467 12359 12368 12458 12467 13457 2345621 489 579 678 1389 1479 1569 1578 2379 2469 2478 2568 3459 3468 3567 12369 12378 12459 12468 12567 13458 13467 23457 12345622 589 679 1489 1579 1678 2389 2479 2569 2578 3469 3478 3568 4567 12379 1246
11、9 12478 12568 13459 13468 13567 23458 23467 12345723 689 1589 1679 2489 2579 2678 3479 3569 3578 4568 12389 12479 12569 12578 13469 13478 13568 14567 23459 123458 12346724 789 1689 2589 2679 3489 3579 3678 4569 4578 12489 12579 12678 13479 13569 13578 14568 23469 23478 123459 123468 12356725 1789 26
12、89 3589 3679 4579 4678 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567 123469 123478 123568 12456726 2789 3689 4589 4679 5678 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568 123479 123569 123578 124568 13456727 3789 4689 5679 12789 13689 14589 14679 15678 23
13、589 23679 24579 24678 34569 34578 123489 123579 123678 124569 124578 134568 23456728 4789 5689 13789 14689 15679 23689 24589 24679 25678 34579 34678 123589 123679 124579 124678 134569 134578 234568 123456729 5789 14789 15689 23789 24689 25679 34589 34679 35678 123689 124589 124679 125678 134579 1346
14、78 234569 234578 123456830 6789 15789 24789 25689 34689 35679 45678 123789 124689 125679 134589 134679 135678 234579 234678 1234569 123457831 16789 25789 34789 35689 45679 124789 125689 134689 135679 145678 234589 234679 235678 1234579 123467832 26789 35789 45689 125789 134789 135689 145679 234689 235679 245678 1234589 1234679 123567833 36789 45789 126789 135789 145689 234789 235689 245679 345678 1234689 1235679 124567834 46789 136789 145789 235789 245689 345679 1234789 1235689 1245679 134567835 56789 146789 236789 245789 345689 1235789 1245689 134567
