TI图形计算器编程实现数独初盘矩阵的高效生成

admin管理员组

文章数量:1530883

2024年3月30日发(作者：)

2021年第5期

中学数学教学参考（下旬）

TI

图形计算器编程

实现数独初盘矩阵的高效生成

王佳淇（北京市第一〇一中学高二15班）

摘要：在给定一个初始合法数独矩阵的基础上，利用随机数，对初始矩阵进行数字交换、宫内行列交换、

宫间的行列交换，并且根据所提示的数字个数，随机确定位置，产生一个合法的数独矩阵初盘，并在

TI

图

形计算器上进行编程实现。

关键词：数独；随机数；编程；

TI

图形计算器

文章编号：1002-2171(2021)5-0035-04

1提出问题

换，形成结果数独八，再从结果数独中每行、每列去掉

一些数字，形成数独初盘B，这个算法的时间复杂度是

数独盘面是一个9X9的矩阵，按照3行3列进

〇(«)，相比于回溯法，这种算法将是非常高效的。

行分块成9个3X3的小矩阵，称为9个九宫，所以

又称“九宫格”。一个合法数独的要求是用1〜9的

2数独矩阵交换方法

数字填充矩阵，使得数字1〜9在每一行、每一列和

通过如下几步交换，从种子数独A生成数独A,。

每一宫中都只出现一次。给一定提示数的盘面作为

2.1第一步：矩阵中两个数字交换

初始条件，称为初盘。玩家根据提示数和规则，用

数独的难点在于把1个数字变了之后，相应的会

1〜9的数字填满其他空格，得到数独的解，这个盘面

有一连串的数字需要改变。对于确定的种子数独，如

称为终盘。2005 年 Bertram Felgenhauer 和 Frazer

图1所示。假设把第一行第一列的数字由1变成2,

Jarvis 计算出存在 9! X 722 X 27 X 27 704 267 971 =

相应的第一行第二列和第一列第四行的2需要变成

6 670 903 752 021 072 936 960(约有 6. 67 X 1021)种

1，这个2相应的行和列上的1需要变成2,这个1相

组合，如果将重复（如数字交换、对称等）的数去掉，那

应的行和列上的2需要变成1，……一系列交换之后，

么有5 472 730 538个组合。基于这个数量级，如果

只是相当于把矩阵上所有的2变成了 1，所有的1变

考虑生成所有数独，并存储起来肯定是不能现实的。

成了 2,这样新的矩阵中的每行、每列、每宫就有且只

目前主要的数独初盘生成算法是回溯法。实现思路

有一个1〜9的数字，即得到的仍是一个合法的数独

是先在第一行生成一组1〜9不重复的数字，然后第

矩阵，如图2所示。

二行开始不停地验证，不停地回退，直到生成一个可

•1

2

34

56789"

■2134567

89'

4567

89

1

2

3

4567

89

2

13

以解的数独初盘:1]。通过对这些算法的分析，理论上

789

1

2

34

56

7

892

13456

可以生成任意一种初盘，但是它的执行效率却非常

2

345678

9

1

134

5678

92

56

789

1

2

345

6789

2

低，算法的时间复杂度为〇 (2")，〃为数独初盘中数

13

4

89

1234

567

892

13

4

56

7

字的个数。能否寻找一种效率更高的数独初盘算法

34

5678

9

1

2

3

45678

9

2

1

678

9

1

2

34

5

6789

2

1345

呢？我们提出如下解决思路：先写一个合法数独，称

9

1

2

345

67

8.•9

2

1345678_

之为“种子数独”，用A表示，然后对这个数独进行变

图1 图2

*本文系北京市海淀区“十三•五”重点课题“图形计算器情景下数学核心素养培养的研究”阶段性成果，课题编号:

HDGH20190088。

2021年第5期

中学数学教学参考（下旬>

hucan com

如果我们先把1变成2,再把相应的2变成其他

数字，比如变成3,则该行会出现多于一个3存在的问

题.即交换结果为一个非法的数独矩阵。为了矩阵合

法，我们只对两个数字进行交换，把所有的x变成y，

所有的7变成1。x和y可以是1〜9中的任意数字，

经过多次交换后，矩阵与原矩阵的差异已经非常大。

比如，我们随机生成10对随机数（7, 2)、（2, 5)、（8,

6)、（9 ，6)、（ 4 ，7)、（2, 9)、（6, 8)、（ 5, 9)、（1， 2)、

(8，4)，并依次对这些数字对进行交换，经过10次交换

后的数独矩阵如图3所示，与图1比较已经面目全非。

转换之后的数独，虽然看上去与种子数独矩阵差

