前幾天和隔壁鄰居玩斗地主被發(fā)現(xiàn)了，牌被沒收了，斗地主是斗不了了，但我還想和鄰居玩耍。如果你還想斗斗地主，戳：趁老王不在，和隔壁鄰居斗斗地主，比比大小
<https://www.cnblogs.com/moonhmily/p/11306668.html>

想破腦袋終于讓我想到一個(gè)游戲，數(shù)獨(dú)！什么叫數(shù)獨(dú)？數(shù)獨(dú)就是可以讓我趁老王不在的時(shí)候和隔壁鄰居一起玩耍的游戲！



數(shù)獨(dú)的規(guī)則

1、數(shù)字 1-9 在每一行只能出現(xiàn)一次。

2、數(shù)字 1-9 在每一列只能出現(xiàn)一次。

3、數(shù)字 1-9 在每一個(gè) 3x3 宮內(nèi)只能出現(xiàn)一次。3x3 的宮內(nèi)為A1-C3,A4-C6,A7-C9,D1-F3,D4-F6,D7-F9...

數(shù)獨(dú)題目示例



大致思路

1、數(shù)獨(dú)我們使用一個(gè)二維列表存儲(chǔ),沒有值的位置我們使用''空字符竄占位。（二維數(shù)組）


2、得到每一個(gè)3*3的宮內(nèi),每一行，每一列已有的數(shù)據(jù)，然后存放起來。3、得到所有的空缺位置，再遍歷空缺位置，嘗試放置數(shù)據(jù)，然后進(jìn)行判斷，如果滿足條件安繼續(xù)放置下一個(gè)。以此類推，在途中有不滿足條件的情況，就進(jìn)行回溯，返回上一次滿足條件的情況，在進(jìn)行另一次嘗試。



演示環(huán)境

* 操作系統(tǒng)：windows10
* python版本：python 3.7
* 代碼編輯器：pycharm 2018.2
具體代碼

