二分类数据集 跨域 图像处理 计算机网络 sockets jpa layout reflection jar yii uiviewcontroller vue案例 bootstrap管理模板 安卓项目实战 sallenkey滤波器 oracle查看数据库 cos图像和sin图像 移动端上传图片插件 a标签去除下划线 python开发安卓应用 nfc卡片 python正则 python迭代 python自学教材 python如何调用函数 javaswitch java实现 java中的抽象类 javaswitch语句 java字符串长度 java环境部署 java写文件 java系统时间 java网页 shell编程学习 bcdautofix 数据挖掘原理与算法 win10有几个版本 gg修改器下载 cubase下载
当前位置: 首页 > 学习教程  > 编程语言

Python 解析数独

2021/2/13 17:23:35 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

前几天,四年级的弟弟拿着数独题来问我,我陷入了沉思,为了避免以后的尴尬,做了一个数独解析的算法。 """ 1、参数 grid是数独中所有的数 row是行下标 col是列下标 2、主要功能 寻找空值并返回对应的行列下标 3、返…

前几天,四年级的弟弟拿着数独题来问我,我陷入了沉思,为了避免以后的尴尬,做了一个数独解析的算法。
在这里插入图片描述

"""
1、参数
grid是数独中所有的数
row是行下标
col是列下标
2、主要功能
寻找空值并返回对应的行列下标
3、返回值
x、y是空值的行列下标
如果数独中没有空值,就返回-1,-1
"""


def getNullIndex(grid, row, col):
    # 从row,col开始遍历
    for x in range(row, 9):
        for y in range(col, 9):
            if grid[x][y] == 0:
                return x, y
    # 从头开始遍历
    for x in range(0, 9):
        for y in range(0, 9):
            if grid[x][y] == 0:
                return x, y
    # 没有空值返回-1,-1
    return -1, -1


"""
1、参数:
grid是数独中所有的数,row是行下标、col是列下标、value是填入的值
2、主要功能:
判断填入的值是否符合规则(行、列、九宫格不能重复规则)
3、返回值:
True代表符合规则,False代表不符合规则
"""


def judgeValue(grid, row, col, value):
    # 行结果
    rowValid = all([value != grid[row][x] for x in range(9)])
    # 行合法
    if rowValid:
        # 列结果
        colValid = all([value != grid[x][col] for x in range(9)])
        # 列合法
        if colValid:
            # 最小行、列的下标
            minRow, minCol = 3 * (row // 3), 3 * (col // 3)
            # 遍历所在的九宫格
            for x in range(minRow, minRow + 3):
                for y in range(minCol, minCol + 3):
                    if grid[x][y] == value:
                        return False
            # 九宫格合法
            return True
    # 行不合法
    return False


# 利用深度优先搜索去解决数独问题
"""
1、参数:
grid是数独中所有的数,row是行下标、col是列下标
2、主要功能:
开始填入正确的值
"""


def DFS2SD(grid, row=0, col=0):
    # 得到空值的index
    i, j = getNullIndex(grid, row, col)
    # 数独中没有空值
    if i == -1:
        return True
    # 填入1-10的所有数
    for k in range(1, 10):
        # 如果这个数字符合规则
        if judgeValue(grid, i, j, k):
            # 对空值进行赋值
            grid[i][j] = k
            # 调用自己,递归。
            if DFS2SD(grid, i, j):
                return True
            # 如果递归返回False,把空值复位为0
            grid[i][j] = 0
    return False


if __name__ == '__main__':
    # 构建数独,第1行,第二行...第n行,未知数用0代替。
    matrix = [[0, 1, 0, 0, 0, 8, 4, 0, 7], [9, 5, 0, 0, 0, 0, 0, 0, 0], [0, 0, 8, 0, 1, 0, 0, 0, 0],
              [0, 8, 2, 0, 0, 0, 0, 0, 0], [7, 0, 0, 4, 0, 6, 0, 0, 8], [0, 0, 0, 0, 0, 0, 6, 2, 0],
              [0, 0, 0, 0, 5, 0, 7, 0, 0], [0, 0, 0, 0, 0, 0, 0, 8, 2], [5, 0, 3, 2, 0, 0, 0, 1, 0]]
    # 执行
    DFS2SD(matrix)
    # 输出
    print(matrix)
/*
结果
[[2, 1, 6, 9, 3, 8, 4, 5, 7], [9, 5, 4, 7, 6, 2, 8, 3, 1], [3, 7, 8, 5, 1, 4, 2, 6, 9], [6, 8, 2, 1, 9, 5, 3, 7, 4], [7, 3, 5, 4, 2, 6, 1, 9, 8], [4, 9, 1, 8, 7, 3, 6, 2, 5], [8, 2, 9, 6, 5, 1, 7, 4, 3], [1, 6, 7, 3, 4, 9, 5, 8, 2], [5, 4, 3, 2, 8, 7, 9, 1, 6]]
*/

总结

十六阶的数独,只需要把9改为16,10改为17即可,换汤不换药,原理一致。


本文链接: http://www.dtmao.cc/news_show_700136.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?