-
Notifications
You must be signed in to change notification settings - Fork 0
/
#37 Sudoku
24 lines (22 loc) · 952 Bytes
/
#37 Sudoku
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// https://leetcode.com/problems/sudoku-solver/
def solveSudoku(self, board):
m = len(board)
n = len(board) if m else 0
seen, points =set(), []
for i in range(m):
for j in range(n):
if board[i][j] == '.':
points.append((i, j))
else:
seen.update([str(i) + 'r' + board[i][j], str(j) + 'c' + board[i][j], str(i/3) + str(j/3) + board[i][j]])
def dfs(points, i, board, v):
if i == len(points): return True
x, y = points[i]
for j in range(1, 10):
tmp = set([str(x) + 'r' + str(j), str(y)+ 'c'+ str(j), str(x/3) + str(y/3) + str(j)])
if not tmp&v:
board[x][y] = str(j)
if dfs(points, i + 1, board, v | tmp ): return True
board[x][y] = '.'
return False
dfs(points, 0, board, seen)