[LeetCode]37 解数独

题目描述

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。

3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

   空白格用 '.' 表示。

   

   一个数独。

   

   答案被标成红色。

   Note:

• 给定的数独序列只包含数字 1-9 和字符 '.' 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

代码

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def Boardcyc(rowaray,colarray,cellarray,dotpos,k):
            if k == len(dotpos):
                return True
            i,j = dotpos[k]
            indexij = i//3*3 + j//3
            res = rowarray[i]&colarray[j]&cellarray[indexij]
            if len(res) == 0:
                return False
            for one in res:
                rowarray[i].remove(one)
                colarray[j].remove(one)
                cellarray[indexij].remove(one)
                board[i][j] = one
                if Boardcyc(rowarray,colarray,cellarray,dotpos,k+1):
                    return True
                else:
                    rowarray[i].add(one)
                    colarray[j].add(one)
                    cellarray[indexij].add(one)
                    board[i][j] = '.'
            return False
        onearray = set(map(str,[1,2,3,4,5,6,7,8,9]))
        rowarray = [onearray.copy() for _ in range(9)]
        colarray = [onearray.copy() for _ in range(9)]
        cellarray = [onearray.copy() for _ in range(9)]
        dotpos = []
        for i in range(9):
            indexi = i//3*3
            for j in range(9):
                if board[i][j] == '.':
                    dotpos.append([i,j])
                else:
                    rowarray[i].remove(board[i][j])
                    colarray[j].remove(board[i][j])
                    cellarray[indexi+j//3].remove(board[i][j])
        if len(dotpos) == 0:
            return True
        Boardcyc(rowarray,colarray,cellarray,dotpos,0)