Sudoku Solver

这道题的问题主要就是要找到valid sudoku那道题里面的快速查找subbox重复与否的方法，如果找到了这个方法，这道题实际上就和N皇后问题一样穷举即可了，不过此题的穷举还有一些需要注意的地方就是需要返回布尔值来让结果停留在正确答案上而不会被修改回原始状态，另外这里最外层的返回值不是一般DFS的false而是true，false值被放在了if判断里面，代表对一个位置我们穷举了九个数都不能有合法结果，那代表这个数独盘无法有正确答案

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if not n:
            return 
        m = len(board[0])
        if not m:
            return

        row = [[0] * 9 for _ in xrange(9)]
        col = [[0] * 9 for _ in xrange(9)]
        sub = [[0] * 9 for _ in xrange(9)]
        count = 0
        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] != '.':
                    num = ord(board[i][j]) - ord('0') - 1
                    k = i / 3 * 3 + j / 3
                    row[i][num] = 1
                    col[j][num] = 1
                    sub[k][num] = 1

        self.DFS(board, n, m, row, col, sub,)

    def DFS(self, board, n, m, row, col, sub):
        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] == '.':
                    for num in xrange(1, 10):
                        k = i / 3 * 3 + j / 3
                        if row[i][num - 1] or col[j][num - 1] or sub[k][num - 1]:
                            continue
                        board[i][j] = str(num)
                        row[i][num - 1], col[j][num - 1], sub[k][num - 1] = 1, 1, 1
                        if self.DFS(board, n, m, row, col, sub):
                            return True
                        else:
                            board[i][j] = '.'
                            row[i][num - 1], col[j][num - 1], sub[k][num - 1] = 0, 0, 0
                    return False
        return True