Day28. 實作練習：數獨解決器Sudoku Solver - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2024 iThome 鐵人賽

DAY 28

0

佛心分享-IT 人自學之術

Python學習馬拉松：30天挑戰系列第 28 篇

Day28. 實作練習：數獨解決器Sudoku Solver

16th鐵人賽

2024-10-12 09:51:50

66 瀏覽

分享至

教學來源：https://www.youtube.com/watch?v=8ext9G7xspg
這段 Python 程式碼實現了一個 Sudoku 解決器。Sudoku 是一種數學邏輯遊戲，玩家需要根據已知的數字，在一個 9x9 的格子上填入數字 1-9，使得每一行、每一列和每一個 3x3 的小九宮格中，數字 1-9 都只出現一次。
程式碼與執行結果：

程式結構
◆ find_next_empty 函數:
◎ 這個函數用來尋找下一個空的格子。
◎ 遍歷整個棋盤，找到第一個值為 -1 的格子（用 -1 表示空格子），並返回其行和列索引。
◎ 如果找不到空的格子，則返回 None。
◆ is_valid 函數:
◎ 這個函數用來判斷在指定位置填入一個數字是否合法。
◎ 檢查該數字是否在同一行、同一列或同一個 3x3 小九宮格中出現過。
◎ 如果數字合法，返回 True，否則返回 False。
◆ solve_sudoku 函數:
◎ 這是整個解題的核心函數。
◎ 採用回溯法（backtracking）來解決 Sudoku。
◎ 首先找到下一個空的格子。
◎ 對於這個空格子，嘗試填入 1 到 9 之間的數字。
◎ 對於每個嘗試的數字，檢查是否合法。
○ 如果合法，則遞歸調用 solve_sudoku 函數，試圖解出剩下的部分。
○ 如果遞歸調用返回 True，表示找到了一個解。
○ 如果遞歸調用返回 False，則回溯，嘗試填入其他數字。
○ 如果所有數字都試過了，仍然找不到解，則表示原來的 Sudoku 無解。
程式流程

初始化棋盤: 將一個部分填好的 Sudoku 棋盤作為輸入。
尋找空格子: 使用 find_next_empty 函數找到下一個空的格子。
嘗試填數字: 對於找到的空格子，依次嘗試填入 1 到 9。
檢查合法性: 使用 is_valid 函數檢查填入的數字是否合法。
遞歸求解: 如果合法，則遞歸調用 solve_sudoku 函數，試圖解出剩下的部分。
回溯: 如果遞歸調用返回 False，則回溯，嘗試填入其他數字。
找到解或無解: 如果找到了一個解，則返回 True；如果所有可能都試過了，仍然找不到解，則返回 False。

Day27. 實作練習：踩地雷遊戲 Minesweeper

Day29. 實作練習：圈圈叉叉Tic-Tac-Toe --AI

系列文

Python學習馬拉松：30天挑戰共 30 篇

目錄

RSS系列文訂閱系列文

2 人訂閱

完整目錄

直播研討會

{{ item.subject }}

{{ item.channelVendor }} {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

1064 組

團體組數

40 組

累計文章數

22189 篇

完賽人數

602 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