python 解數獨
一、數獨規則：
\qquad數獨共有九九八十一個小方格，要求每一行、每一列的小方格都包含數字1-9,且不能重複；将這個方格平均分成9個3 ∗
*∗ 3的方格，每個方格的數字也必須包含1-9，且不能重複。
二、解題思路
\qquad 1、擷取每一個空缺方格的坐标；
\qquad 2、周遊每一個空缺方格的坐标進行取可能的值，周遊從1-9進行取值。
\qquad(1)若滿足數字不包含在空缺坐标的所在行和所在列以及3 ∗
*∗ 3方格内，則停止周遊，将該數字指派于空缺坐标内；
\qquad(2)、若1-9都包含在空缺坐标的所在行和所在列以及3 ∗
*∗ 3方格内，則傳回上一步，從比上一步的取值大1開始周遊取值。
三、代碼
import pandas as pd
import time
class Sudoku():
def __init__(self,data):
self.data = data
# 擷取空缺坐标
self.origin_list = [[i,j] for i in range(9) for j in range(9) if data.iloc[i,j]==0]
# 判斷小格子屬于哪個小正方形，并讀取該小正方形的資料
def Check_in(self,i,j):
a = i//3
b = j//3
data = self.data.iloc[a*3:a*3+3,b*3:b*3+3]
data = data.values.flatten()
return data
# 判斷小格子數字的值
def Check_Value(self,num,i,j):
for a in range(num,10):
if (a not in list(self.data.iloc[i,:]))&(a not in list(self.data.iloc[:,j]))&(a not in self.Check_in(i,j)) :
b=a
else:
b=0
if b!=0:
break
return b
# 傳回上一步
def Come_Back(self,i):
i = i - 1
while True:
# 擷取上一步的取值，并對取值進行加1
num = self.data.iloc[self.origin_list[i][0],self.origin_list[i][1]]+1
# 若上一步取值為9，則對上一步的格子指派0，然後再往前退一步
if num >9:
self.data.iloc[self.origin_list[i][0],self.origin_list[i][1]] = 0
i= i-1
# 若傳回上一步周遊後沒有數值可取，則對上一步的格子指派0，然後再傳回上一步
elif self.Check_Value(num,self.origin_list[i][0],self.origin_list[i][1])==0:
self.data.iloc[self.origin_list[i][0], self.origin_list[i][1]] = 0
i = i - 1
# 若傳回上一步周遊可以取得滿足條件的值，則計算出該值，并退出循環
else:
a = self.Check_Value(num,self.origin_list[i][0],self.origin_list[i][1])
break
c = [a,i]
return c
# 判斷每個格子的值
def Value_In(self):
i = 0
num = 1
while True:
# 對空缺值進行取值
a = self.Check_Value(num, self.origin_list[i][0], self.origin_list[i][1])
# 若該格子能取到滿足條件的值，則對該格子進行指派，并進入下一個空缺格子，取值函數的取值範圍是0-9，則大于0即為滿足條件
if a >0:
self.data.iloc[self.origin_list[i][0],self.origin_list[i][1]] = a
i+=1
# 若該格子無法取得滿足條件的值，則傳回上一步。
else:
c = self.Come_Back(i)
i = c[1]
self.data.iloc[self.origin_list[i][0],self.origin_list[i][1]] = c[0]
i=i+1
# 當所有空缺格子都填滿了則退出循環
if i>=len(self.origin_list):
break
return
def main():
# 讀取資料
data = pd.read_excel('./sudoku.xlsx', header = None, names = [str(i) for i in range(9)])
# 對空缺的數值指派為0
data = data.fillna(0)
# 對所有的資料類型改為整數型
data = data.astype(int)
start = time.clock()
sudoku = Sudoku(data)
sudoku.Value_In()
end = time.clock()
print(sudoku.data)
print(end-start)
if __name__ == "__main__":
main()
原文連結:https://blog.csdn.net/vgrant/article/details/108974369