文档介绍：word
word
1 / 17
word
数独问题
摘要
本文是对数独问题进展求解。结合数独生成的特点，立足于题中数独建模和求解的要求，建立了数独难度分析函数和整数规划模型。
对于问题一，首先研究数独难度的影响因素，通过综合分析数独的特点结构，得出可以在常数时间计算出来以衡量数独的难易程度。通过计算可知，根据数独难度的划分得到如下结论： 数独难度系数为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
关键词：数独 数独难度分析 穷举法 回溯法 整体规划
word
word
2 / 17
word
1问题的重述
前段时间芬兰一位数学家号称设计出全球最难的“数独游戏〞，并刊登在报纸上，让大家去挑战。该数独如如下图所示：
数独是根据9×9盘面上的数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫的数字均含1-9，且不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为根底，任何无解或多解的题目都是不合格的。
根据以上描述，试完成以下问题：
1. 分析此数独的难度；
2. 用穷举算法求解数独；
3. 设计此数独求解的较优的算法；
4. 建立数独求解模型并给出此数独的答案。
2模型的根本假设
1该数独问题存在唯一解。
3符号说明
表示空单元格候选数
表示候选数数的加权函数
表示数独空单元格中的候选数数目函数
表示该数独的空格处
表示该数独难度的函数
表示数k是否填入数独方中的〔i，j〕处
表示往空格处填入0后数独方中〔i，j〕处的数
表示经过求解后数独方中〔i，j〕处的数
word
word
3 / 17
word
4模型的建立与求解
问题1
通过对数独的分析与研究，数独难度与数独候选数、逻辑推理方法、搜索步数、空格数以与空格的分布情况都有密切的关系。通过大量的计算观察发现，用到的逻辑与推理方法越复杂，那么在数独中出现的候选数越多;反之，在数独题中出现的候选数越多，解决数独题所用到的逻辑推理方法一般也越难。解答一个数独所用到的搜索步数越多，数独中的候选数越多。反之，一般情况下也成立。另外数独中的空格数以与空格的分布情况与候选数也有同样类似的关系。综合这几个影响数独难度的几种因素，分析候选数和空格数为主要影响因素，再根据其构造加权规函数，计算数值来衡量数独难度。
加权规函数建立在候选数列表的根底上。根据候选数列表，计算出每一个空单元格中的候选数数目，将候选数数目与其相对应的加权函数结合起来，计算加权规函数。
定义单元格中的候选数数目函数为，这个函数仅适用
于数独P中的空单元格，而数独中的空单元格可以表示为
(1)
有个候选数的候选数数目函数
(2)
我们赋予它相应的加权函数，从而得到加权函数
(3)
不能准确的反映数独难度，受数独中空单元格数目影响很大，呈正向关系，如在数独中删除单元格，数独空单元格数增加，导致增加，即空格数越多，越大，然而这并不符合所有的数独。为了排除这一影响，将加权函数规，得到加权规函数：
word
word
4 / 17
word
(4)
根据以上