LeetCode-Python-37. 解数独

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode-Python-37. 解数独，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1590字，纯文字阅读大概需要3分钟。

内容图文

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

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

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

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

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

思路：

回溯，一个数一个数地试……

不知道为什么board的值会变，所以只好用了一个self.result来存答案

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        from collections import defaultdict
        row, column, squre  = defaultdict(set), defaultdict(set), defaultdict(set)
        fill_list = []
        for i in range(9):
            for j in range(9):
                if board[i][j].isdigit(): #排除掉空的情况
                    row[i].add(board[i][j].encode("utf-8"))
                    column[j].add(board[i][j].encode("utf-8"))
                    squre[(i // 3, j // 3)].add(board[i][j].encode("utf-8"))
                else:
                    fill_list.append([i, j])
                    
        self.result = []           
        def backtrack(idx):
            if idx == len(fill_list):
                for row1 in board:
                    self.result.append(row1[:])
                return
            if not self.result:
                i, j = fill_list[idx][0], fill_list[idx][1]
                for digit in range(1, 10):
                    if str(digit) in row[i] or str(digit) in column[j] or str(digit) in squre[(i // 3, j // 3)]:
                        continue

                    board[i][j] = str(digit)
                    row[i].add(board[i][j])
                    column[j].add(board[i][j])
                    squre[(i // 3, j // 3)].add(board[i][j])

                    backtrack(idx + 1)

                    row[i].remove(board[i][j])
                    column[j].remove(board[i][j])
                    squre[(i // 3, j // 3)].remove(board[i][j])

        backtrack(0)  
        for i in range(9):
            for j in range(9):
                board[i][j] = self.result[i][j]

内容总结

以上是互联网集市为您收集整理的LeetCode-Python-37. 解数独全部内容，希望文章能够帮你解决LeetCode-Python-37. 解数独所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端