Skip to content

[Python] 使用遞迴程式進行數獨解題（優化版）

Last Updated on 2021-05-19 by Clay

過去，大概在一年多以前，在我初學 Python 的時候，我寫了個『數獨解題程式』來當作練習，在那之後，我曾經有短暫地 Clean Code，不過並沒有對這個程式有太多的優化。

沒錯，就是我曾經寫過的這篇文章《使用 Python 進行數獨自動解題》。

我一直非常慚愧，一來那個程式的程式碼不好閱讀、二來在碰到高級題目的時候解題速度稱不上快。比如說我挑戰號稱『11 星』的世界最難數獨題目 (https://newtalk.tw/news/view/2012-06-30/26670)：

40 秒！這花得時間太久了！有鑑於此，趁著我最近比較有空閒的時間，我重新寫了一個比較快的版本。

那麼，我就紀錄在下方吧！

首先，我本來的程式使用了遞迴，但就像我同學說得一樣：遞迴是高手才在用的東西！像我這種凡人，寫寫 For 迴圈就差不多了。

import time


# Settings
start_time = time.time()


class Sudoku():
    def __init__(self, board):
        self.board = board

        self.size = len(self.board[0])
        self.choices = [-1 if self.board[i][j] else 1
                        for i in range(self.size)
                        for j in range(self.size)]
       
        self.x = 0
        self.y = 0

    def plot(self):
        cn = 0
        for row in self.board:
            print(row)

            for _ in row:
                if _ != 0:
                    cn += 1

        print('===========================', cn)

    def row(self, n):
        return n in self.board[self.y]

    def col(self, n):
        return n in [self.board[_][self.x]
                     for _ in range(9)]

    def square(self, n):
        return n in [self.board[b][a]
                     for a in range(self.x//3*3, self.x//3*3+3)
                     for b in range(self.y//3*3, self.y//3*3+3)]

    def collision(self, n):
        if self.row(n) or self.col(n) or self.square(n):
            return True
        else: return False

    def backward(self):
        self.board[self.y][self.x] = 0
        self.choices[self.c] = 1
        if self.x == 0:
            self.x = 8
            self.y -= 1
        else:
            self.x -= 1

        while self.choices[self.y * self.size + self.x] == -1:
            if self.x == 0:
                self.x = 8
                self.y -= 1
            else:
                self.x -= 1

    def forward(self):
        if self.x == 8:
            self.x = 0
            self.y += 1
        else:
            self.x += 1

    def isEnd(self):
        for row in self.board:
            if 0 in row:
                return False

        return True

    def run(self):
        while not self.isEnd():
            self.c = self.y*self.size+self.x
            if self.choices[self.c] != -1:
                if self.collision(self.choices[self.c]):

                    # Error
                    if self.choices[self.c] != 9:
                        self.choices[self.c] += 1
                        continue

                    # Back
                    else:
                        self.backward()

                # Success
                else:
                    self.board[self.y][self.x] = self.choices[self.c]
                    # plot()

                    self.forward()

            else:
                self.forward()

        self.plot()
        print('time:', time.time()-start_time)


if __name__ == '__main__':
    board = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 3, 6, 0, 0, 0, 0, 0],
             [0, 7, 0, 0, 9, 0, 2, 0, 0],
             [0, 5, 0, 0, 0, 7, 0, 0, 0],
             [0, 0, 0, 0, 4, 5, 7, 0, 0],
             [0, 0, 0, 1, 0, 0, 0, 3, 0],
             [0, 0, 1, 0, 0, 0, 0, 6, 8],
             [0, 0, 8, 5, 0, 0, 0, 1, 0],
             [0, 9, 0, 0, 0, 0, 4, 0, 0]]

    s = Sudoku(board)
    s.run()



Output:

同一個題目，從 40 秒縮短成 1 秒，希望我的程式功力有大約 40 倍的成長。

以下是我 Sudoku 這個程式的 Github 網址：https://github.com/ccs96307/Sudoku，歡迎大家自由參觀。

Tags:

Leave a Reply