数学建模论文

2012-2013（2）建模实践论文Kakuro数独问题队员1：队员2：队员3：建模实践论文成绩考核表学生姓名1专业班级学号学生姓名2专业班级学号学生姓名3专业班级学号题目Kakuro数独问题评审者考核项目评分（每项满分20分）学生1学生2学生31上课态度与遵守纪律的情况2完成任务的情况与水平（工作量）3论文质量（正确性、条理性、创造性和实用性）4技术水平（理论、分析、计算、验证以及创新性）5论文答辩（讲述的条理性、系统性，回答问题的正确性）总评成绩总评成绩等级（优、良、中、及格、不及格）指导教师签字：Kakuro数独问题摘要数独的历史可以追溯到1783年，瑞士数学家欧拉发明了一种当时称作“拉丁方块”（LatinSquare）的游戏，这个游戏是一个nn的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。后被称为Sudoku数独。当大家还在钻研Sudoku数独，究竟填写1至9这几个数字的窍门时，另一个相类似的游戏于最近迅速火爆，这就是Kakuro。Kakuro在英美等地人气急升，它的好玩之处在于既有Sudoku的逻辑推理，还多了加数运算。Kakuro是一款在游戏中需要增加运算(加法)的智力游戏，逻辑推理性很强。本文主要通过建立数学求解模型解决Kakuro数独的解法，以及相关问题。主要包括以下几个问题：1.建立数学模型，编写MatLab程序求解Kakuro数独；2.算法复杂性讨论；3.为Kakuro数独问题划分级别，给出一种划分方式；产生不同级别且有唯一解的Kakuro数独。关键词：数独，求解模型，复杂性讨论，唯一性。一、问题重述下图就是一道难度级别较高的Kakuro数独问题。Kakuro数独规则如下：1．在空格中填入数字1～9；数字0不能出现。2．带斜线的方格，斜线上方的数字等于该方格右面对应的一组水平空格里的数字之和；斜线下方的数字，等于该方格下面对应一组垂直空格里的数字之和。3．同一数字在每组水平（垂直）空格里只能出现一次。810的Kakuro数独题针对Kakuro数独，完成以下问题：1．讨论求解模型或方法,并给出算法复杂性讨论。2．如何对Kakuro数独问题划分为不同级别，并给出一种划分方式，并给出实例。3．如何产生不同级别的Kakuro数独，并保证产生的数独问题为唯一解。假定所有kakuro数独都以108为标准进行讨论。二、模型分析求解模型包括三个重要的子模型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和3只能由2和3相加得到，即B为2，C为3。41023116B1044A333116C相同道理，右下侧的空格组里，提示码10（由上往下加总）及提示码11（向右的加总），两回交叠的区块里标有一个D。因为432110，532111都只有一种分解方式，D为1或2或3，又因为D上为2，D右为3，所以D为1，从而推出E只能为3或4，因为3216，分解式唯一，所以E为3，则由加法规律可计算出第二行，第三行的其他空格。41023116E21010244133321311111D363410231161321010213444133321311111F13依照这样的逻辑推论，F处从右往左看，F可能为2或5，从上往下看F为1或2，可判定F为2，通过计算可得其他空格的结果，所以该数独的最终答案为（3）、审视各个横列、竖列及根据其和罗列出的可能的数字结果，若发现某一个数字在各个横列、竖列出现的次数仅一次，则可以确定该空格的解为此数字。并6341023116132101021344413332131111152136321根据第二条的方法排除与此空格相关列或方格中相同的数字。（4）、审视各个横列、竖列中罗列的各个可能的结果，找出相对称的两个数组合的空格（或3个、4个及其以上个数的组合），并确定这两个空格（或3个、4个及其以上个数的组合）的数字只可能为这两个数字，即两个数字在这两个空格的位置可以交换，但不可能到该行、该列的其他位置。根据此结果可以排除相关列罗列出相关数字的可能，并缩小范围。（该步骤处理的难度相对复杂，需要在积累一定经验的基础上进行，也是最终求解的关键）（5）、反复使用2、3、4提到的步骤，逐步得到一个一个空格的解，并将先前罗列的各种可能的结果一个一个排除，使可能的范围越来越小，直至得到最后结果。2.通过数学软件求解,建立数独问题的数学模型现在以1210的数独图为例介绍。程序输入，一个1210的输入矩阵。考虑到Kakuro数独对横向和纵向的加和都有要求，且交叉点为同一个数，所以我们考虑到将要求简化，如果纵向没有任何要求，那么就简单多了。简化后就变成了如下两个问题：在空格中填入数字1～9，数字0不能出现；每个格里的数字等于该方格右面对应的一组水平空格里的数字之和；同一数字在每组水平空格里只能出现一次，垂直空格中的数字无要求131729162751424172491617173318321720333181616258162914420172116292424161621141423221616514241617181720331816同样道理，如果横向没有要求，竖向要求加和，则得到如下问题：在空格中填入数字1～9，数字0不能出现；每个格里的数字等于该方格下面对应的一组垂直空格里的数字之和；同一数字在每组垂直空格里只能出现一次，水平空格中的数字无要求按照以上简化，只要两个问题的解是相同的即对应的空白格中的数字完全相同，则就是Kakuro数独的解。那么下面的问题就是如何解上面的两种数独：由于垂直（水平）方向上没有数字不相等的要求，那么就可以单独拿出一行816421292416211423221616131729162724179173332316252914201716241614（一列）求解即可。例如：第二行32415；869514将不需要填写的格子和有已知条件数字的格子表示成In，则该行可以表示成16种行向量：InInInInInIn9541；InInInInInIn9514；InInInInInIn5941；InInInInInIn5914；InInInInInIn9532；InInInInInIn9523；InInInInInIn5932；InInInInInIn5923；InInInInInIn8641；InInInInInIn8614；InInInInInIn6841；InInInInInIn6814；InInInInInIn8632；InInInInInIn8623；InInInInInIn6832；InInInInInIn6823。按此方法去解其它行（列），再合并成矩阵InInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInIn其中空格表示需要填数字的格子。根据此法可得到两个矩阵A，B（一个是根据行算出的，另一个是根据列算出的），如果两个矩阵ijijBA则该矩阵就是Kakuro数独的解。但是矩阵A和矩阵B都有很多种可能，下面的问题就是根据任意一个Kakuro数独问题得出所有的矩阵A和所有的矩阵B，然后进行比较。因此，我们需要一些剪枝来优化算法，在不影响结果的条件下，进一步减少所获得的矩阵A和矩阵B的数量。我们采用如下优化：（1）技巧性剪枝一：唯一分解方式数和中有些和值只有一种分解方式5142字组3=1+24=1+316=7+917=8+93字组6=1+2+37=1+2+423=6+8+924=7+8+94字组10=1+2+3+411=1+2+3+529=5+7+8+930=6+7+8+95字组15=1+2+3+4+516=1+2+3+4+634=4+6+7+8+935=5+6+7+8+96字组21=1+2+3+4+5+622=1+2+3+4+5+738=3+5+6+7+8+939=4+5+6+7+8+97字组28=1+2+3+4+5+6+729=1+2+3+4+5+6+841=2+4+5+6+7+8+942=3+4+5+6+7+8+98字组36=1+2+3+4+5+6+7+837=1+2+3+4+5+6+7+938=1+2+3+4+5+6+8+939=1+2+3+4+5+7+8+940=1+2+3+4+6+7+8+941=1+2+3+5+6+7+8+942=1+2+4+5+6+7+8+943=1+3+4+5+6+7+8+944=2+3+4+5+6+7+8+98字组中每一个和值都有唯一解。9字组由于组内数字不能重复，9字组只能是1～9各填一遍，和值只能是45。（2）技巧性剪枝二：重叠组重叠组在数和中有很重要的作用，当重叠的两个组有一个是唯一解时就较为简单。这种情况常常用来做解题的突破口。以上文的题目为例（a是第10行第10列）：acb1416因为16只能分解成9716,而14可分解为869514，则可判断a只能为9，所以相应可得7b，5c。同理可确定下列空格（a是第2行第4列）182451713cba因为5可分解为32415；76859413。所以a只能为4，所以1b，9c重叠的组有两个是唯一解时，则更为简单。例如：xxxa1623因为23只能分解为98623，16只能分解为9716，所以a只能为9。通过这两个优化剪枝，可以先确定一些所求矩阵的值，使得求出矩阵和矩阵比较的计算量大大减少。例如该例题，通过上述剪枝确定后的矩阵为：InInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInInIn97595797577989514优化以后，通过一个程序函数z=paixu(a),(附录)找出所有的矩阵A和B，该函数的作用是输入任何一行或