【LeetCode】0037 解数独

https://leetcode-cn.com/problems/sudoku-solver/

# -*- coding:utf-8 -*-
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        def check(x, y, s):
            """
            检查当前输入是否合法
            :param x:
            :param y:
            :param s:
            :return:
            """
            # 检查横竖
            for i in range(9):
                if board[x][i] == s or board[i][y] == s:
                    return False
            # 检查3*3
            for i in range(3):
                for j in range(3):
                    if board[x // 3 * 3 + i][y // 3 * 3 + j] == s:
                        return False
            return True
        def find_s(cur_idx):
            """
            回朔寻找合适的s
            :param cur_idx:
            :return:
            """
            if cur_idx == 81:
                return True
            # 确定x y
            x, y = cur_idx // 9, cur_idx % 9
            if board[x][y] != '.':
                return find_s(cur_idx + 1)
            for i in range(1, 10):
                str_s = str(i)
                if check(x, y, str_s):
                    board[x][y] = str_s
                    if find_s(cur_idx + 1):
                        return True
                    # 检查不通过，需要回朔，因此将这个位置恢复为空
                    board[x][y] = '.'
            return False
        return find_s(0)
if __name__ == '__main__':
    board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."],
             [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
             ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
             [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"],
             [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
    print(Solution().solveSudoku(board))

思路：其实刚开始并不知道怎么解数独，我解数独多半就是一点点试的2333。我去知乎搜了一圈，发现了一些简单的（对于人）的解法，就是把每一个空白的可填数字找到，使用 三到四个约束条件， 一点点的确定空白或者缩减可填数字列表以此慢慢解出整个数独。

但是这个方法说实话对于人简单，但是对于机器，好多判断逻辑需要大量的代码支撑，因此选择了对于机器相对友好对于人相对就不友好的回朔法进行求解。

这个方法类似于递归穷举，可以简单理解成有一个9*9的栈，每瞎填一个地方就入栈，栈满说明解出了数独。

先随机放一个满足当前位置条件的数，然后一直向后寻找，如果某个位置没办法放置满足条件的数，那么就回溯（就是出栈）直至可以继续计算下一个位置的索引（十分类似于深搜）。