递归回溯实现

退出条件全部遍历结束

  // 全部结束   
 if (count == 81):  # 递归出口
        return True
 // 已经填充过了
# 行优先遍历
row = count // 9  # 行标
col = count % 9  # 列标
if matrix[row][col] != 0:  # 已填充
    return solveSudoku(matrix, count=count + 1)

递归

    for i in range(1, 10):
        if check(matrix, row, col, i):  # 找到可能的填充数
            matrix[row][col] = i
            if solveSudoku(matrix, count=count + 1):  # 是否可完成
                return True  # 可完成
            # 不可完成
            matrix[row][col] = 0  # 回溯
    return False  # 不可完成

每个数字检查

  • 每一行包含1~9
  • 每列包含1~9
  • 3 *3 区域包含 1~9
def check(matrix, row, col, value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    # 检测每行
    for j in range(9):
        if matrix[row][j] == value:
            return False
    # 检测每列
    for i in range(9):
        if matrix[i][col] == value:
            return False
    # 检测元素所在3*3区域
    area_row = (row // 3) * 3
    area_col = (col // 3) * 3
    for i in range(area_row, area_row + 3):
        for j in range(area_col, area_col + 3):
            if matrix[i][j] == value:
                return False
    return True

整体代码

点击查看代码 
def check(matrix, row, col, value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    # 检测每行
    for j in range(9):
        if matrix[row][j] == value:
            return False
    # 检测每列
    for i in range(9):
        if matrix[i][col] == value:
            return False
    # 检测元素所在3*3区域
    area_row = (row // 3) * 3
    area_col = (col // 3) * 3
    for i in range(area_row, area_row + 3):
        for j in range(area_col, area_col + 3):
            if matrix[i][j] == value:
                return False
    return True


def solveSudoku(matrix, count=0):
    """
    遍历每一个未填元素，遍历1-9替换为合适的数字
    """
    if (count == 81):  # 递归出口
        return True

    # 行优先遍历
    row = count // 9  # 行标
    col = count % 9  # 列标
    if matrix[row][col] != 0:  # 已填充
        return solveSudoku(matrix, count=count + 1)

    for i in range(1, 10):
        if check(matrix, row, col, i):  # 找到可能的填充数
            matrix[row][col] = i
            if solveSudoku(matrix, count=count + 1):  # 是否可完成
                return True  # 可完成
            # 不可完成
            matrix[row][col] = 0  # 回溯
    return False  # 不可完成


if __name__ == '__main__':
    matrix = [[0 for x in range(81)][i:i + 9] for i in range(0, 81, 9)]
    solveSudoku(matrix)
    for i in range(9):
        print(' '.join(map(str, matrix[i])))

原文地址：http://www.cnblogs.com/guanchaoguo/p/16852821.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性