python 解数独

概述题目思路我们可以检查每行、每列、每子宫格的数字，如果每行、每列、每子宫格的数字中都没有此数字，则可以判定为可填入，否则不可填入。循环多次之后，最终得到全部的结果。代码classSolution:defsolveSudoku(self,board:List[List[str]])->None:defcheck(x, 题目

思路

我们可以检查每行、每列、每子宫格的数字，如果每行、每列、每子宫格的数字中都没有此数字，则可以判定为可填入，否则不可填入。

循环多次之后，最终得到全部的结果。

代码

class Solution:    def solveSudoku(self, board: List[List[str]]) -> None:      def check(x, y, s): #判断要插入的数s是否可以插入board[x][y]            for i in range(9):                if board[i][y] == s or board[x][i] == s:                    return False            for i in [0, 1, 2]:                for j in [0, 1, 2]:                    if board[x//3*3+i][y//3*3+j] == s:                        return False            return True                def bt(cur):  #参数为数独中正确位置的个数            if cur == 81:                return True            x, y = cur // 9, cur % 9            if board[x][y] != '.':                return bt(cur + 1)            for i in range(1, 10):                s = str(i)                if check(x, y, s):                    board[x][y] = s                    if bt(cur + 1):                        return True                    board[x][y] = '.'            return False                bt(0)           

结果

复杂度

时间复杂度:O(n^3)

空间复杂度: O(1)

总结

以上是内存溢出为你收集整理的python 解数独全部内容，希望文章能够帮你解决python 解数独所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。