旁友數獨會伐啦？python秒解數獨瞭解下伐啦？

来源:https://www.cnblogs.com/moonhmily/archive/2019/08/07/11312887.html
-Advertisement-
Play Games

前幾天和隔壁鄰居玩鬥地主被髮現了，牌被沒收了，鬥地主是鬥不了了，但我還想和鄰居玩耍。 想破腦袋終於讓我想到一個游戲，數獨！什麼叫數獨？數獨就是可以讓我趁老王不在的時候和隔壁鄰居一起玩耍的游戲！ ...


前幾天和隔壁鄰居玩鬥地主被髮現了，牌被沒收了，鬥地主是鬥不了了，但我還想和鄰居玩耍。如果你還想鬥鬥地主，戳：趁老王不在，和隔壁鄰居鬥鬥地主，比比大小

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

數獨的規則

1、數字 1-9 在每一行只能出現一次。

2、數字 1-9 在每一列只能出現一次。

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

數獨題目示例

大致思路

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

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

在這裡插入圖片描述

演示環境

  • 操作系統：windows10
  • python版本：python 3.7
  • 代碼編輯器：pycharm 2018.2

具體代碼

1、首選我們創建一個類SudoKu。編寫構造函數。

class SudoKu():
    def __init__(self,sudo_ku_data):
        # 判斷傳入的數獨是否滿足格式
        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
        # 存放每一行已有的數據
        self.every_row_data = {}
        # 每一列已有的數字
        self.every_column_data = {}
        # 每一個3*3宮內有的數字
        self.every_three_to_three_data = {}
        # 每一個空缺的位置
        self.vacant_position = []
        # 每一個空缺位置嘗試了的數字
        self.every_vacant_position_tried_values = {}

2、編寫添加每一行，每一列，每一宮方法，方便我們後面調用

def _add_row_data(self,row,value):
    '''
    添加數據到self.every_row_data中,即對每一行已有的數據進行添加
    :param row:
    :param value:
    :return:
    '''
    # 如果當前行不存在，就以當前行為key，初始化值為set()（空的集合）
    if row not in self.every_row_data:
        self.every_row_data[row] = set()

    # 如果這個值已經出現過在這一行了，說明傳入的不是一個正確的數獨
    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):
    '''
    添加數據到self.every_column_data中,上面的函數思路一樣
    :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的宮內
    :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):
    '''
    添加數據到self.every_three_to_three_data中
    :param row:
    :param column:
    :param value:
    :return:
    '''
    # 首先得到在哪一個3*3的宮內
    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、遍曆數獨，對每種數據進行初始化

def _init(self):
    '''
    根據傳入的數獨，初始化數據
    :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:
                # 添加行數據
                self._add_row_data(row,value)
                # 添加列數據
                self._add_column_data(column,value)
                # 添加宮數據
                self._add_three_to_three_data(row,column,value)

4、編寫判斷某一個位置的值是否合法的函數

def _judge_value_is_legal(self,row,column,value):
    '''
    判斷方放置的數據是否合法
    :param row:
    :param column:
    :param value:
    :return:
    '''

    # value是否存在這一行數據中
    if value in self.every_row_data[row]:
        return False
    # value是否存在這一列數據中
    if value in self.every_column_data[column]:
        return False

    # value是否存在這個3*3的宮內
    key = self._get_three_to_three_key(row,column)
    if value in self.every_three_to_three_data[key]:
        return False

    return True

5、編寫計算的函數，在當前位置迴圈 可以使用的額數據，確定可以是否可以放置這個值

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

    # 對當前為位置創建一個唯一key,用來存放當前位置已經嘗試了的數據
    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不存在，就創建一個空的集合
    else:
        self.every_vacant_position_tried_values[key] = set()

    for value in values:
        # 對當前數據添加到當前位置嘗試過的的數據中
        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}')
            # 更新 判斷數據合法時 需要使用到的數據
            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、如果當前位置沒有任何一個值可以放置，那麼就回溯，返回上一次成功的位置，重新取值,所以我們編寫一個回溯函數

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
    # 對上一次成功的值從需要用到的判斷的數據中移除
    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] = ''

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

