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
| class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
def dfs(usedCol, usedRow, usedGrid, col, row):
if col == 9:
col = 0
row += 1
if row == 9:
print(board)
return True
if board[row][col] != '.':
if dfs(usedCol, usedRow, usedGrid, col + 1, row):
return True
else:
for i in range(9):
if not usedRow[row][i] and not usedCol[col][i] and not usedGrid[row // 3][col // 3][i]:
usedRow[row][i] = True
usedCol[col][i] = True
usedGrid[row // 3][col // 3][i] = True
board[row][col] = str(i + 1)
if dfs(usedCol, usedRow, usedGrid, col + 1, row):
return True
board[row][col] = '.'
usedRow[row][i] = False
usedCol[col][i] = False
usedGrid[row // 3][col // 3][i] = False
return False
usedCol = [[False] * 9 for i in range(9)]
usedRow = [[False] * 9 for i in range(9)]
usedGrid = [[[False] * 9 for i in range(3)] for j in range(3)]
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = ord(board[i][j]) - ord('1')
usedRow[i][num] = True
usedCol[j][num] = True
usedGrid[i // 3][j // 3][num] = True
dfs(usedCol, usedRow, usedGrid, 0, 0)
|
