数独问题-数学建模.doc

《数独问题-数学建模.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数独问题摘要本文是对数独问题进行求解。结合数独生成的特点，立足于题中数独建模和求解的要求，建立了数独难度分析函数和整数规划模型。对于问题一，首先研究数独难度的影响因素，通过综合分析数独的特点结构，得出可以在常数时间内计算出来以衡量数独的难易程度。通过计算可知，根据数独难度的划分得到如下结论：数独难度系数为4，达到了极难的程度。对于问题二，我们通过对此数独的分析和讨论，利用穷举法，通过matlab软件编程求解，最终得出答案，如表1所示。对于问题三，我们利用回溯法思想，建立求解模型，具体算法一般采用如下步骤：1).在此数独初盘选择一个空单

2、元格；2).取这个单元格中一个可能的候选数；3).将这个候选数填入单元格中，迭代完成数独；4).若这个候选数推导得到一个无效数独终盘，返回此单元格取其他候选数；对于问题四采用整数规划模型，采用三维0-1变量的方法，运用lingo软件编程求解。最终得到答案，如表1所示。表1数独问题的唯一解812753649943682175675491293154237896369845721287169534521974368438526917796318452关键词：数独数独难度分析穷举法回溯法整体规划151问题的重述前段时间芬兰一位数学家号称设计

3、出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。该数独如下图所示：数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，且不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。根据以上描述，试完成以下问题：1.分析此数独的难度；2.用穷举算法求解数独；3.设计此数独求解的较优的算法；4.建立数独求解模型并给出此数独的答案。2模型的基本假设1该数独问题存在唯一解。3符号说明表示空单元格候选数表示候选数数的加权函数表示数独

4、空单元格中的候选数数目函数表示该数独的空格处表示该数独难度的函数表示数k是否填入数独方中的（i，j）处表示往空格处填入0后数独方中（i，j）处的数表示经过求解后数独方中（i，j）处的数154模型的建立与求解4.1问题14.1.1数独难度的影响因素通过对数独的分析与研究，数独难度与数独候选数、逻辑推理方法、搜索步数、空格数以及空格的分布情况都有密切的关系。通过大量的计算观察发现，用到的逻辑与推理方法越复杂，那么在数独中出现的候选数越多;反之，在数独题中出现的候选数越多，解决数独题所用到的逻辑推理方法一般也越难。解答一个数独所用到的搜索步

5、数越多，数独中的候选数越多。反之，一般情况下也成立。另外数独中的空格数以及空格的分布情况与候选数也有同样类似的关系。综合这几个影响数独难度的几种因素，分析候选数和空格数为主要影响因素，再根据其构造加权规范函数，计算数值来衡量数独难度。4.1.2函数的建立加权规范函数建立在候选数列表的基础上。根据候选数列表，计算出每一个空单元格中的候选数数目，将候选数数目与其相对应的加权函数结合起来，计算加权规范函数。定义单元格中的候选数数目函数为，这个函数仅适用于数独P中的空单元格，而数独中的空单元格可以表示为(1)有个候选数的候选数数目函数(2)我

6、们赋予它相应的加权函数，从而得到加权函数(3)不能准确的反映数独难度，受数独中空单元格数目影响很大，呈正向关系，如在数独中删除单元格，数独空单元格数增加，导致增加，即空格数越多，越大，然而这并不符合所有的数独。为了排除这一影响，将加权函数规范，得到加权规范函数：15(4)根据以上的分析，对于某单元格，其候选数数越大，其对应的加权函数也应越大。我们采用指数函数”计算数独的，其中为某空单元格的候选数数目。计算发现，与数独难度是正相关的，即越大，数独的难度越大。4.1.3函数的求解根据题中给出的数独，按照数独游戏应该满足的条件，可以得到该数

7、独的空格处的候选数列表，如下表2所示：表2空格处候选数列表8124624569234712357123413569457913456791245912436125781248158945789145791456745634891348245813456123469524692389236871689248912469123691236826923894572891269246792468246791268268956893245692345723412347923723493596823467234685236723469391237

8、9235679256723781236781236842572357根据表2，把所得变量带入式(3)得：(5)由代入式(4)式中得：(6)4.1.4数独难度的划分根据计算所得大小，我们将数独题难度分为四个区间，分别表示简