Sudoku-Python作品

1 前言微叙

本附属文档及Python作品,演示视频作者:张宁

就读学校:泌阳县第一高级中学

本作品灵感来源:Leetcode

关于此程序:本程序杂糅了作者在见到本题目开始至本程序截稿期间,个人想法,本校科技社成员间的交流,以及部分博文所体现出来的试错递归思想,数独矩阵技巧,下标数学问题。在经过多次测试后实现了本程序基础算法的完整性,可行性,快捷性,由于本程序主要集中于集合算法递归函数学习。所以对于可视化,观赏性,本作品没有足够的精力来优化,但本程序体现了数学思想和Python的不可分割,以及数学思维,编程思维之间的相辅相成,希望评委能够给予支持,感谢。

2 程序简介

2.1 数独简介

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。

注:本段来源于百度百科

3 实现思路

3.1 转换矩阵

3.1.1 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
m = [

[6, 0, 0, 1, 0, 0, 7, 0, 8],

[0, 0, 0, 8, 0, 0, 2, 0, 0],

[2, 3, 8, 0, 5, 0, 1, 0, 0],

[0, 0, 0, 0, 4, 0, 0, 9, 2],

[0, 0, 4, 3, 0, 8, 6, 0, 0],

[3, 7, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 3, 0, 7, 0, 5, 2, 6],

[0, 0, 2, 0, 0, 4, 0, 0, 0],

[9, 0, 7, 0, 0, 6, 0, 0, 4]

]

本段代码无任何技术难题,不再赘述。

3.2 探寻首格

3.2.1 码前思路

借助于本文档【1.1】中对数独的解释,可以得出解数独的第一步是寻找第一个空白格。对于人类而言,在短时间内的大量试错是极其浪费时间的,但对于具有极强计算能力的计算机来说,试错是比人类技巧更简单的一种方法

3.2.2 代码实现

1
2
3
4
5
6
7
8
9
10
11
def start_0(m:"矩阵"):#寻找第一个0

for x in range(9):

for y in range(9):

if m[x][y] == 0:

return x, y

return -1,-1

在本程序的前部分,已经将数独转化为Python矩阵,并且将未填入的数字用0来代替。在本段代码中,通过使用两个for循环来确定0格的位置。倘若无0点,则证明本数独已然完成。

3.3 探寻下格

3.3.1 码前思路

如果将当前格填入之后,下一步的工作便是填入下一个空白格,但是在码前应当思考,下一格的坐标如何确定,如果单纯的以x+1便会致使程序只在第一行进行(若第一个空格在第一行的条件下),所以这里要考虑空格的换行问题

3.3.2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def seenext(m:"矩阵", x:"行", y:"列"):

for next_y in range(y+1, 9):

if m[x][next_y] == 0:

return x, next_y

for next_x in range(x+1, 9):

for next_y in range(0, 9):

if m[next_x][next_y] == 0:

return next_x, next_y

return -1, -1

本段代码在探寻下一行时使用了两个for 循环,第一个循环计算了在本行的条件下,通过用累加y值进行判断是否为0。第二个计算了下一列中的空格。其余不再赘述。

3.4 剔除筛选[重要]

3.4.1 码前思路

将 1~9 这个数字集合中,与行的数字集合、列的数字集合以及九宫格的数字集合重叠的部分去除。剩余的就是符合条件的集合。

3.4.2 代码实现

1
2
3
4
5
6
7
8
9
def value(m:"矩阵", x:"行", y:"列"):

i, j = x//3, y//3

g = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]

v = set([x for x in range(1,10)]) - set(g) - set(m[x]) - set(list(zip(*m))[y])

return list(v)

line2中的整除是为了得出在哪一宫,line3中的[i3+r][j3+c]是根据I,j(m[i3][j3]是本宫的起始位点)。并将横纵坐标用for循环累加。

Line4利用set,zip来确定具体的集合。

3.5 递归试错

3.5.1 码前思路

以首空格为基本,尝试下一个空格,若下一个空格的集合为空,则解数独失败,将此格填为0,再次试错。

3.5.2 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def trysudoku(m:"矩阵", x:"行", y:"列"):

for v in value(m, x, y):

m[x][y] = v

next_x, next_y = seenext(m, x, y)

if next_y == -1: #无

return True

else:

end = trysudoku(m, next_x, next_y) #递归

if end == True:

return True

m[x][y] = 0

在本段代码中,通过对上一步获得的集合进行填数,从value中填入数字,倘若无空格,则返回True,如果在seenext中未探寻到空格,那么便会得到next_y=-1,故无下一个空白格。如果有下一个空白格,则进行下一个空白格的试错,直至end=True。本数独完成。

3.6 代码整合

3.6.1 代码实现

1
2
3
4
5
6
7
def sudoku(m):

x, y = start_0(m)

trysudoku(m, x, y)

print(m)

由于本段代码无任何技术性难题,不进行【码前思路】部分。

4 视频演示

1074_0b2eryahtmimzmaeuoaxkrsd5dqepf2azmsa.f0.mp4