当前位置:首页 » 《资源分享》 » 正文

Python 控制台操作的文字版“数独”游戏(非GUI版本)_汉阳Hann's Home

21 人参与  2021年09月13日 10:23  分类 : 《资源分享》  评论

点击全文阅读


数独

数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵(Latin Square)。19世纪80年代,一位美国的退休建筑师格昂斯(Howard Garns)根据这种拉丁方阵发明了一种填数趣味游戏,这就是数独的雏形。20世纪70年代,人们在美国纽约的一本益智杂志《Math Puzzles and Logic Problems》上发现了这个游戏,当时被称为填数字(Number Place),这也是公认的数独最早的见报版本。——摘自百度百科

除了九宫格数独,还有许多各种变形数独(如下图),也有几个数独复合在一起的联合数独等等。

python实现数独游戏

本篇以九宫格数独为例,自定义了两个类 Matrix() 和 Sudo(),源代码见本篇末尾。

用法:Sudo(level)
参数:level = 1 ~ 7 ,分别初始化10~70个待填空格,默认值为4。

>>> sudoku = Sudo()

>>> #题目矩阵的数组
>>> sudoku.matrix
[[9, 7, 0, 6, 0, 4, 0, 0, 0],
 [0, 0, 3, 5, 7, 0, 4, 6, 9],
 [0, 0, 0, 2, 0, 9, 0, 7, 0],
 [3, 4, 0, 8, 0, 6, 0, 1, 2],
 [0, 2, 0, 0, 9, 7, 0, 5, 0],
 [0, 6, 0, 0, 0, 0, 7, 0, 4],
 [8, 0, 0, 0, 6, 2, 1, 3, 0],
 [7, 5, 0, 9, 0, 3, 2, 4, 6],
 [6, 0, 2, 0, 4, 0, 0, 0, 0]]

>>> #题目答案的元组
>>> sudoku.matrix.data
((9, 7, 5, 6, 1, 4, 3, 2, 8),
 (2, 1, 3, 5, 7, 8, 4, 6, 9),
 (4, 8, 6, 2, 3, 9, 5, 7, 1),
 (3, 4, 7, 8, 5, 6, 9, 1, 2),
 (1, 2, 8, 4, 9, 7, 6, 5, 3),
 (5, 6, 9, 3, 2, 1, 7, 8, 4),
 (8, 9, 4, 7, 6, 2, 1, 3, 5),
 (7, 5, 1, 9, 8, 3, 2, 4, 6),
 (6, 3, 2, 1, 4, 5, 8, 9, 7))
>>> 

>>> #矩阵中空格坐标的元组
>>> m.zero
[(0, 2), (0, 4), (0, 6), (0, 7), (0, 8), (1, 0), (1, 1), (1, 5), (2, 0), (2, 1),
 (2, 2), (2, 4), (2, 6), (2, 8), (3, 2), (3, 4), (3, 6), (4, 0), (4, 2), (4, 3),
 (4, 6), (4, 8), (5, 0), (5, 2), (5, 3), (5, 4), (5, 5), (5, 7), (6, 1), (6, 2),
 (6, 3), (6, 8), (7, 2), (7, 4), (8, 1), (8, 3), (8, 5), (8, 6), (8, 7), (8, 8)]
>>> 

游戏操作过程