7、到這裡為止，我們所有的功能函數都寫完了，然後我們編寫一個函數，開始迴圈所有的空缺位置。然後進行計算。

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

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

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

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

        # 計入計算函數，返回是否成功，如果成功，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 了 說明這個數獨是無效的
        if index < 0:
            raise ValueError(f'{self.sudo_ku} is a invalid sudo ku')

    # 返回計算之後的數獨
    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],
    ]

    # 得到計算好的數獨
    sudo_ku = SudoKu(sudo_ku_data).get_result()
    print(sudo_ku)

################
#   結果顯示    #
################
[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]

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

輸入數獨為：

[
    [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],
]

################
#   結果顯示    #
################
[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]

哈哈哈哈哈，以後還有誰能夠和我比解數獨。膨脹.jpg

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

更多好玩有趣的Python盡請關註「Python專欄」


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • vue-cli3構建ts項目
    1、構建項目 上面的第一條，也就是 aaa 這一個選項在你第一次創建項目的時候是並不會出現的，只有你第一次創建完成項目後回提示你保存為預設配置模板，下次新建項目的時候就可以使用你選用的配置快速新建項目了，不需要再重新選擇配置項目了。 第二條選項便是 vue cli 3 預設的項目模板，包含 babe ...
  • JavaScript數據結構——字典和散列表的實現
    在前一篇文章中，我們介紹瞭如何在JavaScript中實現集合。字典和集合的主要區別就在於，集合中數據是以[值，值]的形式保存的，我們只關心值本身；而在字典和散列表中數據是以[鍵，值]的形式保存的，鍵不能重覆，我們不僅關心鍵，也關心鍵所對應的值。 我們也可以把字典稱之為映射表。由於字典和集合很相似， ...
  • jQuery效果之滑動
    jQuery 滑動方法有三種：slideDown()、slideUp()、slideToggle()。 ...
  • typeScript學習隨筆（一）
    TypeScript學習隨筆（一） 這麼久了還不沒好好學習哈這麼火的ts,邊學邊練邊記吧！ 啥子是TypeScript TypeScript 是 JavaScript 的一個超集，支持 es6 標準。 TypeScript 由微軟開發的自由和開源的編程語言。 TypeScript 設計目標是開發大型 ...
  • DesignPattern系列__08UML相關知識
    前言 現在，很少有人和90年代一樣，自己去實現一個軟體的各個方面，也就是說，在工作中，和人溝通是必備的技能。那麼，作為一枚碼農，如何和他人溝通呢？這就要依靠本文的主題了——UML。 簡介 UML——Unified modeling language UML(統一建模語言)，是一種用於軟體系統分析和設 ...
  • DesignPattern系列__06迪米特原則
    迪米特原則定義 迪米特原則，也叫最少知道原則，即一個類應該 對自己依賴的類知道的越少越好 ，而你被依賴的類多麼複雜，對我都沒有關係。也就是說，對於別依賴的類來說，不管業務邏輯多麼複雜，都應該儘量封裝在類的內部；對外除了必備的public方法，不再泄露任何信息。 1.問題由來 我們知道，類和類是有耦合 ...
  • python 通過使用pandas的實現的Excel的批量轉換CSV文件的處理
    最近同事在處理文件導入的時候需要把一批文件換成CSV的格式，但是直覺修改尾碼是不生效的，而且xlsx和xls的文件沒法直接換成CVS的文件，所以找了一下方式，並且自己實現了python的轉換方式。代碼如下 文件需要導入pandas 還要引入xlrd 代碼是基於python3.6的環境。 ...
  • 重溫面向對象核心 上
    實例解讀面向對象核心，所有例子基於 C#，涉及我們實務中最常關心的問題： 1、封裝、繼承、多態； 2、抽象類、介面； 3、委托、事件。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類