优化算法之Python穷举数独

前言

本文的 Github 仓库

https://github.com/taurusxin/Sudoku

Python 穷举 Sudoku

玩法简介(来自百度百科)

数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。

从初中开始第一次接触数独,大大小小的也玩过很多。 学了计算机之后自然就会用算法去解决一些问题,本文讲解的就是在穷举数独之时,对相应的算法进行优化。

开发环境

  1. VSCode
  2. Python 3.x

在开始之前,先配置一下 VSCode 的运行环境,可以直接克隆我的Github仓库。 因为默认VSCode在文件夹下调试的时候,会以当前正在编辑的文件传入命令行,如果正在编辑其它的例如json/xml等文件,那运行就出错了。 在项目路径下建立文件夹 .vscode,然后新建文件 launch.json来构建运行的脚本。

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "Sudoku",
            "type": "python",
            "request": "launch",
            "program": "${workspaceRoot}/Sudoku.py",
            "args": ["test1.csv"],
            "console": "integratedTerminal"
        }
    ]
}

表示无论在哪个标签页,就会将 Sudoku.py 作为要运行的程序源文件传入解释器,并且将 test1.csv 作为第一个参数传入。

导入文件

lines = None
if len(argv) != 2:
    print(usage)
    return
f = None
if argv[1] in ('-h', '--help'):
    print(usage)
    return
try:
    f = open(argv[1], 'r', encoding='utf-8')
except IOError:
    print('Error: File do not exists!')
    return

lines = f.read().splitlines()
if len(lines) != 9:
    print('Error: Sudoku format error, type -h or --help for more.')
    return
grid = map(lambda i: i.split(","), lines)

def new_int(t):
    return int(t) if t else 0

grid = [list(map(new_int, i)) for i in grid]

初始的几行是命令行的解析及文件的打开 grid定义了整一个表格的列表,每一行为一个列表,9行构成了整个二维列表 这里看到,我定义了一个new_int函数,这因为 Python 自带的 int()函数不能将非0的字符转为0。

class 定义

class Sudoku(object):
    def __init__(self, board):
        self.b = board
        self.t = 0

构造函数引入了1个参数board,即数独二维列表的表格。 t为尝试的次数

尝试前的准备

def check_is_legal(self):
    # 判断每一行是否有效
    for i in range(9):
        for j in self.b[i]:
            if (j not in range(0, 10)) or (self.b[i].count(j) > 1 and j != 0):
                return False, 'There are %d same number %d in line %d.' % (self.b[i].count(j), j, (i + 1))
    # 判断每一列是否有效
    columns = [[r[col] for r in self.b] for col in range(len(self.b[0]))]
    for i in range(9):
        for j in columns[i]:
            if (j not in range(0, 10)) or (self.b[i].count(j) > 1 and j != 0):
                return False, 'There are %d same number %d in column %d.' % (self.b[i].count(j), j, (i + 1))
    # 判断九宫格是否有效
    for i in range(3):
        for j in range(3):
            grid = [tem[j * 3:(j + 1) * 3] for tem in self.b[i * 3:(i + 1) * 3]]
            merge_str = grid[0] + grid[1] + grid[2]  # 合并为一个list[]
            for m in merge_str:
                if (m not in range(0, 10)) or (merge_str.count(m) > 1 and m != 0):
                    return False, 'There are %d same number %d in block %d.' \
                           % (merge_str.count(m), m, (3 * i + j + 1))
    return True, 'OK'

def solve(self):
    is_legal, error_s = self.check_is_legal()
    if not is_legal:
        print("Error: The sudoku is illegal!")
        print(error_s)
        return

    begin = datetime.datetime.now()
    if self.b[0][0] == 0:
        self.try_it(0, 0)  # 如果第一格为空,则从此开始尝试
    else:
        x, y = self.get_next(0, 0)  # 否则就获得从第一个格子的下一个空格子开始
        self.try_it(x, y)

在开始尝试之前,当然要先检测一下数独是否合法,即给出的数独题目,是否每一行,每一列,每一宫都不得重复1-9

尝试函数的递归

def try_it(self, x, y):  # 主循环
    if self.b[x][y] == 0:
        possible = self.possible_num(x, y)
        for i in possible:  # 从可能的数字中尝试
            self.t += 1
            self.b[x][y] = i  # 将可能的数字填入0格
            next_x, next_y = self.get_next(x, y)  # 得到下一个0格
            if next_x == -1:  # 如果无下一个0格
                return True  # 返回True
            else:  # 如果有下一个0格,递归判断下一个0格直到填满数独
                end = self.try_it(next_x, next_y)
                if not end:  # 在递归过程中存在不符合条件的,即 使try_it函数返回None的项
                    self.b[x][y] = 0  # 回朔到上一层继续
                else:
                    return True

solve函数中,如果第一格格子为空,程序尝试着从第一格格子开始尝试,否则就从第一格格子的下一个开始尝试。 尝试的法则则为,用possible_num函数列举出当前格子可能的情况列表,然后从中逐个尝试,若遇到了这个格子为空,并且这个格子没有可能的数值,那么就发生错误,则回到上一个格子重新开始,将此格子清除

辅助功能函数

def get_next(self, x, y):  # 得到下一个未填项
    for next_solution in range(y + 1, 9):
        if self.b[x][next_solution] == 0:
            return x, next_solution
    for row_n in range(x + 1, 9):
        for col_n in range(0, 9):
            if self.b[row_n][col_n] == 0:
                return row_n, col_n
    return -1, -1  # 若无下一个未填项,返回-1

block_in_grid = {(x, y): (x // 3) * 3 + (y // 3) for x in range(9) for y in range(9)}
grid_get_block = {x: [] for x in range(9)}

for i, j in block_in_grid.items():
    grid_get_block[j].append(i)

def possible_num(self, x, y):  # 获得一个格子可能的数字集合
    whole = set(range(1, 10))
    x_set = set(self.b[x])
    y_set = {self.b[i][y] for i in range(9)}
    block_num = self.block_in_grid[(x, y)]
    block_set = {self.b[i][j] for i, j in self.grid_get_block[block_num]}
    return whole - x_set - y_set - block_set

这两个函数应该比较好理解,获得下一个未填格子,就是在表格中从当给出格子开始遍历,找到一个为非1-9的格子就返回,如果没有下一个,那就返回 -1, -1 可能的数,就是列出这个格子所在行、列、九宫格,然后用 Python集合 去做减法运算,除去重复项,剩下的就是可能项 block_in_gridgrid_get_block 两个字典就可以很方便地查询给出九宫格序号,返回格子坐标列表,或者给出格子坐标,返回所在的九宫格序号

结尾语

这个数独的解法,最初写出来时候,在尝试函数处,其代码如下

for i in range(1, 10):  # 从可能的数字中尝试

当然是在没有写出possible_num这个函数之前 如果从1到9遍历,查看最终结果,原本只需尝试80多次,现在需要尝试800多次,就做了很多不必要的尝试及回溯。 这就是这个算法的核心优化

Licensed under CC BY-NC-SA 4.0