>>> m = Sudo(1)
>>> m.Question   # 1~9 为已知数字, 0 表示待填的空格
6 0 3 | 8 7 5 | 0 2 1
7 2 5 | 1 3 9 | 0 6 8
1 0 8 | 2 4 0 | 5 7 3
------+-------+------
3 5 4 | 6 9 7 | 8 1 2
0 0 9 | 5 0 8 | 6 3 4
8 6 1 | 4 2 3 | 7 9 5
------+-------+------
9 8 7 | 3 5 0 | 1 4 6
4 3 6 | 9 8 1 | 2 5 7
5 1 2 | 7 0 4 | 3 8 9
>>> m.Try()  #返回待填空的坐标,左上第一格坐标为(1,1),最右下一格的坐标为(9,9)
[(1, 2), (1, 7), (2, 7), (3, 2), (3, 6), (5, 1), (5, 2), (5, 5), (7, 6), (9, 5)]
>>> m.Try(1,2) #返回某一格可填的数字
{9, 4}
>>> [m.Try(x,y) for x,y in m.Try()]  #返回所有空格
[{9, 4}, {9, 4}, {4}, {9}, {6}, {2}, {7}, {1}, {2}, {6}]
>>> m.Get(1,2)  #获取某坐标的答案
4
>>> m.pprint() #返回任意中间状态
6 4 3 | 8 7 5 | 0 2 1
7 2 5 | 1 3 9 | 0 6 8
1 0 8 | 2 4 0 | 5 7 3
------+-------+------
3 5 4 | 6 9 7 | 8 1 2
0 0 9 | 5 0 8 | 6 3 4
8 6 1 | 4 2 3 | 7 9 5
------+-------+------
9 8 7 | 3 5 0 | 1 4 6
4 3 6 | 9 8 1 | 2 5 7
5 1 2 | 7 0 4 | 3 8 9
>>> m.Fill(1,2,4)  #Fill(x,y,value) 在坐标(x,y)空格内填上数字value
>>> [m.Try(x,y) for x,y in m.Try()]
[{9}, {4}, {9}, {6}, {2}, {7}, {1}, {2}, {6}]
>>> m.Try()
[(1, 7), (2, 7), (3, 2), (3, 6), (5, 1), (5, 2), (5, 5), (7, 6), (9, 5)]
>>>
>>> m.Answer  #可以提前“偷看”答案
6 4 3 | 8 7 5 | 9 2 1
7 2 5 | 1 3 9 | 4 6 8
1 9 8 | 2 4 6 | 5 7 3
------+-------+------
3 5 4 | 6 9 7 | 8 1 2
2 7 9 | 5 1 8 | 6 3 4
8 6 1 | 4 2 3 | 7 9 5
------+-------+------
9 8 7 | 3 5 2 | 1 4 6
4 3 6 | 9 8 1 | 2 5 7
5 1 2 | 7 6 4 | 3 8 9
>>> 
>>> 
>>> m.valid  #检查所有空格是否填满并正确
False
>>> #以下代码填上全部空格,前提条件所有待填空格只有一种选择时才有效
>>> [m.Fill(x,y,z) for x,y,z in [list(x)+[*z] for x,z in list(zip(m.Try(),[m.Try(x,y) for x,y in m.Try()]))]]
>>>
>>> m.valid  #检查是否已填完,全部正确返回True
True
>>> m.Question
6 0 3 | 8 7 5 | 0 2 1
7 2 5 | 1 3 9 | 0 6 8
1 0 8 | 2 4 0 | 5 7 3
------+-------+------
3 5 4 | 6 9 7 | 8 1 2
0 0 9 | 5 0 8 | 6 3 4
8 6 1 | 4 2 3 | 7 9 5
------+-------+------
9 8 7 | 3 5 0 | 1 4 6
4 3 6 | 9 8 1 | 2 5 7
5 1 2 | 7 0 4 | 3 8 9
>>> 

一步完成答案

>>> sudoku = Sudo(6)
>>> sudoku.Question
0 0 0 | 0 0 0 | 0 0 0
0 0 0 | 0 0 3 | 0 7 0
8 1 0 | 4 0 9 | 0 0 2
------+-------+------
0 0 0 | 0 9 0 | 0 0 0
1 7 0 | 0 5 0 | 0 3 4
0 0 0 | 0 0 4 | 0 9 0
------+-------+------
0 0 0 | 8 0 0 | 1 4 0
0 3 0 | 0 0 0 | 0 0 0
0 0 0 | 5 0 0 | 0 0 9
>>> sudoku.valid
False
>>> sudoku.Solve()
True
>>> sudoku.valid
True
>>> sudoku.pprint()
2 4 3 | 1 7 5 | 9 6 8
9 5 6 | 2 8 3 | 4 7 1
8 1 7 | 4 6 9 | 3 5 2
------+-------+------
3 6 4 | 7 9 2 | 8 1 5
1 7 9 | 6 5 8 | 2 3 4
5 8 2 | 3 1 4 | 7 9 6
------+-------+------
7 9 5 | 8 2 6 | 1 4 3
6 3 8 | 9 4 1 | 5 2 7
4 2 1 | 5 3 7 | 6 8 9
>>> 

完成时间测试

>>> sudo1 = Sudo()
>>> sudo1.timeSolve()
0.007241964340209961
>>> sudo2 = Sudo(5)
>>> sudo2.timeSolve()
0.02873539924621582
>>> sudo3 = Sudo(6)
>>> sudo3.timeSolve()
0.20312190055847168
>>> sudo4 = Sudo(7)
>>> sudo4.timeSolve()
0.022271156311035156
>>> 

# 并非空格越多耗时越多;矩阵是随机产生的,个别的可能要10多秒才能出答案

矩阵变换

同一数独题目,通过矩阵变换可以变化出千千万万不同的排列来。同一组数字通过变换,粗略估算一下至少有6的9次方个变化,数量为1000万以上。

转置和反序等

