python實現自動解數獨小程序

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

這篇文章主要為大家詳細介紹了python實現自動解數獨小程序，具有一定的參考價值，感興趣的小伙伴們可以參考一下

跟朋友最近聊起來數獨游戲，突發(fā)奇想使用python編寫一個自動計算數獨解的小程序。

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

（當前程序只針對于簡單的數獨，更復雜的還待深入挖掘）

1.計算當前每個空格可能的取值集合，并將空格順序值對應取值集合置于字典中；

2.對取值集合位數為1，即空格處為單一取值的進行賦值，（填入動作），重復1刷新字典直到字典為空位置；

當前實現如下：

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

#編輯數獨題目，將題目輸入列表中
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)
 
 #用循環(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] #對可能取值進行迭代輸出
 
 #用循環(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.定義函數求解對應每個為0的位置的可能求解，并將位置信息與可能求解以鍵-鍵值的形式存儲于字典中：

#對數組中每個為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.對每一個位置的可能求解進行判斷，若可能解只有一個，則填入該解，循環(huán)直至數獨求解完成

def main_count():
 answer_sudoku = question
 candidate_number_dic = {}
 while True:
 candidate_number_dic = all_possible_candidate_number() #在每次循環(huán)之前刷當前每個為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的取值集合，既確定該數字變?yōu)楫斍皯≈?
  if len(eachValue) == 1:
   answer_sudoku[eachkey] = eachValue[0]
   print(eachkey,eachValue[0])   #打印對應鍵值及對應數值
  pass
 
if __name__ == '__main__':
 main_count()

程序運行結果：

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

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

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: