定义
数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
算法思想
启发式搜索算法，针对摒弃法的改进。
先算出所有空格的候选数，然后找到候选数个数最少的位置开始搜索。如果不满足则回退。
代码
# -*- coding: utf-8 -*-# @Time : /5/2 14:58# @Author : kunkun# @File : algorithm3.py# ------------------------------# 启发式搜索算法，针对算法2的改进。# 先算出所有空格的候选数，然后找到候选数个数最少的位置开始搜索。import numpy as npsudoku = np.zeros((9, 9), dtype=np.int32) # 存储数独矩阵def cal_blank():# 计算空格的个数count = 0coord = []for i in range(9):for j in range(9):if sudoku[i][j] == 0:coord_tmp = [i, j] # 记录坐标coord.append(coord_tmp)count += 1return count, coorddef blank_candidate(coord, count):candidate_list = [] # 保存没哟个空格位置的候选列表for i in range(count):num = [1, 2, 3, 4, 5, 6, 7, 8, 9]# 取坐标x = coord[i][0]y = coord[i][1]# 找九宫格位置start_row = x // 3start_col = y // 3# 行去重复数字for j in range(9):if sudoku[x][j] in num:num.remove(sudoku[x][j])# 列去重复数字for j in range(9):if sudoku[j][y] in num:num.remove(sudoku[j][y])# 九宫格去重复数字for j in range(start_row * 3, start_row * 3 + 3):for k in range(start_col * 3, start_col * 3 + 3):if sudoku[j][k] in num:num.remove(sudoku[j][k])candidate_list.append(num)return candidate_listdef min_index(candidate_list, coord, count):# 找到最小候选个数的位置candidate_len = []for i in range(count):lens = len(candidate_list[i])candidate_len.append(lens)min_len = min(candidate_len) # 最小候选个数index = candidate_len.index(min_len) # 最小候选个数索引return min_len, index, coord[index]def search_algorithm():# 计算需要填空的坐标及个数:坐标列表:coord,个数:countcount, coord = cal_blank()total_count = 0 # 记录总的迭代次数# 弹出的候选数列表pop_candi_list = []# 弹出坐标列表pop_coord_list = []while count:# 计算空白位置的候补列表candidate_tmp = blank_candidate(coord, count)# 计算最小候补个数的位置min_len, index, min_coord = min_index(candidate_tmp, coord, count)# print(total_count, candidate_tmp[index], min_coord)if min_len == 0:while len(pop_candi_list[-1]) == 0:# 上一个空格的坐标x = pop_coord_list[-1][0]y = pop_coord_list[-1][1]# 还原当前节点的值sudoku[x][y] = 0count = count + 1coord.append(pop_coord_list[-1])# 删除当前节点坐标及侯选数列表del pop_coord_list[-1]del pop_candi_list[-1]# 上一个空格位置重新填数x = pop_coord_list[-1][0]y = pop_coord_list[-1][1]sudoku[x][y] = pop_candi_list[-1][0]del pop_candi_list[-1][0]total_count += 1else:# 更改min_coord处的值x = min_coord[0]y = min_coord[1]sudoku[x][y] = candidate_tmp[index][0]# 取出min_coord位置处的候选数删除候选数的第一项后放到弹出来的候选数列表中tem_list = candidate_tmp.pop(index)del tem_list[0]pop_candi_list.append(tem_list)# 取出min_coord的位置放到弹出来的坐标列表中tem_coord = coord.pop(index)pop_coord_list.append(tem_coord)count = count - 1total_count += 1print(f'共迭代{total_count}次')if __name__ == '__main__':sudoku = [[0, 0, 5, 3, 0, 0, 0, 0, 0],[8, 0, 0, 0, 0, 0, 0, 2, 0],[0, 7, 0, 0, 1, 0, 5, 0, 0],[4, 0, 0, 0, 0, 5, 3, 0, 0],[0, 1, 0, 0, 7, 0, 0, 0, 6],[0, 0, 3, 2, 0, 0, 0, 8, 0],[0, 6, 0, 5, 0, 0, 0, 0, 9],[0, 0, 4, 0, 0, 0, 0, 3, 0],[0, 0, 0, 0, 0, 9, 7, 0, 0]]search_algorithm()for i in range(9):print(sudoku[i])
总结
针对摒弃法的改进，考虑了一种启发式的搜索算法，核心思想仍然是模拟人的解题思路。为了跳出传统方法，下面将尝试运用一些新的方法解决数独问题。
