37. Sudoku Solver
这题是一道backtracking的题，难点在于backtracking进入下一层之前要做的事情，和退出下一层后要做的事情。
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
self.found = False
self.dfs(board, 0, 0)
print self.found
def dfs(self, board, i, j):
if j == 9:
self.found = True
return
if board[i][j] == '.':
for number in list("123456789"):
if self.valid(board, i, j, number):
board[i][j] = number
if i == 8:
self.dfs(board, 0, j+1)
else:
self.dfs(board, i+1, j)
if not self.found:
board[i][j] = "."
else:
if i == 8:
self.dfs(board, 0, j+1)
else:
self.dfs(board, i+1, j)
def valid(self, board, row, col, number):
# row
if number in board[row]:
return False
# col
for i in range(len(board)):
if board[i][col] == number:
return False
start_row = row / 3 * 3
start_col = col / 3 * 3
for i in range(3):
for j in range(3):
if board[start_row+i][start_col+j] == number:
return False
return True
