数独中的数学模型

数独中的数学模型

摘要

现如今数独游戏风靡全球，深受人们喜爱。其难度等级多样，求解数独难度

等级较高的常常需要花费大量的时间和精力，因此我们试图用计算机来解决这一

问题。

在问题一中，我们主要考虑空格数的多少以及空格自由度与数独难度等级的

关系。由一定的案例分析得出数独题目的难度等级与空格数存在正比关系，接着

我们考虑如果只是简单的按照空格的数目多少来划分数独题目的难易程度是不

全面的，因此继续分析，得出空格自由度与数独的难度等级存在正比的关系，最

后又以空格数和空格自由度综合分析进行验证，得出此数独等级为3级。[1] 空格自由度法模型如下：

在问题二中，我们运用穷举法分析大量可能情况，再用MATLAB编写程序得

出此数独游戏的终盘。

在问题三中，我们运用了比较排除法、唯一解法和综合法来求解此数独游戏，最终选用综合法作为较优方法。[1]

在问题四中，我们用循环回溯法进行求解，使用MATLAB编写程序得出结果（见表8）。[1]

关键字：穷举法比较排除法唯一解法循环回溯法数独空格数空格自由度

一、问题背景

数独是一种数字解谜游戏，英文名叫Sudoku，前身为“九宫格”，当时

的算法比现在的更为复杂，要求纵向、横向、斜向上的三数之和等于15，

而不只是数字的不能重复，儒家典籍《易经》中的“九宫图”也是来源于此。关于它的起源一直存有争议，有人认为最早起源于中国，也有人认为起

源于瑞士。1970年由美国一家数学逻辑游戏杂志首先发表，名为Number。后在

日本流行，于1984年把Sudoku取名为数独。数独全面考验做题者观察能力和逻

辑推理能力，它的玩法逻辑简单，除了1到9的阿拉伯数字以外，不必用到

任何东西，但数字的排列方式却又千变万化，不少教育者认为，数独是锻炼大

脑的绝佳方式。它不仅具有很强的趣味性，也是一种对智慧和毅力的考验。

二、问题重述

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，

让大家去挑战。这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这

个“数独之谜”。

所给数独游戏表格如下：

据介绍，目前，数独游戏难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所有数

独游戏中，难度最高的等级。

数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足

每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。每一道合格的数

独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

由此我们要解决以下问题：

问题一：分析此数独的难度；

问题二：用穷举算法求解数独；

问题三：设计此数独求解的较优的算法；

问题四：建立数独求解模型并给出此数独的答案。

三、问题分析

根据题中所给信息我们知道数独是一种数字解谜游戏，要求游戏者有很好的观察能力和逻辑推理能力。

针对问题一：

分析此数独难度，我们认为有两点因素：一、空格数的多少，二、空间自由度。因此我们采取例证法进行分析，根据空格数来划分等级，进行一定的数据分析求出空格率，进而得出难度系数与空格数的关系。数独的难度等级与行、列、宫格内的空格数存在着密切联系，所以数独难易程度还与空间自由度有关。数独的空格自由度，指除掉空格本身，空格所在行、列、九宫内的空格数总和。除此之外我们可以以玩家完成数独题目的时间来判定数独题目的难度。

针对问题二：

“穷举法”是指当一个问题有几种可能而一时难以判定时,把几种可能一一列举出来,然后逐一尝试，直到尝试结果与给定的条件和结论相符为止。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确，所以我们就以此来分析所有可能情况得出最终结果。

针对问题三：

为了找出更好的数独解法，我们运用了三种方法来求解。分别是：比较排除法、唯一解法和综合法。分析比较，选出较优方案。

针对问题四：

我们选用循环回溯法进行分析求解，与问题三中所求结果对比，以此验证其准确性。

四、模型假设

1、假设每种数独游戏都存在一定的联系且相互之间的难易程度成一定的比例；

2、假设实验者水平相同，随着实验不断进行，完成数独题目熟练程度不会增加；

3、假设实验者数独时间与数独题目难度无关。

五、符号说明

六、模型建立与求解

6．1问题一的求解

为了更好的区分难易程度我们将数独以空格数划分为五个等级，具体划分如下：

空格数的取值范围为0-81，以空格数来平均划分难度等级，将空格数平均分成5个类型，空格数的取值范围缩小到37-81。

划分等级如下表所示：

100道，表格行表示空格的个数，列表示难度的级别，一星为最容易，二星为容易，三星为难，四星为最难。例如：表一的首格3表示，难度为一星，空格数为50的题目有3道。

也相应的增加。为进一步探讨数独的难易程度是否还与其他因素有关，我们对数独题目的统计表格进行处理，在同等难度上，将每种空格的题目个数除以该难度的总题目数，得到如下表格。

表2 计算《数独》空格率与难度

表格的数据用图表表示（图1），由图可以清晰看出，难度等级递增，空格

数也不断增加。难度等级与空格数存在正比的关系。

图1 《数独》空格数与难度

经过我们的多次试验与分析，我们初步得到，随着空格数的增加，数独的难度系数也相应的增加，当然数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体趋势递增，不同难度等级的题目空格数也一样的情况。6.1.2空格自由度与难度等级

数独题目的难度等级与空格数存在正比关系。难度等级的增加，空格数总体