别很大，但是不难发现，其中存在一个问题，即如果原

始数独对应矩阵A的元素与a,2,_2相同，则最后生

成的矩阵B的元素6%与6,2,2相同，如图1，原始矩阵

中an，a31相同，图3中交换后的矩阵，634仍然相同，

这意味着矩阵的结构没有改变，也就是说，1在矩阵中的

位置无论换成什么数，它都占用相同的相对位置。下面

我们想改变矩阵的结构.继续对矩阵S进行交换。

2 8 3 7 5 6 9 14'

756914283

914283756

837569142

569142837

142837569

375691428

691428375

4 2837569 1.

图

2

7

9

8

5

1

3

6

4

837

569

1

42

3

7

5

69

1

4

28

75

6

9

1

4

283

56

1

4

83

6

9

42

3

7

9

1

28

75

9

1

4

287

75

6

1

42

1行5行、

837

569

交换

4

2

8

375

6

9

1

图

5

7

9

8

2

⑥

9

1

3

6

4

5

©

1

4

3

7

8

3

4

2

75

9

1

2

8

4

2.3 第

弟

三

二

步

步

：

：

宫间行或列交换

宫间？丁或列交换

为了保证宫的位置交换后行和列仍然有合法性，

所以要将每个行或列上宫做整体的交换，称之为宫间

行列交换，即将数独矩阵的前三行和中间三行交换，

前三行和最后三行交换，中间三行和最后三行交换，

三列交换亦是如此。如图5所示，第1〜3行与第7〜

9行进行交换，即1，7行交换，2,8行交换，3,9行交

换.结果为合法数独矩阵。

2

7

9

8

5

1

3

6

4

8

5

1

3

6

4

7

9

2

3

6

4

7

9

2

5

1

8

7

9

2

5

1

8

6

4

3

5

1

8

6

4

3

9

2

7

6

4

3

9

2

7

1

8

5

9

2

7

1

8

5

4

3

6

1

8

5

4

3

6

2

7

9

4

7

6

前

3

行

2

后

3

行

7

1 一〉

9

交换

8

5

1

3

6

4

8

5

1

2

7

9

7

9

2

3

6

4

8

5

1

5

1

8

7

9

2

3

6

4

6

4

3

5

1

8

7

9

2

9

2

7

6

4

3

5

1

8

1

8

5

9

2

7

6

4

3

4

3

6

1

8

5

9

2

7

2

7

9

4

3

6

1

8

5

8

5

1

2

7

9

4

3

6

图5

3数独矩阵“相关性”的刻画

3

2.2第二步：宫内两行或两列交换

在交换行和列时需注意，交换不能打破矩阵的合

法性。交换行不会打破列的合法性，但可能会打破宫

的合法性。交换列不会打破行的合法性，但也可能打

破宫的合法性。为了避免这个问题，我们交换行时,

保证在宫内进行，称之为宫内行列交换，即第一行只

能与第二、三行交换，第六列只能与第四、五列交换。

其他行、列也一样。如果第一行与第五行交换，则如

图4所示的矩阵不合法。宫内的行或列的交换保证

了每个宫的合法性，为了实现每个宫的位置变化.继

续对矩阵B进行宫间行列交换。

表1对结果进行的随机模拟

经过前面三步的交换，结果矩阵与原始种子矩阵

有相当大的区别了。为了选择更好的结果，我们引人

两个数独矩阵的相关性概念，将两个矩阵的9行依次

展开成一个行向量，每个向量包含81个元素，计算两

个向量夹角的余弦值，作为刻画两个矩阵相似性的指

标（简称余弦相似性指标），指标接近1，两个向量的

方向越接近，指标越接近〇,说明两个向量的方向越

趋向垂直。为了确定指标的取值范围，对结果进行随

机模拟，将种子数独矩阵经过20次数字交换、9次宫

内行交换、9次宫内列交换、2次宫间行交换、2次宫

间列交换的矩阵与原种子矩阵计算余弦相似性指标，

共计算10 000次，计算结果如表1第一行所示。同

时.我们对随机生成的两个数独矩阵，采用相同的方法

计算相关性，同样统计1〇 〇〇〇次，结果如表1第二行。

丨

实验次数

最大值

最小值

期望值

/i

