Skip to content

[Python] 使用遞迴程式進行數獨解題

Last Updated on 2021-04-07 by Clay

＝＝＝ 2020/01/04 更新 ＝＝＝

新版的寫法比較好懂、效能也比較好，歡迎移步觀看《使用 Python 進行數獨解題 (優化版)》。

＝＝＝ 2019/10/09 更新 ＝＝＝

我優化了一下程式，挑戰世界最難數獨從『我可以去喝杯茶』進化到了『我人才剛拿起茶杯站起來』，但意外地我身邊的朋友反而更看不懂我在寫什麼了（汗）

也許沒什麼值得參考的地方，對於懂數獨跟寫程式的人來說，這種解題就跟 Hello World 差不多吧！

程式直接更新於文章當中。

＝＝＝ 更新結束 ＝＝＝

想必大家都知道『數獨』這種遊戲吧！這是一種只用數字組成的謎題，相信熱愛此道的人並不少，比如家母就是熱衷於此，樂此不疲地解題解了數十年呢！

在此，請讓我先引用維基百科的簡介：

數獨是一種數學邏輯遊戲，遊戲由9×9個格子組成，玩家需要根據格子提供的數字推理出其他格子的數字。遊戲設計者會提供最少17個數字使得解答謎題只有一個答案。
這種遊戲只需要邏輯思維能力，與數字運算無關。雖然玩法簡單，但提供的數字卻千變萬化，所以不少教育者認為數獨是鍛鍊腦筋的好方法。
數獨遊戲由日本出版商 Nikoli 於 1986年發展，意思為「獨身最適數字」[1]。
2005年，數獨遊戲發揚到全世界![2]

Wiki

再放上圖示：

Sudoku
Sudoku

而今天我要筆記的就是，我當初剛學習 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 基本教學

感謝大家的閱讀！

Tags:

Leave a Reply