闲来有了用 python 解数独的想法,但由于对复杂些的算法仍是一窍不通,最终算是用简单算法实现了出来.
相关简介:
1. 使用的算法很常规,很好理解,有点类似深度优先搜索算法.
2. 解常规难度的数独耗时约 50~150 ms,但对网上的超难数独尚不能短时间内解出. - -0
3. 输入数独数据要么要 input 一行行手输,要么在程序中替换 default_data 数据,总之没有图形界面,输入有点不方便.
后续可能会继续优化性能,也可能改成图形界面~
使用方法:
主要是输入介绍,我设定了两种,游戏开始前可选择方式 "1" 或 "2":
1:直接修改程序中给出的 default_data,数字的修改数字,空处请填 0.
***Method 1: Modify the default sudoku***
***Method 2: Through input method***
Please select the data input method:1 or 2
如下所示(default_data 的初始数独也可以跑的~):
2:input() + for loops,一行行地输入代码,输入一行确定后按回车进入下一行输入,9 行全部输入后还可以让你再次确认下,都 OK 了再开始计算.
default_data = [[1 ,0 ,6 ,2 ,0 ,0 ,0 ,0 ,0 ],
[0 ,0 ,0 ,4 ,0 ,0 ,8 ,2 ,0 ],
[2 ,0 ,0 ,0 ,0 ,5 ,0 ,0 ,0 ],
[0 ,8 ,0 ,0 ,4 ,0 ,0 ,0 ,7 ],
[0 ,0 ,0 ,6 ,0 ,3 ,0 ,0 ,0 ],
[5 ,0 ,0 ,0 ,1 ,0 ,0 ,4 ,0 ],
[0 ,0 ,0 ,9 ,0 ,0 ,0 ,0 ,0 ],
[0 ,3 ,9 ,0 ,0 ,4 ,0 ,0 ,0 ],
[0 ,0 ,0 ,0 ,0 ,2 ,9 ,0 ,5 ]]
如下所示(每一行的数字键用空格间隔开即可):
当你输入完毕会打印你输入的 Sudoku,然后问你是否确认,输入 Y 确认后即可得到答案,N 则重新输入:
***Method 1: Modify the default sudoku***
***Method 2: Through input method***
Please select the data input method:1 or 2
2
Enter 1th line: 1 0 6 2 0 0 0 0 0
Enter 2th line: 0 0 0 4 0 0 8 2 0
Enter 3th line: 2 0 0 0 0 5 0 0 0
Enter 4th line: 0 8 0 0 4 0 0 0 7
Enter 5th line: 0 0 0 6 0 3 0 0 0
Enter 6th line: 5 0 0 0 1 0 0 4 0
Enter 7th line: 0 0 0 9 0 0 0 0 0
Enter 8th line: 0 3 9 0 0 4 0 0 0
Enter 9th line: 0 0 0 0 0 2 9 0 5
原理介绍
Your data:
1 0 6 2 0 0 0 0 0
0 0 0 4 0 0 8 2 0
2 0 0 0 0 5 0 0 0
0 8 0 0 4 0 0 0 7
0 0 0 6 0 3 0 0 0
5 0 0 0 1 0 0 4 0
0 0 0 9 0 0 0 0 0
0 3 9 0 0 4 0 0 0
0 0 0 0 0 2 9 0 5
Confirm? Y or N
主要函数有两个:
judge,用于判断数独矩阵中某一处是否允许填入某个数字,这个比较简单
fill_num,用于将 judge 函数允许的数字填入空处,接着填下一个空,再下一个...(没错,这是一个迭代过程)... 直到某一个空发生 judge 为 False 的情况,额,会 pass 掉;直到所有的空都被填满且 judge 均为 True,则返回填满的 data 矩阵.
def judge(data, x, y, num):
if data[y].count(num) > 0: #行判断
#print('error1')
return False
for col in range(9): #列判断
if data[col][x] == num:
#print('error2')
return False
for a in range(3): #九宫格判断
for b in range(3):
if data[a+3*(y//3)][b+3*(x//3)] == num:
#print('error3')
return False
return True
顺便还要介绍一下 build_data_list 函数:用于初始化,为每个空位建立备选数字列表,如下所示:
为每一个空处都建立一个备选列表,而 fill_num 函数则是在迭代所有的空处,循环其中的备选列表.备选列表是可以在每一步前被筛选掉一部分,从而提高速度的,不过这一部分工作还没想好怎么做.
def build_data_list(data):
data_list = []
for y in range(9):
for x in range(9):
if data[y][x] == 0:
data_list.append([(x, y), [1, 2, 3, 4, 5, 6, 7, 8, 9]]) #列表中有坐标信息以及备选的数字
return data_list
fill_num 函数代码如下:
fill_num 函数中有坑:
def fill_num(data, data_list, start):
if start < len(data_list):
one = data_list[start]
for num in one[1]:
if judge(data, one[0][0], one[0][1], num):
data[one[0][1]][one[0][0]] = num
tem_data = fill_num(data, data_list, start+1) #迭代部分
if tem_data != None:
return tem_data #当迭代返回值非空时才传给上层
data[one[0][1]][one[0][0]] = 0 #当for loops结束时需要执行清零操作
else:
return data
每一处空的循环尝试都能成功,并通向下一处空,直至最后一个空... 这种情况当然是最好啦,这种情况下会一层层返回正确的 data,不会出啥问题.图示如下:
理想情况
但这种猜测式解数独法,总是猜错的情况多.对应的这种情况就是第 n 阶的猜测 judge 为 True,但却不是答案值,而这种错误往往要继续往下猜很多阶才能体现出来,图解如下,这样就会形成两个坑.
日常情况
坑一,当第 n+1 阶的 for loops 执行完都没找到可填的数字时,此时的第 n+1 阶的迭代函数也会返回值(只不过这个值为 None).一旦某一阶函数返回了值,其外部的函数依次返回,后续的猜测就终止了,无法找到正确值(正确值非 None).
因此增加这部分代码,避免某函数 for loops 结束,返回值为 None 时,引起外层函数连续 return,中断操作.
if tem_data != None:
return tem_data #当迭代返回值非空时才传给上层
坑二,解决返回值问题是其一,其二是尽管对返回值设了检查,return 有了保障,但是毕竟某一阶或多阶的 for loops 已经错误执行,导致 data 被多次错误赋值:
解决方案为,一旦 for loops 能完整执行,表明前面一定填错了,因此要将每一个错误的填数清零:
if judge(data, one[0][0], one[0][1], num): #judge为True就允许赋值
data[one[0][1]][one[0][0]] = num
data[one[0][1]][one[0][0]] = 0 #当for loops结束时需要执行清零操作
来源: http://www.jianshu.com/p/fcd35b68c1e3