Last Updated on 2021-04-07 by Clay
＝＝＝ 2020/01/04 更新 ＝＝＝
新版的寫法比較好懂、效能也比較好，歡迎移步觀看《使用 Python 進行數獨解題 (優化版)》。
＝＝＝ 2019/10/09 更新 ＝＝＝
我優化了一下程式，挑戰世界最難數獨從『我可以去喝杯茶』進化到了『我人才剛拿起茶杯站起來』，但意外地我身邊的朋友反而更看不懂我在寫什麼了（汗）
也許沒什麼值得參考的地方，對於懂數獨跟寫程式的人來說，這種解題就跟 Hello World 差不多吧！
程式直接更新於文章當中。
＝＝＝ 更新結束 ＝＝＝
想必大家都知道『數獨』這種遊戲吧！這是一種只用數字組成的謎題，相信熱愛此道的人並不少，比如家母就是熱衷於此，樂此不疲地解題解了數十年呢！
在此，請讓我先引用維基百科的簡介：
數獨是一種數學邏輯遊戲，遊戲由9×9個格子組成，玩家需要根據格子提供的數字推理出其他格子的數字。遊戲設計者會提供最少17個數字使得解答謎題只有一個答案。
Wiki
這種遊戲只需要邏輯思維能力，與數字運算無關。雖然玩法簡單，但提供的數字卻千變萬化，所以不少教育者認為數獨是鍛鍊腦筋的好方法。
數獨遊戲由日本出版商 Nikoli 於 1986年發展，意思為「獨身最適數字」[1]。
2005年，數獨遊戲發揚到全世界![2]
再放上圖示：
而今天我要筆記的就是，我當初剛學習 Python 時所寫的一個練習用小程式。
這雖然沒什麼了不起的技術、程式碼也肯定還存在著許多可以精簡、優化的地方——那這個解題程式卻是我 Python 程式學習的開頭。
接下來，請容我向大家介紹吧！
解題想法
數獨基本上只有幾個簡單的規則：
- 一行裡的數字不重複
- 一列裡的數字不重複
- 九宮格 (3x3) 範圍內的數字不重複
- 所有行、列、九宮格的數字都是由 1～9 組成
如何？很單純吧？
基本上，我的程式分成兩個部份: 一開始，當我們初始化好我們的題目之後，首先我先進行『只有一解』的判斷 —— 也就是遍歷整個棋盤，找到棋盤上僅有一解的地方，然後填入那唯一的解答。
當我們還有找到這樣的『唯一解』時，我的程式便會無止境地跑下去，直到再也無法找到答案為止。
要注意！這樣的程式設計是不足以完成整個數獨題目的！（當然，有些簡單的或許可以。）數獨題目中，往往有著『暫時』看不出來複數解答中『哪一個才是正解』的情況。
這時候，我們就要利用程式的暴力解法啦！使用『遞迴』的觀念，不斷將可能的答案填入，若是發現棋盤已經填不下去、沒有解答，可是棋盤偏偏又還沒有完成的情況，我們就先回到遞迴上一層，排除掉我們填入的這個解答，繼續往下尋找正解。
我想大家都聽得出來，第二部份『遞迴』比第一部份『填唯一解』時間複雜度大上許多，這就是我們為什麼需要第一部份來簡化棋盤。
程式碼
＝＝＝ 2019/10/09 更新版本 ＝＝＝
# -*- coding: utf-8 -*- class Sudoku: def __init__(self, board): if board and len(board) == 9 and len(board[0]) == 9: self.board = board else: raise ValueError # List all possible number self.positionState = [[[n for n in range(1, 10)] for r in range(9)] for c in range(9)] self.setNumberHistory = [] self.boardNum = self.setNum() self.i, self.j = self.simplifyBoard() def plotBoard(self): for n in range(9): print(self.board[n]) print('-------------------------------------', self.setNum()) def onlyOneCheck(self, x, y): new_x, new_y = x//3*3, y//3*3 row = self.board[x] column = [self.board[_][y] for _ in range(9)] square = [self.board[a][b] for a in range(new_x, new_x+3) for b in range(new_y, new_y+3)] total_collision_num_list = list(set(row+column+square)) total_num_list = [n for n in range(1, 10)] for n in total_collision_num_list: if n in total_num_list: total_num_list.remove(n) if len(total_num_list) == 1: return total_num_list[0] else: return False def row_col(self, x, n): return n in self.board[x] def column_col(self, y, n): return n in [self.board[_][y] for _ in range(9)] def square_col(self, x, y, n): return n in [self.board[a][b] for a in range(x//3*3, x//3*3+3) for b in range(y//3*3, y//3*3+3)] # Count the number we set into the board def setNum(self): return sum([1 for a in range(9) for b in range(9) if self.board[a][b]]) def simplifyBoard(self): for a in range(9): for b in range(9): if self.board[a][b] == 0: result = self.onlyOneCheck(a, b) if result: self.board[a][b] = result return 0, 0 def check_end(self): for r in range(9): if 0 in self.board[r]: return False return True def update(self): if self.j == 8: self.i, self.j = self.i+1, 0 else: self.j += 1 def run(self): while True: if self.board[self.i][self.j]: self.update() continue if self.positionState[self.i][self.j]: n = self.positionState[self.i][self.j].pop() if not (self.row_col(self.i, n) or self.column_col(self.j, n) or self.square_col(self.i, self.j, n)): self.board[self.i][self.j] = n self.setNumberHistory.append([self.i, self.j]) result = self.check_end() if result: break self.update() else: self.positionState[self.i][self.j] = [_ for _ in range(1, 10)] self.i, self.j = self.setNumberHistory.pop() self.board[self.i][self.j] = 0 if __name__ == '__main__': import time startTime = time.time() question = [[1, 0, 0, 0, 7, 9, 0, 8, 0], [5, 9, 0, 0, 0, 2, 7, 3, 4], [7, 0, 0, 5, 3, 8, 0, 0, 9], [0, 0, 0, 3, 4, 0, 0, 2, 0], [3, 4, 0, 7, 2, 0, 0, 5, 1], [0, 5, 0, 8, 0, 0, 0, 0, 3], [0, 0, 7, 9, 0, 3, 5, 0, 8], [9, 1, 0, 0, 0, 0, 3, 0, 0], [6, 0, 0, 0, 0, 0, 1, 9, 0]] sudoku = Sudoku(question) sudoku.run() sudoku.plotBoard() print('cost time:', time.time()-startTime)
Output:
[7, 8, 9, 3, 1, 4, 6, 5, 2]
[3, 4, 2, 8, 5, 6, 7, 9, 1]
[6, 1, 5, 9, 2, 7, 4, 3, 8]
[5, 2, 7, 4, 3, 9, 8, 1, 6]
[8, 9, 1, 6, 7, 2, 3, 4, 5]
[4, 3, 6, 5, 8, 1, 2, 7, 9]
[2, 5, 8, 7, 9, 3, 1, 6, 4]
[1, 6, 3, 2, 4, 5, 9, 8, 7]
[9, 7, 4, 1, 6, 8, 5, 2, 3]
------------------------------------- 81
The End
cost: 0.013887643814086914 s寫得很冗長，請大家笑笑就好。
我簡單講解下我的程式，由於行數太多，我只講解 sudoku 這個重要 class 的基本函式。
__init()__: 這部份就是初始化棋盤，你可以任意填入想要解題的題目。
board_plot(): 這部份就是畫出棋盤，主要是我當初在看解題的進度用的。
only_one_check(): 這就是剛才講的第一階段『找唯一解』，這可說是相當單純。
row_check(): 判斷我們填入的值是否在列裡面。
column_check(): 判斷我們填入的值是否在行裡面。
square_check(): 判斷我們填入的值是否在九宮格裡面。
check_end(): 判斷棋盤是否填完。
run(): 進行遞迴，逐步找出數獨的解答。（也就是第二部份）
順帶一題，我也將所有的程式碼放上 github，歡迎大家留言，或是給 star 支持 ＝)
https://github.com/ccs96307/Sudoku
將來的改進計畫
目前所想到還可以做的的就是製作 GUI 吧！當年我在撰寫這個程式的時候，其實有試圖用 Pygame 做一個有點醜的界面，但因為要多次運行時出了 bug，加上當時後來有別的事情要忙，我便暫時擱著了。
若還有續篇的話，也許我會再次重新寫一個好看點的界面的。
如果你想學習 Python 的基本教學，不妨參考我所寫的： Python 基本教學
感謝大家的閱讀！