>>> su = Sudo()
>>> su.pprint()
5 4 0 | 7 9 0 | 0 0 3
1 3 0 | 2 0 0 | 5 6 0
0 0 8 | 3 0 0 | 0 9 1
------+-------+------
3 0 4 | 0 8 0 | 9 1 2
2 0 0 | 0 1 9 | 0 3 0
0 9 1 | 4 0 2 | 0 8 5
------+-------+------
8 7 5 | 0 0 0 | 1 0 6
0 0 3 | 1 0 4 | 0 5 0
0 1 0 | 8 0 0 | 0 0 0
>>> su.mat.T.pprint()
5 1 0 | 3 2 0 | 8 0 0
4 3 0 | 0 0 9 | 7 0 1
0 0 8 | 4 0 1 | 5 3 0
------+-------+------
7 2 3 | 0 0 4 | 0 1 8
9 0 0 | 8 1 0 | 0 0 0
0 0 0 | 0 9 2 | 0 4 0
------+-------+------
0 5 0 | 9 0 0 | 1 0 0
0 6 9 | 1 3 8 | 0 5 0
3 0 1 | 2 0 5 | 6 0 0
>>> su.mat.T1.pprint()
3 0 0 | 0 9 7 | 0 4 5
0 6 5 | 0 0 2 | 0 3 1
1 9 0 | 0 0 3 | 8 0 0
------+-------+------
2 1 9 | 0 8 0 | 4 0 3
0 3 0 | 9 1 0 | 0 0 2
5 8 0 | 2 0 4 | 1 9 0
------+-------+------
6 0 1 | 0 0 0 | 5 7 8
0 5 0 | 4 0 1 | 3 0 0
0 0 0 | 0 0 8 | 0 1 0
>>> su.mat.T2.pprint()
0 1 0 | 8 0 0 | 0 0 0
0 0 3 | 1 0 4 | 0 5 0
8 7 5 | 0 0 0 | 1 0 6
------+-------+------
0 9 1 | 4 0 2 | 0 8 5
2 0 0 | 0 1 9 | 0 3 0
3 0 4 | 0 8 0 | 9 1 2
------+-------+------
0 0 8 | 3 0 0 | 0 9 1
1 3 0 | 2 0 0 | 5 6 0
5 4 0 | 7 9 0 | 0 0 3
>>> su.mat.T3.pprint()
0 0 0 | 0 0 8 | 0 1 0
0 5 0 | 4 0 1 | 3 0 0
6 0 1 | 0 0 0 | 5 7 8
------+-------+------
5 8 0 | 2 0 4 | 1 9 0
0 3 0 | 9 1 0 | 0 0 2
2 1 9 | 0 8 0 | 4 0 3
------+-------+------
1 9 0 | 0 0 3 | 8 0 0
0 6 5 | 0 0 2 | 0 3 1
3 0 0 | 0 9 7 | 0 4 5
>>> 

交换大行或大列

>>> su = Sudo()
>>> su.pprint()
0 0 0 | 0 7 2 | 5 3 8
5 8 0 | 0 3 0 | 0 0 0
0 3 7 | 0 8 0 | 0 0 1
------+-------+------
3 0 0 | 6 9 8 | 0 0 0
8 2 0 | 7 0 4 | 0 5 0
0 0 1 | 0 0 0 | 9 0 4
------+-------+------
9 6 0 | 8 4 0 | 0 2 5
0 5 8 | 0 2 1 | 0 0 6
0 1 4 | 3 0 5 | 8 0 7
>>> su.mat.R(1,2).pprint()
3 0 0 | 6 9 8 | 0 0 0
8 2 0 | 7 0 4 | 0 5 0
0 0 1 | 0 0 0 | 9 0 4
------+-------+------
0 0 0 | 0 7 2 | 5 3 8
5 8 0 | 0 3 0 | 0 0 0
0 3 7 | 0 8 0 | 0 0 1
------+-------+------
9 6 0 | 8 4 0 | 0 2 5
0 5 8 | 0 2 1 | 0 0 6
0 1 4 | 3 0 5 | 8 0 7
>>> su.mat.R(1,3).pprint()
9 6 0 | 8 4 0 | 0 2 5
0 5 8 | 0 2 1 | 0 0 6
0 1 4 | 3 0 5 | 8 0 7
------+-------+------
0 0 0 | 0 7 2 | 5 3 8
5 8 0 | 0 3 0 | 0 0 0
0 3 7 | 0 8 0 | 0 0 1
------+-------+------
3 0 0 | 6 9 8 | 0 0 0
8 2 0 | 7 0 4 | 0 5 0
0 0 1 | 0 0 0 | 9 0 4
>>> su.mat.R(2,3).pprint()
9 6 0 | 8 4 0 | 0 2 5
0 5 8 | 0 2 1 | 0 0 6
0 1 4 | 3 0 5 | 8 0 7
------+-------+------
3 0 0 | 6 9 8 | 0 0 0
8 2 0 | 7 0 4 | 0 5 0
0 0 1 | 0 0 0 | 9 0 4
------+-------+------
0 0 0 | 0 7 2 | 5 3 8
5 8 0 | 0 3 0 | 0 0 0
0 3 7 | 0 8 0 | 0 0 1
>>> su.mat.C(1,2).pprint()
8 4 0 | 9 6 0 | 0 2 5
0 2 1 | 0 5 8 | 0 0 6
3 0 5 | 0 1 4 | 8 0 7
------+-------+------
6 9 8 | 3 0 0 | 0 0 0
7 0 4 | 8 2 0 | 0 5 0
0 0 0 | 0 0 1 | 9 0 4
------+-------+------
0 7 2 | 0 0 0 | 5 3 8
0 3 0 | 5 8 0 | 0 0 0
0 8 0 | 0 3 7 | 0 0 1
>>> 

交换小行或小列

>>> su = Sudo()
>>> su.pprint()
2 4 0 | 5 0 0 | 9 6 3
3 0 0 | 0 0 6 | 4 0 7
0 7 6 | 0 4 9 | 0 0 0
------+-------+------
4 0 5 | 6 0 0 | 0 0 2
1 8 0 | 7 5 2 | 0 3 0
0 2 0 | 0 0 0 | 0 9 5
------+-------+------
0 5 4 | 8 0 3 | 1 2 0
0 0 0 | 9 0 0 | 0 0 8
8 0 3 | 2 6 4 | 0 0 9
>>> su.mat.Rn(2,1,3).pprint()
2 4 0 | 5 0 0 | 9 6 3
3 0 0 | 0 0 6 | 4 0 7
0 7 6 | 0 4 9 | 0 0 0
------+-------+------
0 2 0 | 0 0 0 | 0 9 5
1 8 0 | 7 5 2 | 0 3 0
4 0 5 | 6 0 0 | 0 0 2
------+-------+------
0 5 4 | 8 0 3 | 1 2 0
0 0 0 | 9 0 0 | 0 0 8
8 0 3 | 2 6 4 | 0 0 9
>>> su.mat.Cn(1,2,3).pprint()
2 0 4 | 5 0 0 | 9 6 3
3 0 0 | 0 0 6 | 4 0 7
0 6 7 | 0 4 9 | 0 0 0
------+-------+------
4 5 0 | 6 0 0 | 0 0 2
1 0 8 | 7 5 2 | 0 3 0
0 0 2 | 0 0 0 | 0 9 5
------+-------+------
0 4 5 | 8 0 3 | 1 2 0
0 0 0 | 9 0 0 | 0 0 8
8 3 0 | 2 6 4 | 0 0 9
>>> 

自定义数独题目

以矩阵样本matrixSample为列:

>>> matrixSample
[[8, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]]
>>> m = Sudo(0)
>>> m.Create(matrixSample)
Solving...
Soluted!
>>> m.Question
8 0 0 | 0 0 0 | 0 0 0
0 0 3 | 6 0 0 | 0 0 0
0 7 0 | 0 9 0 | 2 0 0
------+-------+------
0 5 0 | 0 0 7 | 0 0 0
0 0 0 | 0 4 5 | 7 0 0
0 0 0 | 1 0 0 | 0 3 0
------+-------+------
0 0 1 | 0 0 0 | 0 6 8
0 0 8 | 5 0 0 | 0 1 0
0 9 0 | 0 0 0 | 4 0 0
>>> m.Answer
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 8 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
>>> 

批量生成数独题目

Sudo.build(n, level)

n = 1~50 ; level = 1~7

矩阵数据保存在全局变量 Sudoku 

