|
python求解数独
最近突然对数独感兴趣，于是用python写了一个求解脚本。
求解算法思路
１．建立初始化数独，我使用numpy模块来建立一个矩阵，也可以直接使用python的列表 ２．计算当前的空缺位置以及该位置可以填入的数据 ３．找到最优位置（数据最少的坐标） ４．循环填入数据，知道某个位置的数据为空时，则回溯到上一个坐标，重新填入数据
代码如下
#!/usr/bin/python3
# coding=utf-8
# Author : Fan Liu
import numpy as np
import time
def col_hang(mat,i,el):
'''
判断一行是否重复
'''
if el in mat[i,:]:
return False
return True
def col_lie(mat,j,el):
'''
判断一列是否重复
'''
if el in mat[:,j]:
return False
return True
def col_fang(mat,i,j,el):
'''
判断一个３×３的矩阵是否重复
'''
i_start=i-i%3
j_start=j-j%3
fang=[]
for m in range(i_start,i_start+3):
for n in range(j_start,j_start+3):
fang.append(mat[m,n])
if el in fang:
return False
return True
def init():
'''
初始化数据
建立第一个副本
'''
mat=np.array([[0,0,2,7,0,0,0,0,0],
[0,0,0,0,1,0,8,0,9],
[0,5,0,0,0,2,0,6,0],
[0,6,0,8,0,0,9,0,4],
[1,0,0,0,0,0,0,0,0],
[0,3,0,6,0,0,7,0,1],
[0,1,0,0,0,3,0,7,0],
[0,0,0,0,7,0,5,0,6],
[0,0,8,9,0,0,0,0,0]])
copy={}
copy[0]=mat.copy()
return mat,copy
def pos_zero(mat):
'''
计算当前数独空缺位置坐标
'''
li=[]
for i in range(9):
for j in range(9):
if mat[i,j]==0:
li.append((i,j))
return li
def pos_value(li,mat):
'''
计算每个空缺位置的可填的数据
储存为一个列表
'''
el={}
for pos in li:
i,j=pos
el[pos]=[]
for num in range(1,10):
if col_hang(mat,i,num) & col_lie(mat,j,num) & col_fang(mat,i,j,num):
el[pos].append(num)
else:
pass
return el
def sort_value(el):
'''
对空缺位置的数据长度进行排序
返回长度最小的位置和数据列表
'''
li_value=[]
pos_value=[]
for pos in el:
li_value.append(len(el[pos]))
pos_value.append(pos)
index=li_value.index(min(li_value))
return pos_value[index],el[pos_value[index]]
def main():
mat,copy=init()
back_value={} #储存每个空缺位置填过的数据
max_index=pos_zero(mat)
for pos in max_index:
back_value[pos]=[]
index=0 #结束的索引，当其等于空缺位置的个数时结束
n=0 #循环次数
while index 0: #可填数据非空时，继续下一个坐标填值
m[pos]=value[0]
print(pos,'set:',value[0])
back_value[pos].append(value[0])
index+=1
n+=1
copy[index]=m
elif len(value)==0: #可填数据为空时，回溯到上一个坐标
del copy[index]
print('return')
back_value[pos]=[]
index-=1
n+=1
else: #当index |