python實(shí)現(xiàn)自動(dòng)解數(shù)獨(dú)小程序

更新時(shí)間：2019年01月21日 11:16:48 作者：wu_xying

這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)自動(dòng)解數(shù)獨(dú)小程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

跟朋友最近聊起來(lái)數(shù)獨(dú)游戲，突發(fā)奇想使用python編寫一個(gè)自動(dòng)計(jì)算數(shù)獨(dú)解的小程序。

數(shù)獨(dú)的規(guī)則不再過(guò)多闡述，在此描述一下程序的主要思路：

（當(dāng)前程序只針對(duì)于簡(jiǎn)單的數(shù)獨(dú)，更復(fù)雜的還待深入挖掘）

1.計(jì)算當(dāng)前每個(gè)空格可能的取值集合，并將空格順序值對(duì)應(yīng)取值集合置于字典中；

2.對(duì)取值集合位數(shù)為1，即空格處為單一取值的進(jìn)行賦值，（填入動(dòng)作），重復(fù)1刷新字典直到字典為空位置；

當(dāng)前實(shí)現(xiàn)如下：

1.將數(shù)獨(dú)輸入列表中，并定義函數(shù)count_candinate_number(j)根據(jù)數(shù)獨(dú)規(guī)則計(jì)算每一個(gè)為0的位置的當(dāng)前可能取值：

#編輯數(shù)獨(dú)題目，將題目輸入列表中
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])
 
#返回當(dāng)前數(shù)獨(dú)為0的空格中所有可能取值
def count_candidate_number(j):
 exist_all_number = [] #當(dāng)前橫豎大方格內(nèi)所有出現(xiàn)的數(shù)字集
 candidate_number = [] #該方格內(nèi)所有的數(shù)字候選集
 SD_Row = int(j) // 9 #行
 SD_Column = int(j) % 9 #列
 
 #用迭代器寫
 exist_all_number_part1 = [question[i+SD_Row*9] for i in range(9)] #橫-出現(xiàn)的所有數(shù)字集
 exist_all_number_part2 = [question[i*9+SD_Column] for i in range(9)] #豎-出現(xiàn)的所有數(shù)字集
 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)] #大方塊-出現(xiàn)的所有數(shù)字集
 exist_all_number = list(set(exist_all_number_part1+exist_all_number_part2+exist_all_number_part3))  #對(duì)出現(xiàn)所有的數(shù)字集組合及去重
 # print(exist_all_number)
 
 #用循環(huán)寫
 # 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] #對(duì)可能取值進(jìn)行迭代輸出
 
 #用循環(huán)寫
 # for i in range(1,10):
 # if i not in exist_all_number:
 #  candidate_number.append(i)
 # print(candidate_number)
 
 return candidate_number

2.定義函數(shù)求解對(duì)應(yīng)每個(gè)為0的位置的可能求解，并將位置信息與可能求解以鍵-鍵值的形式存儲(chǔ)于字典中：

#對(duì)數(shù)組中每個(gè)為0的空格列出所有可能的取值數(shù)集，并放置于字典中
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.對(duì)每一個(gè)位置的可能求解進(jìn)行判斷，若可能解只有一個(gè)，則填入該解，循環(huán)直至數(shù)獨(dú)求解完成

def main_count():
 answer_sudoku = question
 candidate_number_dic = {}
 while True:
 candidate_number_dic = all_possible_candidate_number() #在每次循環(huán)之前刷當(dāng)前每個(gè)為0的空格，所有的取值集合
 if candidate_number_dic == {}:    #如果為空，則證明沒有為0的空格，則為求解
  answer_sudoku = question    #對(duì)answer_sudoku賦值，并打印
  print("已求解",answer_sudoku)
  break
 else:
  for eachkey,eachValue in candidate_number_dic.items(): #對(duì)字典中位數(shù)為1的取值集合，既確定該數(shù)字變?yōu)楫?dāng)前應(yīng)取值
  if len(eachValue) == 1:
   answer_sudoku[eachkey] = eachValue[0]
   print(eachkey,eachValue[0])   #打印對(duì)應(yīng)鍵值及對(duì)應(yīng)數(shù)值
  pass
 
if __name__ == '__main__':
 main_count()

程序運(yùn)行結(jié)果：

D:\pythonwokr\venv\Scripts\python.exe D:/pythonwokr/數(shù)獨(dú).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

程序到這里就結(jié)束了，下一步拓展是對(duì)于若不存在單獨(dú)唯一解的情況，待續(xù)。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: