数独
数独起源于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界面，用键鼠来游戏操作才方便。
