一、问题描述

数独(Sudoku)是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字,推算出所有剩余空格的数字,并且满足每一行、每一列、每一个粗线宫内的数字均含1-9,并且不重复。
输入:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出:
完整的9X9盘面数组

输入示例:

0 9 2 4 8 1 7 6 34 1 3 7 6 2 9 8 58 6 7 3 5 9 4 1 26 2 4 1 9 5 3 7 87 5 9 8 4 3 1 2 61 3 8 6 2 7 5 9 42 7 1 5 3 8 6 4 93 8 6 9 1 4 2 5 70 4 5 2 7 6 8 3 1

输出示例:

5 9 2 4 8 1 7 6 34 1 3 7 6 2 9 8 58 6 7 3 5 9 4 1 26 2 4 1 9 5 3 7 87 5 9 8 4 3 1 2 61 3 8 6 2 7 5 9 42 7 1 5 3 8 6 4 93 8 6 9 1 4 2 5 79 4 5 2 7 6 8 3 1

二、思路

对于这个题我们的第一思路当然是用深度遍历加回溯法来完成。

首先将数字存在9*9的二维数组数据结构内,其次寻找值为0的元素,将其换成1到9任一个数字。

　　若能满足称为数独的三个条件,则继续往下搜索值为0的元素。

　　　　同样将其换成0到9之间的任意数字,若发现所有的数字都不满足条件的话,则回溯到上一个点,并把该点的值继续换成其他数字。

　　直到所有的81个点都遍历完,若遍历完发现没有满足条件的值可以填满值为0的位子,则返回False。

三、代码实现

首先我们先写一个函数来判断数字num是否可以放到9*9矩阵的(row,col)位置上。

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)    else:#未填充        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#回溯, i换个数继续走        return False#不可完成matrix=[]for i in range(9):    matrix.append(list(map(int,input().split())))# print(matrix)solveSudoku(matrix,0)# print(solveSudoku(matrix,0))# for i in range(9):#     print (' '.join(map(str,matrix[i])))# print(matrix)for li in matrix:    print(' '.join(list(map(str,li))))

这里值得注意的一点是,我们可以用递归函数来判断,若我们将当前点的值设为 i 时,其余点是否可以完成数独游戏,即:

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,然后让他接着遍历0-9中的其余数即可。