跟朋友最近聊起来数独游戏,突发奇想使用python编写一个自动计算数独解的小程序。
数独的规则不再过多阐述,在此描述一下程序的主要思路:
(当前程序只针对于简单的数独,更复杂的还待深入挖掘)
1.计算当前每个空格可能的取值集合,并将空格顺序值对应取值集合置于字典中;
2.对取值集合位数为1,即空格处为单一取值的进行赋值,(填入动作),重复1刷新字典直到字典为空位置;
当前实现如下:
1.将数独输入列表中,并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置的当前可能取值:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#编辑数独题目,将题目输入列表中
question = [ 6 , 0 , 7 , 0 , 0 , 0 , 9 , 0 , 3 ,
0 , 0 , 8 , 0 , 0 , 7 , 0 , 0 , 0 ,
3 , 0 , 0 , 0 , 8 , 2 , 0 , 7 , 5 ,
0 , 1 , 2 , 3 , 0 , 5 , 0 , 0 , 0 ,
0 , 0 , 6 , 0 , 0 , 0 , 5 , 0 , 0 ,
0 , 0 , 0 , 4 , 0 , 6 , 7 , 1 , 0 ,
2 , 6 , 0 , 7 , 4 , 0 , 0 , 0 , 8 ,
0 , 0 , 0 , 8 , 0 , 0 , 6 , 0 , 0 ,
7 , 0 , 5 , 0 , 0 , 0 , 1 , 0 , 9 ]
# print(question[0])
#返回当前数独为0的空格中所有可能取值
def count_candidate_number(j):
exist_all_number = [] #当前横竖大方格内所有出现的数字集
candidate_number = [] #该方格内所有的数字候选集
SD_Row = int (j) / / 9 #行
SD_Column = int (j) % 9 #列
#用迭代器写
exist_all_number_part1 = [question[i + SD_Row * 9 ] for i in range ( 9 )] #横-出现的所有数字集
exist_all_number_part2 = [question[i * 9 + SD_Column] for i in range ( 9 )] #竖-出现的所有数字集
exist_all_number_part3 = [question[((j / / 9 ) / / 3 ) * 27 + ((j % 9 ) / / 3 ) * 3 + i] for i in range ( 3 )] + [question[((j / / 9 ) / / 3 ) * 27 + ((j % 9 ) / / 3 ) * 3 + 9 + i] for i in range ( 3 )] + [question[((j / / 9 ) / / 3 ) * 27 + ((j % 9 ) / / 3 ) * 3 + 18 + i] for i in range ( 3 )] #大方块-出现的所有数字集
exist_all_number = list ( set (exist_all_number_part1 + exist_all_number_part2 + exist_all_number_part3)) #对出现所有的数字集组合及去重
# print(exist_all_number)
#用循环写
# for i in range(9):
# if question[i+SD_Row*9] not in exist_all_number:
# exist_all_number.append(question[i+SD_Row*9])
# if question[i*9 + SD_Cloumn] not in exist_all_number:
# exist_all_number.append(question[i*9 + SD_Cloumn])
# # print(exist_all_number)
#迭代器写
candidate_number = [i for i in range ( 1 , 10 ) if i not in exist_all_number] #对可能取值进行迭代输出
#用循环写
# for i in range(1,10):
# if i not in exist_all_number:
# candidate_number.append(i)
# print(candidate_number)
return candidate_number
|
2.定义函数求解对应每个为0的位置的可能求解,并将位置信息与可能求解以键-键值的形式存储于字典中:
1
2
3
4
5
|
#对数组中每个为0的空格列出所有可能的取值数集,并放置于字典中
def all_possible_candidate_number():
all_possible_candidate_number = {i:count_candidate_number(i) for i in range ( 81 ) if question[i] = = 0 }
return all_possible_candidate_number
# print(all_possible_candidate_number)
|
3.对每一个位置的可能求解进行判断,若可能解只有一个,则填入该解,循环直至数独求解完成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def main_count():
answer_sudoku = question
candidate_number_dic = {}
while True :
candidate_number_dic = all_possible_candidate_number() #在每次循环之前刷当前每个为0的空格,所有的取值集合
if candidate_number_dic = = {}: #如果为空,则证明没有为0的空格,则为求解
answer_sudoku = question #对answer_sudoku赋值,并打印
print ( "已求解" ,answer_sudoku)
break
else :
for eachkey,eachValue in candidate_number_dic.items(): #对字典中位数为1的取值集合,既确定该数字变为当前应取值
if len (eachValue) = = 1 :
answer_sudoku[eachkey] = eachValue[ 0 ]
print (eachkey,eachValue[ 0 ]) #打印对应键值及对应数值
pass
if __name__ = = '__main__' :
main_count()
|
程序运行结果:
1
2
3
4
|
D:\pythonwokr\venv\Scripts\python.exe D: / pythonwokr / 数独.py
已求解 [ 6 , 2 , 7 , 5 , 1 , 4 , 9 , 8 , 3 , 5 , 4 , 8 , 9 , 3 , 7 , 2 , 6 , 1 , 3 , 9 , 1 , 6 , 8 , 2 , 4 , 7 , 5 , 4 , 1 , 2 , 3 , 7 , 5 , 8 , 9 , 6 , 9 , 7 , 6 , 1 , 2 , 8 , 5 , 3 , 4 , 8 , 5 , 3 , 4 , 9 , 6 , 7 , 1 , 2 , 2 , 6 , 9 , 7 , 4 , 1 , 3 , 5 , 8 , 1 , 3 , 4 , 8 , 5 , 9 , 6 , 2 , 7 , 7 , 8 , 5 , 2 , 6 , 3 , 1 , 4 , 9 ]
Process finished with exit code 0
|
程序到这里就结束了,下一步拓展是对于若不存在单独唯一解的情况,待续。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/wu_xying/article/details/82891913