>>> Sudo.build(6,5)
No. 1:
8 0 0 | 0 7 0 | 0 0 0
0 0 0 | 1 0 0 | 0 0 0
0 3 0 | 0 0 9 | 0 0 2
------+-------+------
3 0 0 | 0 0 6 | 0 0 1
0 1 9 | 0 0 0 | 6 0 4
0 0 6 | 3 0 0 | 7 0 5
------+-------+------
5 7 8 | 9 3 0 | 0 0 0
9 6 3 | 8 0 4 | 0 0 7
0 0 0 | 5 0 7 | 0 0 9
No. 2:
0 2 3 | 0 5 0 | 1 6 0
0 0 0 | 0 0 0 | 0 7 9
0 1 8 | 0 0 7 | 0 0 0
------+-------+------
0 0 0 | 0 0 9 | 0 0 0
0 0 0 | 0 7 0 | 5 0 3
0 0 0 | 5 0 1 | 0 0 4
------+-------+------
8 0 6 | 7 4 3 | 0 0 0
4 0 1 | 0 0 5 | 0 3 0
0 3 2 | 0 0 6 | 0 4 7
No. 3:
5 2 9 | 0 6 0 | 0 7 3
0 4 8 | 2 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 8 0
------+-------+------
4 0 0 | 0 0 0 | 0 0 1
0 0 0 | 0 9 0 | 0 3 4
2 9 7 | 0 4 0 | 0 0 0
------+-------+------
0 5 0 | 0 0 0 | 2 1 0
0 6 0 | 0 1 0 | 0 4 7
0 0 0 | 3 2 6 | 5 9 0
No. 4:
2 0 4 | 0 0 0 | 1 0 0
0 3 0 | 0 0 0 | 0 0 0
6 8 0 | 3 4 0 | 0 7 0
------+-------+------
3 4 0 | 0 8 0 | 0 0 0
0 0 0 | 2 0 4 | 6 0 3
0 0 2 | 6 3 0 | 0 0 4
------+-------+------
4 6 0 | 8 7 0 | 2 1 0
8 0 0 | 9 0 2 | 0 0 6
0 0 3 | 0 0 0 | 0 0 0
No. 5:
8 5 0 | 6 0 3 | 0 0 0
0 0 6 | 0 0 9 | 0 5 8
9 0 0 | 0 5 8 | 6 0 0
------+-------+------
0 4 0 | 0 0 0 | 9 0 0
0 0 0 | 0 0 4 | 5 6 3
0 0 9 | 5 3 0 | 7 0 0
------+-------+------
6 3 8 | 0 4 0 | 0 0 0
0 0 0 | 0 1 0 | 0 3 0
0 0 0 | 0 6 0 | 8 9 0
No. 6:
9 4 1 | 0 0 8 | 3 5 7
0 0 7 | 0 0 0 | 0 6 9
0 0 0 | 0 0 0 | 0 0 1
------+-------+------
0 0 5 | 0 0 0 | 0 1 2
0 0 6 | 0 8 0 | 5 0 0
7 0 8 | 0 0 0 | 6 0 4
------+-------+------
6 7 0 | 8 0 0 | 0 0 0
2 0 4 | 0 0 0 | 0 0 6
0 0 0 | 7 0 6 | 9 0 8
>>> 
>>> Sudoku[0]
[[8, 0, 0, 0, 7, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 3, 0, 0, 0, 9, 0, 0, 2], [3, 0, 0, 0, 0, 6, 0, 0, 1],
 [0, 1, 9, 0, 0, 0, 6, 0, 4], [0, 0, 6, 3, 0, 0, 7, 0, 5],
 [5, 7, 8, 9, 3, 0, 0, 0, 0], [9, 6, 3, 8, 0, 4, 0, 0, 7],
 [0, 0, 0, 5, 0, 7, 0, 0, 9]]
>>> Sudoku[5]
[[9, 4, 1, 0, 0, 8, 3, 5, 7], [0, 0, 7, 0, 0, 0, 0, 6, 9],
 [0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 5, 0, 0, 0, 0, 1, 2],
 [0, 0, 6, 0, 8, 0, 5, 0, 0], [7, 0, 8, 0, 0, 0, 6, 0, 4],
 [6, 7, 0, 8, 0, 0, 0, 0, 0], [2, 0, 4, 0, 0, 0, 0, 0, 6],
 [0, 0, 0, 7, 0, 6, 9, 0, 8]]
>>> 
>>> Sudoku[2].pprint()
5 2 9 | 0 6 0 | 0 7 3
0 4 8 | 2 0 0 | 0 0 0
0 0 0 | 0 0 0 | 0 8 0
------+-------+------
4 0 0 | 0 0 0 | 0 0 1
0 0 0 | 0 9 0 | 0 3 4
2 9 7 | 0 4 0 | 0 0 0
------+-------+------
0 5 0 | 0 0 0 | 2 1 0
0 6 0 | 0 1 0 | 0 4 7
0 0 0 | 3 2 6 | 5 9 0
>>> 

实战“世界最难数独”

出自搜狗百科词条“世界最难数独”,感觉这个“最”有点水份;难度不是太大,程序用时2.91秒。

>>> m = Sudo()
>>> m.Create([
 [0,0,5,3,0,0,0,0,0],
 [8,0,0,0,0,0,0,2,0],
 [0,7,0,0,1,0,5,0,0],
 [4,0,0,0,0,5,3,0,0],
 [0,1,0,0,7,0,0,0,6],
 [0,0,3,2,0,0,0,8,0],
 [0,6,0,5,0,0,0,0,9],
 [0,0,4,0,0,0,0,3,0],
 [0,0,0,0,0,9,7,0,0]])
