-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2239.py
More file actions
45 lines (42 loc) · 1.06 KB
/
2239.py
File metadata and controls
45 lines (42 loc) · 1.06 KB
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
import collections
import sys
sdoku = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(9)]
area = [[[0, 0], [0, 3], [0, 6]],
[[3, 0], [3, 3], [3, 6]],
[[6, 0], [6, 3], [6, 6]]]
zero = []
answer = [False]
for i in range(9):
for j in range(9):
if sdoku[i][j] == 0:
zero.append([i, j])
def can_in(k, l, num):
if num in sdoku[k]:
return False
for i in range(9):
if sdoku[i][l] == num:
return False
y, x = area[k // 3][l // 3][0], area[k // 3][l // 3][1]
for i in range(y, y + 3):
for j in range(x, x + 3):
if sdoku[i][j] == num:
return False
return True
def dfs(n):
if n == len(zero):
answer[0] = True
return True
y, x = zero[n]
for j in range(1, 10):
if can_in(y, x, j):
sdoku[y][x] = j
dfs(n + 1)
if(answer[0]):
return
sdoku[y][x] = 0
return False
dfs(0)
for i in range(9):
for j in range(9):
print(sdoku[i][j],end='')
print()