标准差(7

(/i

一

(0.762,0. 818)概率

69. 6%

68. 1%

_

2〇

fi

~~ 2

a

)

(0.734,0.856)概率

95. 5%

95. 5%

(//_3

cr

，" + 3(7)

(0.706,0. 874)概率

99. 5%

99.

6°/〇

1

2

10 000

10 000

0. 905

0. 895

0. 656

0. 664

0. 790

0. 791

0.028

0. 029

聲法新探飞

1

2021年第5期

中学数学教学参考（下旬）

Xy

从模拟结果看，余弦相似性指标大致在0. 65〜0. 91

之间，平均值/约为〇. 79左右，标准差约为0. 029,

2

3

154

9

8768376

9

4251

9

548

673216491257

3

8

将余弦相似性指标以〇• 007的组距分成34组，作出

78631

2

5

94154256317

频率分布直方图如图6所示，以期望值为0. 790,标准

1

2

5

9

8476

37

1

3

948

5

62

4987362

157

1

3

948

5

62

差为0.028,绘制正态分布曲线，如图6中的灰色曲线

67

3

2

5

1

9

4826573

1

48

9

所示。模拟数据符合期望值为〇. 790,标准差为

5

1

94

786325

96

31

2

874

847

6

23

15

9

3

2148

76

9

5

0.028的正态分布的假定。将余弦相似性指标绘制正

3

62

1

9

5

48

7.

4

785

6

9

1

2

3.

态概率图，如图7所示，我们发现除了两边少数几点

图8

值以外，其他值基本在一条直线上，也说明正态分布

左侧终盘矩阵与初盘矩阵的第一个宫，都是由数字

比较适合。由于余弦指标反映的是两个向量方向的

1，2,3组成，第二宫有4,5两个数字相同，第三宫有

夹角，越接近1方向越一致。如图8所示，左、右两个

数独矩

7,8两个相同数字，而右侧终盘矩阵与初盘矩阵的第

一个宫，只有一个相同数字3,第二宫有4,6两个数字

相同，第三宫没有相同数字，这说明余弦相似性指标

确实能够反映矩阵的相似性，数值越小则表示数独矩

阵与种子矩阵间差异越大，因此在确定终盘数独矩阵

时，如果选择这个指标低于〇. 818(^+<

t

)，则终盘矩阵

图6 图7

与种子数独矩阵具有更大的差异性。

阵与种子矩阵余弦相似性分别为〇. 905和0. 656,可

4在

TI

图形计算器上编程实现

以直观地看出，左侧数独矩阵与种子矩阵（图1)同位

置有11个相同数字，而右侧矩阵与种子矩阵只有5

为了实现上述过程，共编写了 14个函数或者过

个数字相同，同时我们来看宫的情况，以第一行为例，

程，见表2。

表2函数或过程

函数或者程序名

功能或作用

initseedC

)

初始化种子矩阵函数，完成对种子数独矩阵的初始化

InitsudoC

)

初始化主数独矩阵函数，完成对主数独矩阵的初始化

swapvaKa

，6)

数字交换函数，将数独矩阵中数字

a

和6进行交换，即将数字

a

的位置换成同时将数字6的

位置换成

a

swaprow

(

a

，6)宫内行交换函数，将数独矩阵中第

a

行和第6行进行交换，调用时保证

a

，6在一个宫格内

swapcolumn(a

,6)宫内列交换函数，将数独矩阵中第

a

列和第6列进行交换，调用时保证在一个宫格内

swap

3

row

(

a

，6)

宫间行交换函数，将数独矩阵中第

a

个三行和第6个三行进行交换，如

U

=

l

，6=2,为将第1,4

行交换，2,5行交换，3,6行交换

swap

3

column(a

,6)

宫间列交换函数，将数独矩阵中第

a

个三列和第6个三列进行交换，如

a

=

l

，6=2,为将第1，4

列交换，2,5列交换，3,6列交换

initshowflag

(

w

)

初始化显示矩阵函数，将显示矩阵在随机〃个位置存储1，其他为〇,用以决定初盘显示数独矩

阵中哪些位置

createsudoku

(

cl

，

c

2，

c

3)

数独生成函数，调用上面的子函数，将种子数独矩阵，经过

cl

次随机数字交换，次随机宫内

行、列交换，

c

3次随机宫间行、列交换，生成终盘数独矩阵

check

()

数独矩阵检查函数，检查生成的数独矩阵与种子数独矩阵余弦相似性是否小于/•<+〇

showsudokuC

)

初盘矩阵显示函数，将初盘矩阵显示出来，用于人机交互

showalK

)

终盘矩阵显示函数，将终盘矩阵显示出来，用于人机交互

数独生成主函数，调用

createsudoku

(

cl

，

c

2，

c

3),根据经验，传人参数（'1 = 20，（2 = 9，（3 = 2，生

create

(

w

)

成数独终盘矩阵，待用

check

