Python回溯算法解数独

Python解数独题目，基本的方式就是通过回溯和递归，网上的案例很多，这里我是一步一步分析，然后解决这个问题，顺便讲解递归算法的应用。

题目：download-csv

完整代码：download-sudoku.py

一、题目说明

题目如下，其中空白格用0代替

表格第一行是列标题，不是题目内容。大概数一下，空格有50多个。

二、解题思路

1. 读取&加载题目

数独原始文件放在一个csv文件中，通过pandas读取，然后经过处理：

1. 对空白格处填充0，dataframe.fillna(0, inplace=True)

2. pandas读取的数据，默认是float类型，需要将数据类型转化为int，dataframe[i] = dataframe[i].astype(int)

3. 将pandas读取的数据为dataframe，需要进一步转化为list，方便使用下标进行操作，self.data = dataframe.values

    def __init__(self, file_path):
        self.data = None
        self.blank = None
        self.file_path = file_path

    def load(self):
        dataframe = pd.read_csv(self.file_path, sep=',', header=None)
        dataframe.fillna(0, inplace=True)
        for i in range(9):
            dataframe[i] = dataframe[i].astype(int)
        self.data = dataframe.values

2. 读取空白格

空白格（填充0）就是需要填入数字的内容，先读取list，判断有多少个空格。

将需要填充的空格放入list，后续通过回溯和递归算法，处理空格内容。

    def search_blank(self):
        blank_list = []
        for r in range(9):
            for c in range(9):
                if self.data[r][c] == 0:
                    blank_list.append([r, c])
        self.blank = blank_list
        return blank_list

3. 判断空白格数字有效性

根据数独的规则，行、列以及小九宫格内数字是唯一的，需要验证填入的数字是否有效。 这里三个规则的判断是分别分开验证，方便理解和学习。

• 小九宫格判断

  根据空白格的位置（pos），对九宫格（3×3）遍历，填入数字（num）是否符合规则

# pos是一个list，定义了表格的row和col
    # 验证一个数num在对应的区块中是否符合规则
    def block_valid(self, num, pos):
        row_start = (pos[0] // 3) * 3
        col_start = (pos[1] // 3) * 3
        row_end = row_start + 2
        col_end = col_start + 2
        for r in range(row_start, row_end + 1):
            for c in range(col_start, col_end + 1):
                # print(r, c, self.data[r][c])
                if num == self.data[r][c]:
                    return False
        return True

• 行内数据判断

  对行内9个数进行遍历，填入数据（num）是否符合规则。

    def row_valid(self, num, pos):
        for c in range(9):
            # print(pos[0], c, self.data[pos[0]][c])
            if num == self.data[pos[0]][c]:
                return False
        return True
  

• 列内数据判断

  对列内9个数进行遍历，填入数据（num）是否符合规则。

    def col_valid(self, num, pos):
        for r in range(9):
            # print(r, pos[1], self.data[r][pos[1]])
            if num == self.data[r][pos[1]]:
                return False
        return True

4. 回溯算法处理

通过回溯和递归处理全部空白格，是解数独的核心。 经过前面的处理（读取数据、查找空白格、对行、列、九宫格判断），下一步就是使用回溯和递归逐个处理空白格 处理空白格的逻辑很简单，从1-9验证每个空格填入数字是否可行：

1. 递归的终止条件：空白格list全部处理完为空，即list 长度为0:if len(self.blank) == 0:return True
2. 尝试从1-9逐个取出数据（for循环），然后从空白格list中弹出(pop)一个空白格填入，验证行、列、九宫格是否符合数独规则
3. 如果符合规则，使用递归再次调用此函数；
4. 如何不符合规则，将此空白格再次压入(append)空白格list中，同时此空白格填充0，回溯至上一步
5. 直到全部处理完毕，或者没有正确的解，返回False

    def backtrace(self):
        if len(self.blank) == 0:
            self.show_table()
            return True
        else:
            for num in range(1, 10, 1):
                pos = self.blank[-1]
                if self.block_valid(num, pos) and self.row_valid(num, pos) and self.col_valid(num, pos):
                    self.data[pos[0]][pos[1]] = num
                    # self.show_table()
                    self.blank.pop()
                    if self.backtrace():
                        return True
                    self.data[pos[0]][pos[1]] = 0
                    self.blank.append(pos)
        return False

• 题目答案为：

  将表格打印的注释取消，可以观察到，解数独的过程是从表格的最后一个数字开始演算，这就符合题目的思路，空白格list是从最后一个元素先处理，这个元素就是整个数独表的最后一个空白格。

  其次就是，解数独用到列回溯，list中空白格的弹出和压入，就是一个回溯的过程；

  同时，解数独用到了递归，在前一个空白格填入的数字符合行、列以及九宫格要求后，再次调用函数自身，进行下一个空白格的处理，直到全部空白格处理完毕（空白格list为0，递归终止条件），表明数据全部解题完毕