1、首選我們創(chuàng)建一個(gè)類SudoKu。編寫構(gòu)造函數(shù)。
class SudoKu(): def __init__(self,sudo_ku_data): # 判斷傳入的數(shù)獨(dú)是否滿足格式 if not
isinstance(sudo_ku_data,list): raise TypeError(f'sudo_ku_data params must a
list, but {sudo_ku_data} is a {type(sudo_ku_data)}') if len(sudo_ku_data) != 9
or len(sudo_ku_data[0]) != 9: raise TypeError(f'sudo_ku_data params must a 9*9
list, but {sudo_ku_data} is a {len(sudo_ku_data)}*{len(sudo_ku_data[0])} list')
self.sudo_ku = sudo_ku_data # 存放每一行已有的數(shù)據(jù) self.every_row_data = {} # 每一列已有的數(shù)字
self.every_column_data = {} # 每一個(gè)3*3宮內(nèi)有的數(shù)字 self.every_three_to_three_data = {}
# 每一個(gè)空缺的位置 self.vacant_position = [] # 每一個(gè)空缺位置嘗試了的數(shù)字
self.every_vacant_position_tried_values = {}
2、編寫添加每一行，每一列，每一宮方法，方便我們后面調(diào)用
def _add_row_data(self,row,value): '''
添加數(shù)據(jù)到self.every_row_data中,即對每一行已有的數(shù)據(jù)進(jìn)行添加 :param row: :param value: :return: '''
# 如果當(dāng)前行不存在，就以當(dāng)前行為key，初始化值為set()（空的集合） if row not in self.every_row_data:
self.every_row_data[row] = set() # 如果這個(gè)值已經(jīng)出現(xiàn)過在這一行了，說明傳入的不是一個(gè)正確的數(shù)獨(dú) if value in
self.every_row_data[row]: raise TypeError(f'params {self.sudo_ku} is a invalid
SudoKu') self.every_row_data[row].add(value) def
_add_column_data(self,column,value): ''' 添加數(shù)據(jù)到self.every_column_data中,上面的函數(shù)思路一樣
:param column: :param value: :return: ''' if column not in
self.every_column_data: self.every_column_data[column] = set() if value in
self.every_column_data[column]: raise TypeError(f'params {self.sudo_ku} is a
invalid SudoKu') self.every_column_data[column].add(value) def
_get_three_to_three_key(self,row,column): ''' 得到該位置在哪一個(gè)3*3的宮內(nèi) :param row:
:param column: :return: ''' if row in [0,1,2]: if column in [0,1,2]: key = 1
elif column in [3,4,5]: key = 2 else: key = 3 elif row in [3,4,5]: if column in
[0,1,2]: key = 4 elif column in [3,4,5]: key = 5 else: key = 6 else: if column
in [0,1,2]: key = 7 elif column in [3,4,5]: key = 8 else: key = 9 return key
def _add_three_to_three_data(self,row,column,value): '''
添加數(shù)據(jù)到self.every_three_to_three_data中 :param row: :param column: :param value:
:return: ''' # 首先得到在哪一個(gè)3*3的宮內(nèi) key = self._get_three_to_three_key(row,column) #
然后也和上面添加行，列的思路一樣 if key not in self.every_three_to_three_data:
self.every_three_to_three_data[key] = set() if value in
self.every_three_to_three_data[key]: raise TypeError(f'params {self.sudo_ku} is
a invalid SudoKu') self.every_three_to_three_data[key].add(value)
3、遍歷數(shù)獨(dú)，對每種數(shù)據(jù)進(jìn)行初始化
def _init(self): ''' 根據(jù)傳入的數(shù)獨(dú)，初始化數(shù)據(jù) :return: ''' for row,row_datas in
enumerate(self.sudo_ku): for column,value in enumerate(row_datas): if value ==
'': # 添加空缺位置 self.vacant_position.append( (row,column) ) else: # 添加行數(shù)據(jù)
self._add_row_data(row,value) # 添加列數(shù)據(jù) self._add_column_data(column,value) #
添加宮數(shù)據(jù) self._add_three_to_three_data(row,column,value)
4、編寫判斷某一個(gè)位置的值是否合法的函數(shù)
def _judge_value_is_legal(self,row,column,value): ''' 判斷方放置的數(shù)據(jù)是否合法 :param row:
:param column: :param value: :return: ''' # value是否存在這一行數(shù)據(jù)中 if value in
self.every_row_data[row]: return False # value是否存在這一列數(shù)據(jù)中 if value in
self.every_column_data[column]: return False # value是否存在這個(gè)3*3的宮內(nèi) key =
self._get_three_to_three_key(row,column) if value in
self.every_three_to_three_data[key]: return False return True
5、編寫計(jì)算的函數(shù)，在當(dāng)前位置循環(huán) 可以使用的額數(shù)據(jù)，確定可以是否可以放置這個(gè)值
def _calculate(self, vacant_position): ''' 計(jì)算，開始對數(shù)獨(dú)進(jìn)行放置值 :param
vacant_position: :return: ''' # 得到當(dāng)前位置 row,column = vacant_position values =
set(range(1,10)) # 對當(dāng)前為位置創(chuàng)建一個(gè)唯一key,用來存放當(dāng)前位置已經(jīng)嘗試了的數(shù)據(jù) key = str(row) +
str(column) # 如果這個(gè)key存在，就對values進(jìn)行取差集，因?yàn)閮蓚€(gè)都是集合（set），直接使用-就行了 if key in
self.every_vacant_position_tried_values: values = values -
self.every_vacant_position_tried_values[key] # 如果這個(gè)key不存在，就創(chuàng)建一個(gè)空的集合 else:
self.every_vacant_position_tried_values[key] = set() for value in values: #
對當(dāng)前數(shù)據(jù)添加到當(dāng)前位置嘗試過的的數(shù)據(jù)中 self.every_vacant_position_tried_values[key].add(value) #
如果當(dāng)前value合法，可以放置 if self._judge_value_is_legal(row,column,value): print(f'set
{vacant_position} value is {value}') # 更新 判斷數(shù)據(jù)合法時(shí) 需要使用到的數(shù)據(jù)
self.every_column_data[column].add(value) self.every_row_data[row].add(value)
key = self._get_three_to_three_key(row,column)
self.every_three_to_three_data[key].add(value) # 修改這個(gè)位置的值為value
self.sudo_ku[row][column] = value # 返回True 和填充的 value return True,value return
False,None
6、如果當(dāng)前位置沒有任何一個(gè)值可以放置，那么就回溯，返回上一次成功的位置，重新取值,所以我們編寫一個(gè)回溯函數(shù)
def
_backtrack(self,current_vacant_position,previous_vacant_position,previous_value):
''' 回溯 :param current_vacant_position: 當(dāng)前嘗試失敗的位置 :param
previous_vacant_position: 上一次成功的位置 :param previous_value:上一次成功的值 :return: '''
print(f"run backtracking... value is {previous_value},vacant position is
{previous_vacant_position}") row,column = previous_vacant_position #
對上一次成功的值從需要用到的判斷的數(shù)據(jù)中移除 self.every_column_data[column].remove(previous_value)
self.every_row_data[row].remove(previous_value) key =
self._get_three_to_three_key(row,column)
self.every_three_to_three_data[key].remove(previous_value) # 并且上一次改變的的值變回去
self.sudo_ku[row][column] = '' # 對當(dāng)前嘗試失敗的位置已經(jīng)城市失敗的的值進(jìn)行刪除，因?yàn)榛厮萘?，所以下一次進(jìn)來需要重新判斷值
current_row,current_column = current_vacant_position key = str(current_row) +
str(current_column) self.every_vacant_position_tried_values.pop(key)
7、到這里為止，我們所有的功能函數(shù)都寫完了，然后我們編寫一個(gè)函數(shù)，開始循環(huán)所有的空缺位置。然后進(jìn)行計(jì)算。
def get_result(self): ''' 得到計(jì)算之后的數(shù)獨(dú) :return: ''' # 首先初始化一下數(shù)據(jù) self._init() #
空缺位置的長度 length = len(self.vacant_position) # 空缺位置的下標(biāo) index = 0 # 存放已經(jīng)嘗試了的數(shù)據(jù)
tried_values = [] # 如果index小于length,說明還沒有計(jì)算完 while index < length: # 得到一個(gè)空缺位置
vacant_position = self.vacant_position[index] # 計(jì)入計(jì)算函數(shù)，返回是否成功，如果成功，value為成功
的值，如果失敗，value為None is_success,value = self._calculate(vacant_position) #
如果成功，將value放在tried_values列表里面，因?yàn)榱斜硎怯行虻? # index+1 對下一個(gè)位置進(jìn)行嘗試 if is_success:
tried_values.append(value) index += 1 #
失敗，進(jìn)行回溯,并且index-1，返回上一次的空缺位置，我們需要傳入當(dāng)前失敗的位置 和 上一次成功的位置和值 else:
self._backtrack(vacant_position,self.vacant_position[index-1],tried_values.pop())
index -= 1 # 如果index<0 了 說明這個(gè)數(shù)獨(dú)是無效的 if index < 0: raise
ValueError(f'{self.sudo_ku} is a invalid sudo ku') # 返回計(jì)算之后的數(shù)獨(dú) return
self.sudo_ku
效果展示

呼。。。終于干完代碼，接下來我們呢可以"開始收獲"了
if __name__ == '__main__': sudo_ku_data = [ [5,3,'','',7,'','','',''],
[6,'','',1,9,5,'','',''], ['',9,8,'','','','',6,''], [8,'','','',6,'','','',3],
[4,'','',8,'',3,'','',1], [7,'','','',2,'','','',6], ['',6,'','','','',2,8,''],
['','','',4,1,9,'','',5], ['','','','',8,'','',7,9], ] # 得到計(jì)算好的數(shù)獨(dú) sudo_ku =
SudoKu(sudo_ku_data).get_result() print(sudo_ku) ################ # 結(jié)果顯示 #
################ [5, 3, 4, 6, 7, 8, 9, 1, 2] [6, 7, 2, 1, 9, 5, 3, 4, 8] [1, 9,
8, 3, 4, 2, 5, 6, 7] [8, 5, 9, 7, 6, 1, 4, 2, 3] [4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6] [9, 6, 1, 5, 3, 7, 2, 8, 4] [2, 8, 7, 4, 1, 9, 6,
3, 5] [3, 4, 5, 2, 8, 6, 1, 7, 9]
這效果就很完美啊，我們在來測試一個(gè)比較難得數(shù)獨(dú)。

輸入數(shù)獨(dú)為：
[ [8, '', '', '', '', '', '', '', 4], ['', 2, '', '', '', '', '', 7, ''], ['',
'', 9, 1, '', 6, 5, '', ''], ['', '', 6, 2, '', 8, 9, '', ''], ['', 9, '', '',
3, '', '', 4, ''], ['', '', 2, 4, '', 7, 8, '', ''], ['', '', 7, 9, '', 5, 6,
'', ''], ['', 8, '', '', '', '', '', 2, ''], [6, '', '', '', '', '', '', '',
9], ] ################ # 結(jié)果顯示 # ################ [8, 6, 1, 5, 7, 2, 3, 9, 4]
[5, 2, 4, 3, 8, 9, 1, 7, 6] [3, 7, 9, 1, 4, 6, 5, 8, 2] [4, 3, 6, 2, 5, 8, 9,
1, 7] [7, 9, 8, 6, 3, 1, 2, 4, 5] [1, 5, 2, 4, 9, 7, 8, 6, 3] [2, 4, 7, 9, 1,
5, 6, 3, 8] [9, 8, 5, 7, 6, 3, 4, 2, 1] [6, 1, 3, 8, 2, 4, 7, 5, 9]
哈哈哈哈哈，以后還有誰能夠和我比解數(shù)獨(dú)。膨脹.jpg

代碼已全部上傳至Github：
https://github.com/MiracleYoung/You-are-Pythonista/tree/master/PythonExercise/App/solveSudoku/xujin

<https://github.com/MiracleYoung/You-are-Pythonista/tree/master/PythonExercise/App/solveSudoku/xujin>

更多好玩有趣的Python盡請關(guān)注「Python專欄」

• ? 上一篇：.netcore持續(xù)集成測試篇之Xunit數(shù)據(jù)驅(qū)動(dòng)測試
• ? 下一篇：委托與事件-事件詳解（二）