数独问题数学建模.docVIP

PAGE PAGE 7 数独问题 摘要 本文是对数独问题进行求解。结合数独生成的特点，立足于题中数独建模和求解的要求，建立了数独难度分析函数和整数规划模型。 对于问题一，首先研究数独难度的影响因素，通过综合分析数独的特点结构，得出可以在常数时间内计算出来以衡量数独的难易程度。通过计算可知，根据数独难度的划分得到如下结论： 数独难度系数为4，达到了极难的程度。 对于问题二，我们通过对此数独的分析和讨论，利用穷举法，通过matlab软件编程求解，最终得出答案，如表1所示。 对于问题三，我们利用回溯法思想，建立求解模型，具体算法一般采用如下步骤： 1).在此数独初盘选择一个空单元格； 2).取这个单元格中一个可能的候选数； 3).将这个候选数填入单元格中，迭代完成数独； 4).若这个候选数推导得到一个无效数独终盘，返回此单元格取其他候选数； 对于问题四采用整数规划模型，采用三维0-1 变量的方法，运用lingo软件编程求解。最终得到答案，如表1所示。 表1 数独问题的唯一解 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 9 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2 关键词：数独 数独难度分析 穷举法 回溯法 整体规划 1问题的重述 前段时间芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。该数独如下图所示： 数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，且不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。 根据以上描述，试完成以下问题： 1. 分析此数独的难度； 2. 用穷举算法求解数独； 3. 设计此数独求解的较优的算法； 4. 建立数独求解模型并给出此数独的答案。 2模型的基本假设 1该数独问题存在唯一解。 3符号说明 表示空单元格候选数 表示候选数数的加权函数 表示数独空单元格中的候选数数目函数 表示该数独的空格处 表示该数独难度的函数 表示数k是否填入数独方中的（i，j）处 表示往空格处填入0后数独方中（i，j）处的数 表示经过求解后数独方中（i，j）处的数 4模型的建立与求解 4.1 问题1 4.1 通过对数独的分析与研究，数独难度与数独候选数、逻辑推理方法、有哪些信誉好的足球投注网站步数、空格数以及空格的分布情况都有密切的关系。通过大量的计算观察发现，用到的逻辑与推理方法越复杂，那么在数独中出现的候选数越多;反之，在数独题中出现的候选数越多，解决数独题所用到的逻辑推理方法一般也越难。解答一个数独所用到的有哪些信誉好的足球投注网站步数越多，数独中的候选数越多。反之，一般情况下也成立。另外数独中的空格数以及空格的分布情况与候选数也有同样类似的关系。综合这几个影响数独难度的几种因素，分析候选数和空格数为主要影响因素，再根据其构造加权规范函数，计算数值来衡量数独难度。 4.1.2 函数的建立 加权规范函数建立在候选数列表的基础上。根据候选数列表，计算出每一个空单元格中的候选数数目，将候选数数目与其相对应的加权函数结合起来，计算加权规范函数。 定义单元格中的候选数数目函数为，这个函数仅适用 于数独P中的空单元格，而数独中的空单元格可以表示为 (1) 有个候选数的候选数数目函数 (2) 我们赋予它相应的加权函数，从而得到加权函数 (3) 不能准确的反映数独难度，受数独中空单元格数目影响很大，呈正向关系，如在数独中删除单元格，数独空单元格数增加，导致增加，即空格数越多，越大，然而这并不符合所有的数独。为了排除这一影响，将加权函数规范，得到加权规范函数： (4) 根据以上的分析，对于某单元格，其候选数数越大，其对应的加权函数也应越大。我们采用指数函数”计算数独的，其中为某空单元格的候选数数目。计算发现，与数独难度是正相关的，即越大，数独的难度越大。 4.1.3 函数的求解 根据题中给出的数独，按照数独游戏应该满足的条件，可以得到该数独的空格处的候选数列表，如下表2所示： 表2 空格处候选数列表 8 1246 24569 2347 123