Solving...
Soluted!
>>> m.Question
0 0 5 | 3 0 0 | 0 0 0
8 0 0 | 0 0 0 | 0 2 0
0 7 0 | 0 1 0 | 5 0 0
------+-------+------
4 0 0 | 0 0 5 | 3 0 0
0 1 0 | 0 7 0 | 0 0 6
0 0 3 | 2 0 0 | 0 8 0
------+-------+------
0 6 0 | 5 0 0 | 0 0 9
0 0 4 | 0 0 0 | 0 3 0
0 0 0 | 0 0 9 | 7 0 0
>>> m.Answer
1 4 5 | 3 2 7 | 6 9 8
8 3 9 | 6 5 4 | 1 2 7
6 7 2 | 9 1 8 | 5 4 3
------+-------+------
4 9 6 | 1 8 5 | 3 7 2
2 1 8 | 4 7 3 | 9 5 6
7 5 3 | 2 9 6 | 4 8 1
------+-------+------
3 6 7 | 5 4 2 | 8 1 9
9 8 4 | 7 6 1 | 2 3 5
5 2 1 | 8 3 9 | 7 6 4
>>> m.timeSolve()
2.914081335067749
>>> 

完整代码

class Matrix():
    def __init__(self):
        self.val = [[0 for _ in range(9)] for _ in range(9)]
        self.data = tuple(tuple(j for j in i) for i in self.val)

    def __repr__(self):
        return str(self.val)

    def __eq__(self,other):
        return all([self[i]==s for i,s in enumerate(other.val)])
            
    def __getitem__(self,item):
        return self.val[item]

    def __setitem__(self,item,x):
        if len(x)==9 or set(x)=={i for i in range(1,10)}:
            self.val[item] = list(x)
        else:
            raise ValueError('x is list(), and its length is 9')

    def init1(self,lst=None):
        from random import sample
        from random import choice
        if lst!=None and isinstance(lst,list):
            if set(lst)!={i for i in range(1,10)}: lst=None
        while not self.valid:
            for i in range(9): self[i]=[0 for _ in range(9)]
            self.val[0] = lst if lst!=None else sample([_ for _ in range(1,10)],9)
            for i in range(2):
                if i==0:
                    self[1][:3] = sample(set(self[0])-set(self[0][:3]),3)
                    self[2][:3] = sample(set(self[0])-set(self.N[0]),3)
                else:
                    self[0][3:] = sample(set(self.T[0])-set(self[0]),6)
                self[1][3:-3] = sample(set(self[0])-set(self[0][3:-3])-set(self[1]),3)
                self[2][3:-3] = sample(set(self[0])-set(self.N[1]),3)
                self[1][-3:] = sample(set(self[0])-set(self[1]),3)
                self[2][-3:] = sample(set(self[0])-set(self[2]),3)
                self.val = self.T.val
            for i in range(3,9):
                for j in range(3,9):
                    t = self.fill(i,j)
                    if t!=set(): self[i][j]=choice(list(t))
                    else:break
                if t==set():break
        self.data = tuple(tuple(j for j in i) for i in self.val)
        return self

    def init(self,lst=None):
        from random import sample
        if lst!=None and isinstance(lst,list):
            if set(lst)!={i for i in range(1,10)}: lst=None
        t = False
        while not t:
            for i in range(9): self[i]=[0 for _ in range(9)]
            self.val[0] = lst if lst!=None else sample([_ for _ in range(1,10)],9)
            self[1][:3] = sample(set(self[0])-set(self[0][:3]),3)
            self[2][:3] = sample(set(self[0])-set(self.N[0]),3)
            #self[1][3:-3] = sample(set(self[0])-set(self[0][3:-3])-set(self[1]),3)
            #self[2][3:-3] = sample(set(self[0])-set(self.N[1]),3)
            t = Matrix.solve(self.val)
        self.data = tuple(tuple(j for j in i) for i in self.val)
        return self

    @property
    def valid(self):
        return all([set(i)=={i for i in range(1,10)} for i in self.val+self.N.val+self.T.val])

    def fill(self,i,j):
        if self[i][j]:return self[i][j]
        t = [x for x in [y for y in range(1,10) if y not in self[i]] if x not in self.T[j]]
        return {x for x in t if x not in self.N[i//3*3+j//3]}

    @property
    def T(self):
        t = Matrix()
        t.val = [[self.val[i][j] for i in range(9)] for j in range(9)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t

    @property
    def T1(self):
        t = Matrix()
        t.val = [[self[i][j] for j in range(8,-1,-1)] for i in range(9)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t

    @property
    def T2(self):
        t = Matrix()
        t.val = [[self[i][j] for j in range(9)] for i in range(8,-1,-1)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t
    
    @property
    def T3(self):
        t = Matrix()
        t.val = [[self[i][j] for j in range(8,-1,-1)] for i in range(8,-1,-1)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t

    @property
    def N(self):
        t = Matrix()
        t.val = [[self[i+3*m][j+3*n] for i in range(3) for j in range(3)]
                        for m in range(3) for n in range(3)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t

    @property
    def M(self):
        t = Matrix()
        t.val[3],t.val[5] = t.val[5],t.val[3]
        t.val = [[self[i+3*m][j+3*n] for i in range(3) for j in range(3)]
                        for m in range(3) for n in range(3)]
        t.data = tuple(tuple(j for j in i) for i in t.val)
        return t

    def R(self,x,y):
        if x not in [1,2,3] or y not in [1,2,3]:
            raise ValueError('x or y range: 1,2,3')
        if x==y: return self
        s = Matrix()
        s.val = self.val
        if x>y: x,y=y,x
        if x==1 and y==2:
            s[0],s[1],s[2],s[3],s[4],s[5] = s[3],s[4],s[5],s[0],s[1],s[2]
        if x==1 and y==3:
            s[0],s[1],s[2],s[6],s[7],s[8] = s[6],s[7],s[8],s[0],s[1],s[2]
        if x==2 and y==3:
            s[3],s[4],s[5],s[6],s[7],s[8] = s[6],s[7],s[8],s[3],s[4],s[5]
        return s

    def Rn(self,n,x,y):
        if n not in [1,2,3] or x not in [1,2,3] or y not in [1,2,3]:
            raise ValueError('n or x or y range: 1,2,3')
        if x==y: return self
        if x>y: x,y=y,x
        x,y = x-1+(n-1)*3,y-1+(n-1)*3
        s = self.T.T
        s[x],s[y] = s[y],s[x]
        return s

    def Cn(self,n,x,y):
        if n not in [1,2,3] or x not in [1,2,3] or y not in [1,2,3]:
            raise ValueError('n or x or y range: 1,2,3')
        if x==y: return self
        if x>y: x,y=y,x
        x,y = x-1+(n-1)*3,y-1+(n-1)*3
        s = self.T
        s[x],s[y] = s[y],s[x]
        return s.T

    def C(self,x,y):
        if x not in [1,2,3] or y not in [1,2,3]:
            raise ValueError('x or y range: 1,2,3')
        if x==y: return self
        s = self.T
        s.R(x,y)
        return s.T

    def pprint(self):
        for k,i in enumerate(self.val):
            for j,n in enumerate(i):
                print(n,end='' if j==8 else ' | ' if j%3==2 else ' ')
            print()
            if k%3==2 and k!=8: print('-'*6+'+'+'-'*7+'+'+'-'*6)

    def __find__(mat,i,j):
        for x in range(i,9):
            for y in range(j,9):
                if mat[x][y]==0: return x,y
        for x in range(9):
            for y in range(9):
                if mat[x][y]==0: return x,y
        return -1,-1

    def __valid__(mat,i,j,n):
        if all([n!=mat[i][j] for j in range(9)]):
            if all([n!=mat[i][j] for i in range(9)]):
                X,Y = i//3*3,j//3*3
                for x in range(X,X+3):
                    for y in range(Y,Y+3):
                        if mat[x][y]==n: return False
                return True
        return False

    def solve(mat,i=0,j=0):
        i,j = Matrix.__find__(mat,i,j)
        if i == -1: return True
        for n in range(1,10):
            if Matrix.__valid__(mat,i,j,n):
                mat[i][j] = n
                if Matrix.solve(mat,i,j): return True
                mat[i][j] = 0
        return False

    def create(self,mat):
        if mat==None and isinstance(mat,list):
            raise ValueError('mat is a list of 9x9 Matrix')
        if not all([len(j)==9 for j in mat]) or len(mat)!=9:
            print('Sudoku must be a 9x9 Matrix')
            return
        self.val = mat
        t = self.T.T
        tmp = [i for i in t.val+t.N.val+t.T.val]
        for i in tmp:
            j = [j for j in i if j!=0]
            if len(j)!=len(set(j)):
                print('Duplicate values in a row(or column or block).')
                return
        print('Solving...')
        if t.solve():
            ret = Sudo()
            print('Soluted!')
            ret.mat.val = mat
            self.data=ret.mat.data = tuple(tuple(j for j in i) for i in t.val)
            return ret
        else:
            self.data = ['Nil']
            print('No solution.')

    @property
    def answer(self):
        sudo = Matrix()
        sudo.val = self.data
        sudo.pprint()

class Sudo():
    def __init__(self,level=4):
        t = Matrix()
        self.mat = self.matrix = t.init()
        if level not in range(8):
            raise ValueError('level range: 1,2,3,4,5,6,7')
        zero = []
        from random import choice
        while len(zero)<level*10:
            if level==0: break
            t = [i for i in range(9)]
            t = (choice(t),choice(t))
            if t not in zero: zero.append(t)
        for i in zero:
            self.Modify(i[0]+1,i[1]+1,0)
        self.zero = sorted(zero)
        
    def __repr__(self):
        return str(self.mat)

    def pprint(self):
        self.matrix.pprint()

    @property
    def valid(self):
        return self.matrix.valid

    def build(n,level=4):
        global Sudoku
        if not isinstance(n,int) or n<1 or n>50:
            raise ValueError('level range: 1,2,3,...,50')
        #print('Initializing...')
        Sudoku = []
        for i in range(n):
            Sudoku.append(Sudo(level))
        for i,m in enumerate(Sudoku):
            print(f'No. {i+1}:')
            m.pprint()

    def Get(self,x,y):
        if x*y==0 or not -10<x<10 or not -10<y<10:
            raise ValueError('0<|x|,|y|<10')
        if x>0: x-=1
        if y>0: y-=1
        return self.mat.data[x][y]

    def Try(self,x=0,y=0):
        if x==0==y:
            return [(i+1,j+1) for i in range(9) for j in range(9) if self.mat[i][j]==0]
        if x*y==0 or not -10<x<10 or not -10<y<10:
            raise ValueError('0<|x|,|y|<10')
        if x>0: x-=1
        if y>0: y-=1
        num = self.mat.val[x][y]
        if num: return num
        return self.mat.fill(x,y)

    def Fill(self,x,y,value):
        if x*y==0 or not -10<x<10 or not -10<y<10:
            raise ValueError('0<|x|,|y|<10')
        if x>0: x-=1
        if y>0: y-=1
        if self.mat.val[x][y]==0:
            self.mat.val[x][y] = value
            return True
        else:
            return False

    def Modify(self,x,y,value):
        if x*y==0 or not -10<x<10 or not -10<y<10:
            print(x,y)
            raise ValueError('0<|x|,|y|<10')
        if x>0: x-=1
        if y>0: y-=1
        if self.mat.data[x][y]!=0:
            self.mat.val[x][y] = value
            return True
        else:
            return False

    @property
    def Question(self):
        sudo = self
        sudo.val = self.mat.data
        for i in self.zero:
            sudo.Fill(i[0]+1,i[1]+1,0)
        sudo.pprint()
        
    @property
    def Answer(self):
        return self.mat.answer

    def Create(self,matrix):
        zero = []
        for i,m in enumerate(matrix):
            for j,n in enumerate(m):
                if matrix[i][j]==0:
                    zero.append((i,j))
        self.zero = sorted(zero)
        self.mat.create(matrix)

    def Solve(self):
        if Matrix.solve(self.mat): return True
        return False

    def timeSolve(self):
        from time import time
        t = time()
        Matrix.solve(self.mat)
        print(time()-t)

matrixSample = [
	[8,0,0,0,0,0,0,0,0],
	[0,0,3,6,0,0,0,0,0],
	[0,7,0,0,9,0,2,0,0],
	[0,5,0,0,0,7,0,0,0],
	[0,0,0,0,4,5,7,0,0],
	[0,0,0,1,0,0,0,3,0],
	[0,0,1,0,0,0,0,6,8],
	[0,0,8,5,0,0,0,1,0],
	[0,9,0,0,0,0,4,0,0]]

代码有点繁杂,还可能有不少Bug;本人有点偏爱用推导式解决问题。但这个“数独游戏”也能够简单玩玩了,特别是批量生成数独题目特别方便。下次再补个gui界面,用键鼠来游戏操作才方便。


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/27714.html

数独  空格  矩阵  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 整容99次,归来做未婚妻后爸大结局_姜茜柳眉姜小姐抖音热门_小说后续在线阅读_无删减免费完结_
  • 朝徽宜燕澹容是什么小说(难搞!燕总又争又抢)(朝徽宜燕澹容)全本完整清爽版在线+无广告结局
  • 重生后我去扫厕所,鉴宝女神却疯了阅读_帝王小姐陈列精校文本_小说后续在线阅读_无删减免费完结_
  • 鹤不归顾宁喧林绾绾完结篇(顾宁喧林绾绾)全篇免费版在线+无障碍结局
  • 终章小说简明月顾烬深完结篇(你走后月光沉入深海)已更新+延伸(简明月顾烬深)清爽版
  • 我死后前夫疯魔了全书阮星舟霍景时在线
  • 救命!我被痴女包围了!列表_救命!我被痴女包围了!(神岛裕树)
  • 被亲姐封印百年,她死后我覆灭三界优质全文_封印小老仙老夫新上热文_小说后续在线阅读_无删减免费完结_
  • 全文七零香江,玄学大佬靠算命发家致富(柳玄黄招娣)列表_全文七零香江,玄学大佬靠算命发家致富
  • 七零娇娇美又媚,冷硬糙汉逃不掉续集(纪淮宋安宁)全本完整免费版_起点章节+后续(七零娇娇美又媚,冷硬糙汉逃不掉)
  • 重活一世,我钓到了真正的顾家家主热门推荐_顾星伯父顾星承阅读_小说后续在线阅读_无删减免费完结_
  • 重生之团长老公才是白月光小说(蒋横波姚沐兰)外篇+结局(重生之团长老公才是白月光)全篇在线阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1