-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.py
123 lines (107 loc) · 2.54 KB
/
sudoku.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@File : sudoku.py
@Contact : admin@gksec.com
@License : (C)Copyright 2007, GNU General Public License V3
@Modify Time @Author @Version @Desciption
------------ ------- -------- -----------
2020/3/26 15:28 W4ter 1.0 None
"""
class point:
"""
初始化方法
建立坐标系
"""
def __init__(self,x,y):
self.x = x
self.y = y
self.available = []
self.value = 0
def rowNum(p,sudoku):
"""
判断行
:return:
"""
row = set(sudoku[p.y * 4:(p.y + 1) * 4])
row.remove(0)
return row
def colNum(p,sudoku):
"""
判断列
:return:
"""
col = []
length = len(sudoku)
for i in range(p.x,length,4):
col.append(sudoku[i])
col = set(col)
col.remove(0)
return col
def initPoint(sudoku):
"""
找到需要填充的位置
:return:
"""
pointList = []
length = len(sudoku)
for i in range(length):
if sudoku[i] == 0:
p = point(i % 4,i // 4) #遍历所有的点
for j in range(1,5): #找到不重复的结果
if j not in rowNum(p,sudoku) and j not in colNum(p,sudoku):
p.available.append(j)
pointList.append(p)
return pointList
def tryInsert(p,sudoku):
"""
对于每个需要的位置进行填充
:return:
"""
availNum = p.available
for v in availNum:
p.value = v
if check(p,sudoku):
sudoku[p.y*4 + p.x] = p.value
if len(pointList) <= 0:
showSudoku(sudoku)
exit()
p2 = pointList.pop()
tryInsert(p2,sudoku)
sudoku[p2.y * 4 + p2.x] = 0
sudoku[p.y * 4 + p.x] = 0
p2.value = 0
pointList.append(p2)
else:
pass
def check(p,sudoku):
"""
判断填充条件
:return:
"""
#如果为0就不填充
if p.value == 0:
return False
#再次检查填充的点是否与当前已经填充的点重复
if p.value not in rowNum(p,sudoku) and p.value not in colNum(p,sudoku):
return True
else:
return False
def showSudoku(sudoku):
"""
定义输出格式
"""
for j in range(4):
for i in range(4):
print('%d '%(sudoku[j * 4 + i]),end='')
print('')
if __name__ == '__main__':
sudoku = [
4,0,0,0,
0,0,0,1,
0,0,1,0,
0,0,3,4,
]
pointList = initPoint(sudoku)
p = pointList.pop()
tryInsert(p,sudoku)