- 实验背景
数独起源于拉丁方阵，由单元格、行、列、宫等元素组成，规则是在每行、每列、每宫的九个单元格中填入数字1-9，不重复。给定一定数量提示数的盘面作为初始条件，称为初盘。根据规则将所有单元格填满得到的盘面称为终盘，也就是数独的解。标准的数独初盘只能对应一个终盘。
一般采用随机方式生成数独，即从空白的数独盘面开始随机填数，填入的数字不能违背数独的基本规则，并且要保证解的唯一性。在随机填入过程中，判断某个位置是否可以填入一个随机的数是根据这一位置所处行列宫区域中是否已有此数来决定。当填入这一数之后，修改它所处区域的标记信息。当填入的数字达到一定量之后，再进行数独求解。
数独的求解常用的生成方法有挖洞法，即挖去一个数独终盘上某些位置上的数，使其形成的局面只有一个解，即做为数独初盘。初始的数独终盘，可根据一定的算法生成，也可以根据某个已知的终盘，进行若干次行列互换或数字的交换等方法得到。
实验需要我们通过设计算法来输出不同难度的数独题目和答案。
其中数独生成的规则为：根据9X9表盘上面的已知数字，推理出所有剩余空格的数字，并且需满足每一行、每一列、每个九宫格内的数字均含1-9，不重复。数独的难度通过对数独终盘挖掉数字的个数多少来划分。
①构造数独规则：先初始化数独空白表格，在空白数独中随机选择要求个空白单元格，筛选出该单元格满足条件的数字并填入。
②深度优先算法：定义深度优先算法。
③基础数独生成：使用深度优先算法对已经部分填入的数独进行遍历求解，输出基本数独。
④实现难度划分：在已经求解完毕的基本数独上随机选取单元格，假设扣除该单元格的数字并检验扣除后数独的唯一性，直至成功扣除指定个数的单元格，生成对应难度的数独题目。再次使用深度优先算法对扣除指定个数单元格的数独题进行遍历求解，并输出对应的数独答案。
①定义类Sudoku
class Sudoku:
def __init__(self):
# 初始化九宫格
self.grids= np.zeros((9, 9), dtype=int, order=‘C’)
self.possibleNums= { 1, 2, 3, 4, 5, 6, 7, 8, 9}
# 用于挖洞时保存挖好的数独
self.uniqueGrids = None
②使用Python，导入Numpy库，使用矩阵来保存和处理数独数据。使用zeros方法生成9X9的的0矩阵，初始化数独。导入Random库的randint方法来生成随机的行标和列标用来随机定位一个单元格。
③定义函数get_possible用行、列、九宫格不可重复的规则筛选出指定单元格满足条件的所有取值并存储在集合中。
# 由三个约束条件剔除数据
def get_possible(self, row, col): bRow, bCol = row // 3, col // 3 # 提取行标为row的行
rowSet = set(self.grids[row]) # 提取列标为col的列
colSet = set(self.grids[:,col]) # 由行标列表取出所在的3*3小九宫格
blockSet = set(self.grids[bRow * 3: bRow * 3 + 3, bCol * 3: bCol * 3 + 3].reshape(9)) # 从possible中剔除所在行、所在列和所在小九宫格里的相同的数字
return self.possibleNums - rowSet - colSet - blockSet④定函数dfs深度优先，遍历数独的所有单元格并通过递归对get_possible函数返回的当前单元格的可能取值进行填入，如果数独无法正确填写，便以回溯的方法回到上一个单元格填入其他的可能值继续执行。
# 深度优先方法解数独
def dfs(self): for row in range(9): for col in range(9): # 从0行0列开始寻找空白格
if self.grids[row, col] == 0: # 用get_possible得到当前空白格可以填入的数值
possible = self.get_possible(row, col) # 深度优先，填入第一个值，递归填入剩下空白格的值
# 如果无法正确填写，就回归上一个刚填的格，重新填入possible里第二值
# 直到所有空白格都正确填入
for value in possible: self.grids[row, col] = value if self.dfs(): return True self.grids[row, col] = 0 return False return True⑤定义lasVegas函数，先随机定位空白单元格，再调用get_possible函数获取可能的取值并随机填入，直到填充够指定的个数(NUM)后输出仅填入指定数量数字的数独盘，同时调用Random函数的sample方法来打乱顺序，增加数独生成的随机性。再调用dfs函数对数独进行求解并输出求解完毕的基础数独终盘。
# 拉斯维加斯算法生成数独
def lasVegas(self, initGivenCount): # initGivenCount为初始给定数字的个数
while initGivenCount: # 用随机行列定位一个单元格
row = random.randint(0, 8) col = random.randint(0, 8) # 选中空白格，且避免再次选中已经填入的单元格
if self.grids[row, col] == 0: # 随机在可能的取值中取一个数，避免初始的宫格中都是1,2,3等数字
value = random.sample(self.get_possible(row, col), 1)[0] self.grids[row, col] = value initGivenCount -= 1 # 先输出填充给定初始个数（initGivenCount）数字的基础数独
self.output_sudo() # 再采用深度优先方法解出数独并更新数据
if self.dfs(): return True else: return False①定义函数checkUnique函数用来判断扣除该单元格后的数独答案是否唯一，如果唯一则可以扣除，如果不唯一则不能扣除。
# 挖洞后判断是否只有唯一的答案
def checkUnique(self, row, col):
for value in range(1, 10):
if self.grids[row, col] != value:
# 假设挖掉这个数字
self.grids[row, col] = 0
# 将挖掉的方块置0后，用get_possible来检查
if value in self.get_possible(row, col):
# 更换一个其他符合规则的数字之后检查是否可以解
# 将除去原本值的其他所有值依次尝试
self.grids[row, col] = value
if self.dfs():
return False
# 上面进行深度优先过程已经改变了self.grids的值，恢复更换这个数字之前的状态，再继续换别的数
self.grids = self.uniqueGrids.copy()
# 已尝试所有其他数字发现无解,即只有唯一解
return True
②定义函数potholing函数实现挖除指定数量单元格，每次均调用函数checkUnique来进行唯一性判断，通过挖除数量的多少得到对应难度的数独题并输出。
# 挖洞出题
def potholing(self, level):
# level表示要挖掉的数字个数
self.uniqueGrids = self.grids.copy()
digged = 0
while digged < level:
row = random.randint(0, 8)
col = random.randint(0, 8)
# 跳过被挖过的格子
if self.uniqueGrids[row, col] == 0:
continue
# 挖掉该格子后能生成唯一的九宫格。如果有就继续挖，如果没有唯一解就不挖这个格子
if self.checkUnique(row, col):
# 保存挖洞后的状态
self.uniqueGrids[row, col] = 0
# 挖完洞后继续挖，直到挖出指定数量的格子
self.grids = self.uniqueGrids.copy()
digged += 1
③重新用dfs深度优先算法对挖除对应数量单元格的数独进行求解.
④格式化输出重新求解后的数独终盘
# 格式化输出数独
def output_sudo(self): for i in range(9): if i % 3 == 0: print(' +-------+-------+--------+') print(' ', end='') for j in range(9): if j in [0, 3, 6]: print("| ", end="") if self.grids[i, j] == 0: print(" ", end=" ") else: print(self.grids[i, j], end=' ') if j == 8: print(" |", end="") print("") print(' +-------+-------+--------+')def main(): NUM=eval(input('\n输入一个数字，程序将以这个个数生成基础数数 独：')) digCount=eval(input('\n输入需要挖掉的数量：')) myShuDu = Sudoku() print('\n生成的基础数独如下：') myShuDu.lasVegas(NUM) print('\n数独答案如下：') myShuDu.output_sudo() # 输出挖洞后的数独题
myShuDu.potholing(digCount) print('\n挖掉要求个数后的数独题如下：') myShuDu.output_sudo() # 重新将挖洞后的数独利用深度优先算法解答
myShuDu.dfs() print('\n重新用深度优先算法计算出的数独答案如下：') myShuDu.output_sudo() if __name__ == '__main__': main()1.程序运行后，在输入框中输入11，即先填入11个数字在空白数独中，再以此进行深度优先求解数独，同时输出初始数独和求解出的数独终盘。空数独填写11个数之后，后面采用深度优先算法成功的概率在99%以上，而且重新回退尝试的次数非常少，运行时间非常短。
程序运行截图如下
2.在第二个输入框输入50，即在求解出来的数独终盘中扣除50个单元格中的数字，并再以此进行深度优先求解数独，同时输出扣除后的数独题目和求解出的数独终盘。经测试，挖55个洞以下生成一个有唯一解的数独可以在极短的时间内运行完毕。
程序运行截图如下
可见由初始数独深度优先求解出的数独终盘与挖洞后深度优先求解出的数独终盘完全一致，运行无误。
本次实验中，通过对生成随机数独问题的研究，加深了对递归和深度优先问题的理解。
根据此算法，普通微机在5ms左右可以随机生成一局任意难度的数独初盘。在生成过程中，尽可能地使用了随机值，除了数独的基本规则，不再受其他因素的制约，这使得生成的初盘，理论上可以随机分布，所以本算法在实际的数独游戏或比赛的出题中，是比较有效的，且对于数独的统计分析工作具有一定的意义。
通过这次实验，我认到学好算法分析与设计要重视实践操作，在实践中可以发现很多问题，以此来提高自己的逻辑思维和解决问题的能力。