函数，检査相似度是否满足要求，不满足要求则重新生成，如果满

足要求则生成有》个数字1的显示矩阵，最后根据显示矩阵和终盘数独矩阵，生成初盘矩阵

all

(

n

)

生成数独矩阵，并将数独初盘和数独终盘一并显示出来

2021年第5期

中学数学教学参考(下旬)

等法新^]

操作时运行create(w)会生成一个数独初盘，并

显示出来，〃为数独初盘的数字个数。

运行create(w)时，首先调用swapvaK )函数将

种子数独矩阵进行数字交换，然后调用swaprow(

和swapcolumn(

swap3row (

)

会很大，但是在生成数独后发现这些矩阵非常相似，

如图1和图2所示。所以，增加了宫内行列交换和宫

间行列交换来进行进一步交换矩阵。

通过TI图形计算器编程实现了数独初盘的算

法，并对初盘进行解数独操作，发现数独初盘的难度

并不与初盘数字个数完全对应，所以初盘难度应该还

有其他参数。如与每个行或列中显示的数字及其位

置有关，不同的位置会导致解数独时判断树的分支个

数不一致[2]，这个问题留待后续分析研究。

在编写初盘程序的同时，编写一个解数独的程

序，将初盘算法的结果输人并求解，会有多个解。后

续可以考虑将解数独程序加人进去作为检测代码，如

果检测初盘结果存在多个解的情况，则需要增加bool

数组true值个数，直到只有一个解为止。

参考文献：

)函数进行宫内行列变换，再调用

3

6

0

2

1

8

7

9

0

0

8

2

0

0

9

4

0

0

7

9

0

0

0

0

0

0

8

0

0

6

0

2

0

5

0

9

0

0

8

9

5

0

0

0

3

5

7

9

3

0

0

0

2

0

0

4

0

0

0

0

9

0

0

8

2

0

7

9

5

3

6

0

0

0

0

0

3

6

1

8

0

)和 swap3-

columnC )函数进行宫间

行和列变换，生成终盘数独

矩阵，最后根据initshow-

flag ()需要显示的bool

矩阵内容显示初盘矩阵。

这样运行下来，可以很快生

成一个数独初盘，如图9所示。

5反思

经过这次编程经历，笔者不但对图形计算器编程

[1] 赵志芳，郭静鑫.杨璐.生成

Sudoku

的算法探究[

J

].

和数独本身理解更加深入，更重要的是发现了一些问

题，需要在后续的过程中逐渐修正，如笔者开始以为

经过对种子矩阵进行简单的数字交换后的矩阵差异

内江科技

，

2008(7): 22-23.

[2] 王琼，邹晟.数独问题的求解、评价与生成算法的研究

[

J

].南京师范大学学报，2010，10(1):76-79.

(上接第34页）

例如，概率是高中数学的重要概念，与人们的生

产生活有着密切的联系。课堂上教师可为学生创设

转转盘贏礼品活动的情境。这一情境对学生而言并

不陌生，因为一些商场为促销产品，常常通过鼓励消

费者转动大转盘贏礼品活动，达到宣传与促销产品的

目的。课堂上要求学生认真分析为什么消费者获得

大奖的可能性较小，而获得小奖的可能性较大，并认

真倾听学生的回答，而后肯定学生积极思考的行为，

自然地引出对概率概念的讲解。借助生活情境导入

数学概念，能进一步增加数学课堂的趣味性，使学生

对相关的数学概念留下更为深刻的印象。

解的数学概念，在课下录制并制作相关的微课视频；

另一方面.教学中要求学生通过观看微课视频进行

概念的学习，再鼓励他们积极讨论，真正做到吃透与

理解概念。

例如，集合是高中数学最先学习的概念。在进行

这一概念的教学时，教师可在课堂上为学生播放录制

好的微课视频，学生观看微课视频，并叙述集合的概

念，分析集合的特点，使其在以后解答相关问题时，保

证解题的正确性。借助微课导人数学概念，学生在课

堂上的学习热情非常高，取得了事半功倍的教学

效果。

5总结

高中数学概念引人方式多种多样，教学中为获得

4借助微课视频引人概念

高中生对信息技术教学很感兴趣，而微课正是

良好的引人效果，教师既要敢于探索、实践相关的引

入途径，又要做好引人效果的总结与分析，注重相关

引人环节的优化，不断提高数学概念的教学质量与教

学水平。

基于信息技术发展起来的，能较好地激发学生的学

习兴趣，因此导人高中数学概念时应注重对微课的

应用。一方面，认真收集相关的微课素材，围绕要讲

本文标签： 矩阵交换数字进行概念