定义
数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
算法思想
遗传算法，具体思想感兴趣的可以百度下，这里主要讲解每个部分如何设置。
代码实现：
# -*- coding: utf-8 -*-
# @Time : 2022/5/4 10:01
# @Author : kunkun
# @File : algorithm4_impr.py
# ------------------------------
# 遗传算法改进
import random
import time
rows = 'ABCDEFGHI' # 行标号
cols = '123456789' # 列标号
"""
对于每一个空，除去自己
可填列 col = 8 ，可填行 row = 8， block = 3，总数 8+8+3=19
一共有81个空
最大分数 score = 19 * 81 = 1539
"""
max_score = 200 # 1539 # 适应度评分？c
var_rate = 0.1 # 变异率
quan = 1000 # 种群成员个数
times = 500 # 遗传最大代数
total_score = []
"""
准备部分
"""
# 把行列链接，给每个格子编号
def cross(a, b):
return [s + t for s in a for t in b]
# 格子编号
boxes = cross(rows, cols)
# boxes = ['A1', 'A2', 'A3', 'A4', 'A5', 'A6'...]
# 每一行、列、九宫格的标号
row_units = [cross(r, cols) for r in rows]
# row_units = [['A1', 'A2', 'A3', 'A4', 'A5', 'A6',...],...]
column_units = [cross(rows, c) for c in cols]
# colum_units = [['A1', 'B1', 'C1', 'D1', 'E1', 'F1',...],...]
square_units = [cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')]
# [['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2',...],...]
# 链接
unitlist = row_units + column_units + square_units
# 每一个空所在的行列九宫格元素
units = dict((s, [u for u in unitlist if s in u]) for s in boxes)
# units = {'A1': [['A1', 'A2', 'A3', 'A4', 'A5', 'A6',...], ['A1', 'B1', 'C1', 'D1', 'E1', 'F1',...], ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2',...]],...]
# 每一个空的需要不重复的位置
peers = dict((s, set(sum(units[s], [])) - set([s])) for s in boxes)
# peers = {'A1': {'A6', 'C1', 'C2', 'D1', 'E1', 'A2', 'A3', 'B1', 'F1', 'B2', 'A5', 'A4',...},...]
# 不能和A1重复的位置
"""
打印部分
"""
# 输入：sudoku 字典
# 输出：打印结果
def display(values):
width = 3
line = '+'.join(['-' * (width * 3)] * 3)
for r in rows:
print(''.join(str(values[r + c]).center(width) + ('|' if c in '36' else '')
for c in cols))
if r in 'CF':
print(line)
return
# Input: sudoku string
# Output: sudoku dict
# Keys: 'A1/A2...'
# Values: '1-9' or "."
# return {'A1': '1', 'A2': '-', 'A3': '-', 'A4': '3', 'A5': '-',...]
def grid_values(grid):
chars = []
digits = '123456789'
for c in grid:
if c in digits:
chars.append(c)
if c == '.':
chars.append("-")
# assert len(chars) == 81
return dict(zip(boxes, chars))
"""
种群制造部分
"""
# Input: sudoku string
# Output: sudoku dict.
# return {'A1': 1, 'A2': 5, 'A3': 4, 'A4': 3, 'A5': 5, 'A6': 6, 'B1': 2, 'B2': 5, ...]
def combine_to_dict(combine):
chars = []
for c in combine:
chars.append(c)
# assert len(chars) == 81
return dict(zip(boxes, chars))
# 获取可填值
# input: sudoku dict, element
# output: available digit set
def get_available_digit(grid_dic, element):
ps = peers[element]
num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in ps:
tmp = grid_dic[i]
if tmp != '-':
if int(tmp) in num:
num.remove(int(tmp))
return num
# 根据在grid中的位置获取字母索引
# input: index
# output: A1/A2...
def get_index(index):
x = index // 9
y = index % 9
return chr(ord('A') + x) + str(y + 1)
# input: puzzle string.
# output: random string for empty slots.
# 对可填位置随机赋值，生成个体
def random_generate(grid, grid_dic):
row = 9
col = 9
poss = []
for r in range(0, row):
for c in range(0, col):
index = r * 9 + c
if grid[index] == ".":
ele = get_index(index)
num = get_available_digit(grid_dic, ele)
poss.append(num[random.randint(0, len(num) - 1)])
return poss
# input: sudoku string, 对空值可能的结果 poss
# output: 一个完整的sudoku.(没有 '.', 全部是1-9的数字.)
# 把随机填的数放回sudoku中
def combination(grid, poss):
combine = []
poss_counter = 0
for c in range(0, len(grid)):
if grid[c] != '.':
combine.append(int(grid[c]))
else:
# try:
# combine.append(poss[poss_counter])
# except IndexError:
# print(poss_counter)
combine.append(poss[poss_counter])
poss_counter += 1
return combine
# input: sudoku（不带.） dict.
# output: 得分 score，越大得分越不好.
# 计算有多少重复
def evaluation(dic):
score = 0
for elm in dic.keys():
for peer in peers[elm]:
if dic[elm] == dic[peer]:
score += 1
return score
# 包含所有个体的种群.
# inout: sudoku string(grid).
# output: 生成第一代种群个体（随机）.
def population(grid, grid_dic):
poss = []
for c in range(0, quan):
poss.append(random_generate(grid, grid_dic))
return poss
"""
遗传部分
"""
# 随机选择两个父类交换
def choose_parents(p1, p2):
finish = False
while finish == False:
rand_p1_number = random.randint(0, quan - 1)
p2_flag = False
temp = random.randint(0, quan - 1)
# 保证p1，p2不同
while p2_flag == False:
temp = random.randint(0, quan - 1)
if temp != rand_p1_number:
p2_flag = True
finish = True
rand_p2_number = temp
p1 = rand_p1_number
p2 = rand_p2_number
return p1, p2
# 通过交叉和变异得到子代.
# input: 2 parents, p1, p2(poss)
# ouput: 2 sons, s1, s2(poss)
# 交叉和变异
def generate(p1, p2, len1, grid_dic):
# 随机选择交叉位点
pos1 = random.randint(0, len1 - 1)
pos2 = random.randint(1, len1)
while pos2 == pos1:
pos2 = random.randint(1, len1)
# 交叉，位点之间的部分交叉
for var in range(pos1, pos2):
p1[var], p2[var] = p2[var], p1[var]
# 对交叉后的p1，p2进行变异，位点之间的位置随机变异
for var in range(pos1, pos2):
x1 = random.random()
if x1 < var_rate:
ele = get_index(var)
num = get_available_digit(grid_dic, ele)
p1[var] = num[random.randint(0, len(num) - 1)]
x2 = random.random()
if x2 < var_rate:
ele = get_index(var)
num = get_available_digit(grid_dic, ele)
p2[var] = num[random.randint(0, len(num) - 1)]
# variation finished.
return p1, p2
# 算法流程
def process(grid, poss, new_poss, grid_dic):
score = [] # 得分列表
prob = [] # 遗传概率列表
s1 = []
s2 = []
count = 0
for each in poss: # 对每一个个体计算得分和遗传概率得分
sco = evaluation(combine_to_dict(combination(grid, each)))
# print(sco)
score.append(sco)
prob.append(round(sco / max_score, 3))
while count < quan // 2:
flag = False
while not flag:
p1 = 0
p2 = 0
(p1, p2) = choose_parents(p1, p2) # 随机选择两个父代
# clone
temp1 = poss[p1][:]
temp2 = poss[p2][:]
if prob[p1] * prob[p2] < random.random(): # 两个父代的概率得分越小越容易遗传
(s1, s2) = generate(temp1, temp2, len(poss[p1]), grid_dic)
count += 1
flag = True
new_poss.append(s1)
new_poss.append(s2)
"""
选择得分小的个体成为下一代（按概率）
"""
double_poss = []
for each in poss:
double_poss.append(each)
for each in new_poss:
double_poss.append(each)
double_score = []
for each in double_poss:
sco = evaluation(combine_to_dict(combination(grid, each)))
double_score.append(sco)
i = 0
while i < quan: # 取得分最小的个体放入下一代（按概率）
min_sco = min(double_score)
ind = double_score.index(min_sco)
# ind = random.randint(0, len(double_poss) - 1)
# print(double_score)
sco_tmp = double_score[ind]
if sco_tmp < random.randint(0, max_score):
double_score[ind] = max_score # 找到最小得分位置后，把他变成最大得分
# print(sco_tmp)
poss[i] = double_poss[ind]
i += 1
new_score = []
for each in poss:
sco = evaluation(combine_to_dict(combination(grid, each)))
new_score.append(sco)
return poss, new_poss
# 测试
def test(grid, poss):
solution = []
scores = []
for each in poss:
test_sco = evaluation(combine_to_dict(combination(grid, each)))
scores.append(test_sco)
# if each:
# print('===============================')
# display(combine_to_dict(combination(grid, each)))
# print('===============================')
if test_sco == 0: # 找到可行解
solution = each
total_score.append(scores)
break
total_score.append(scores)
if solution:
return True, solution
else:
return False, solution
"""
执行程序
"""
# 获取最低得分
def get_min_score():
mini = max_score
for i in total_score:
mini = min(i) if mini > min(i) else mini
return mini
def run(grid, time, grid_dic):
solu = []
it = 0
poss = population(grid, grid_dic)
new_poss = []
while it < time:
print(f'第{it + 1}代开始遗传...')
(poss, new_poss) = process(grid, poss, new_poss, grid_dic)
(flag, solu) = test(grid, poss)
print(f'第{it + 1}代结束，当前最小分数为:{get_min_score()}')
it += 1
if flag:
break
file_path = 'result.txt'
with open(file_path, mode='w', encoding='utf-8') as file_obj:
for i in total_score:
for j in i:
file_obj.write(str(j) + ' ')
file_obj.write('n')
if it == time:
print("failed to get a solution in " + str(time) + " times")
else:
print("Total generate times: " + str(it))
print("One solution is:")
display(combine_to_dict(combination(grid, solu)))
"""
主函数
"""
def genaretion_grid(sudoku):
str1 = ''
for i in range(9):
for j in sudoku[i]:
if j != 0:
str1 += str(j)
else:
str1 += '.'
return str1
if __name__ == '__main__':
start = time.perf_counter()
# 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]]
# sudoku = [[6, 3, 2, 0, 0, 4, 7, 8, 0],
# [9, 0, 5, 0, 8, 2, 6, 3, 1],
# [8, 0, 0, 0, 6, 3, 0, 0, 2],
# [0, 6, 1, 3, 0, 7, 2, 0, 0],
# [0, 9, 0, 8, 0, 6, 0, 1, 0],
# [0, 0, 4, 2, 0, 5, 9, 6, 0],
# [1, 0, 0, 4, 2, 0, 0, 0, 6],
# [3, 2, 6, 5, 7, 0, 8, 0, 4],
# [0, 7, 9, 6, 0, 0, 1, 2, 5]]
sudoku = [[0, 8, 5, 0, 0, 0, 2, 1, 0],
[0, 9, 4, 0, 1, 2, 0, 0, 3],
[0, 0, 0, 3, 0, 0, 7, 0, 4],
[5, 0, 3, 4, 0, 9, 0, 0, 0],
[0, 4, 0, 2, 0, 6, 0, 3, 0],
[0, 0, 0, 1, 0, 3, 9, 0, 7],
[6, 0, 8, 0, 0, 5, 0, 0, 0],
[1, 0, 0, 8, 4, 0, 3, 6, 0],
[0, 2, 7, 0, 0, 0, 8, 9, 0]]
grid = genaretion_grid(sudoku)
print("Sudoku puzzle is:")
dic = grid_values(grid)
display(dic)
run(grid, times, dic)
end = time.perf_counter()
print('Running time: {:.3f} ms'.format((end - start) * 1000))
运行截图
遗传各代统计数据：
总结
代码注释还算比较完整，写的有一点点乱，因为期间也改了很多版本，如果重新写肯定会更好，但作者比较懒，就交给大家了。有什么疑问欢迎讨论。
