前幾天和隔壁鄰居玩斗地主被發(fā)現(xiàn)了，牌被沒收了，斗地主是斗不了了，但我還想和鄰居玩耍。如果你還想斗斗地主，戳：趁老王不在，和隔壁鄰居斗斗地主，比比大小

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

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

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

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

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

數(shù)獨題目示例

大致思路

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

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

演示環(huán)境

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

具體代碼

1、首選我們創(chuàng)建一個類 SudoKu 。編寫構(gòu)造函數(shù)。

          
            class SudoKu():
    def __init__(self,sudo_ku_data):
        # 判斷傳入的數(shù)獨是否滿足格式
        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 = {}
        # 每一個3*3宮內(nèi)有的數(shù)字
        self.every_three_to_three_data = {}
        # 每一個空缺的位置
        self.vacant_position = []
        # 每一個空缺位置嘗試了的數(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ù)進行添加
    :param row:
    :param value:
    :return:
    '''
    # 如果當前行不存在，就以當前行為key，初始化值為set()（空的集合）
    if row not in self.every_row_data:
        self.every_row_data[row] = set()

    # 如果這個值已經(jīng)出現(xiàn)過在這一行了，說明傳入的不是一個正確的數(shù)獨
    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):
    '''
    得到該位置在哪一個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:
    '''
    # 首先得到在哪一個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ù)獨，對每種數(shù)據(jù)進行初始化

          
            def _init(self):
    '''
    根據(jù)傳入的數(shù)獨，初始化數(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、編寫判斷某一個位置的值是否合法的函數(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是否存在這個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、編寫計算的函數(shù)，在當前位置循環(huán) 可以使用的額數(shù)據(jù)，確定可以是否可以放置這個值

          
            def _calculate(self, vacant_position):
    '''
    計算，開始對數(shù)獨進行放置值
    :param vacant_position:
    :return:
    '''
    # 得到當前位置
    row,column = vacant_position
    values = set(range(1,10))

    # 對當前為位置創(chuàng)建一個唯一key,用來存放當前位置已經(jīng)嘗試了的數(shù)據(jù)
    key = str(row) + str(column)
    # 如果這個key存在，就對values進行取差集，因為兩個都是集合（set），直接使用-就行了
    if key in self.every_vacant_position_tried_values:
        values = values - self.every_vacant_position_tried_values[key]
    # 如果這個key不存在，就創(chuàng)建一個空的集合
    else:
        self.every_vacant_position_tried_values[key] = set()

    for value in values:
        # 對當前數(shù)據(jù)添加到當前位置嘗試過的的數(shù)據(jù)中
        self.every_vacant_position_tried_values[key].add(value)
        # 如果當前value合法，可以放置
        if self._judge_value_is_legal(row,column,value):
            print(f'set {vacant_position} value is {value}')
            # 更新 判斷數(shù)據(jù)合法時 需要使用到的數(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)

            # 修改這個位置的值為value
            self.sudo_ku[row][column] = value
            # 返回True 和填充的 value
            return True,value

    return False,None
          
        

6、如果當前位置沒有任何一個值可以放置，那么就回溯，返回上一次成功的位置，重新取值,所以我們編寫一個回溯函數(shù)

          
            def _backtrack(self,current_vacant_position,previous_vacant_position,previous_value):
    '''
    回溯
    :param current_vacant_position: 當前嘗試失敗的位置
    :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] = ''

    # 對當前嘗試失敗的位置已經(jīng)城市失敗的的值進行刪除，因為回溯了，所以下一次進來需要重新判斷值
    current_row,current_column = current_vacant_position
    key = str(current_row) + str(current_column)
    self.every_vacant_position_tried_values.pop(key)
          
        

7、到這里為止，我們所有的功能函數(shù)都寫完了，然后我們編寫一個函數(shù)，開始循環(huán)所有的空缺位置。然后進行計算。

          
            def get_result(self):
    '''
    得到計算之后的數(shù)獨
    :return:
    '''

    # 首先初始化一下數(shù)據(jù)
    self._init()

    # 空缺位置的長度
    length = len(self.vacant_position)
    # 空缺位置的下標
    index = 0

    # 存放已經(jīng)嘗試了的數(shù)據(jù)
    tried_values = []
    # 如果index小于length,說明還沒有計算完
    while index < length:
        # 得到一個空缺位置
        vacant_position = self.vacant_position[index]

        # 計入計算函數(shù)，返回是否成功，如果成功，value為成功 的值，如果失敗，value為None
        is_success,value = self._calculate(vacant_position)
        # 如果成功，將value放在tried_values列表里面，因為列表是有序的.
        # index+1 對下一個位置進行嘗試
        if is_success:
            tried_values.append(value)
            index += 1
        # 失敗，進行回溯,并且index-1，返回上一次的空缺位置，我們需要傳入當前失敗的位置 和 上一次成功的位置和值
        else:
            self._backtrack(vacant_position,self.vacant_position[index-1],tried_values.pop())
            index -= 1

        # 如果index<0 了 說明這個數(shù)獨是無效的
        if index < 0:
            raise ValueError(f'{self.sudo_ku} is a invalid sudo ku')

    # 返回計算之后的數(shù)獨
    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],
    ]

    # 得到計算好的數(shù)獨
    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]
          
        

這效果就很完美啊，我們在來測試一個比較難得數(shù)獨。

輸入數(shù)獨為：

          
            [
    [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ù)獨。膨脹.jpg

代碼已全部上傳至Github：https://github.com/MiracleYou...

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