Python秒解數獨

封面Image by JeromeWare from Pixabay 

數獨起源於18世紀初瑞士數學家歐拉等人研究的拉丁方陣（Latin Square）。19世紀80年代，有美國人根據這種拉丁方陣發明了數獨的雛形。20世紀70年代，出現了公認的數獨最早的見報版本。1984年一位日本學者將其介紹到了日本，起名為「數字は獨身に限る」（すうじはどくしんにかぎる），後改名為「數獨」（すうどく），其中「數」（すう）是數字的意思，「獨」（どく）是唯一的意思。

數獨遊戲如下例：

 

在空白格內填1-9，保證每個豎排九格，每個橫排九格，每個粗線九宮格都有數字1-9。

完成：

數獨存在很多進階解法，高階解法，例如：X-Wing，XY-Chian之類。目前已經證明，給定的提示數（一開始標黑色的那些數字）如果少於等於16個，則一定存在多個解（多於16個也不一定是唯一解，還要看給定的提示數的位置）。

數獨的電腦程式解法

電腦程式最簡單的數獨解決辦法就是單純回溯法，即：從第一個空格開始，嘗試每一個數字，直到得到最後結果。這種方法存在優化的空間----剪枝，可以大幅縮減計算量。包括已經在圍棋上一騎絕塵超越人類的AlphaZero（AlphaGo增強版），也需要採用這種算法。通過編程X-Wings、XY-Chain之類的數獨進階、高階解法來解數獨，也不是不可以，但它存在兩個問題：

由於進階、高階解法的複雜性，導致代碼複雜程度急劇上升，使得編寫代碼變得非常困難；

同時，就算完成高階解法的程序編寫，也不能保證這就是萬能解決方案。

Python解法思路

在Python中，有一個擅長處理矩陣的包，Numpy。這個包是用C語言編寫的，所以運算效率高於純Python代碼，同時矩陣切片非常方便。

用一個9個元素的向量代表1-9的可能性，有可能，記為1，不可能，記為0。

例：

[0 0 0 1 0 0 0 0 0] => 只可能為4

[1 1 0 0 0 1 0 0 1] => 可能為1、2、6、9

[1 1 1 1 1 1 1 1 1] = > 1至9都有可能

[0 0 0 0 0 0 0 0 0] = > 沒有任何一個數字可能，解法錯誤

將橫豎都為9行的數獨（9x9的二維數組），每一個方格替換為一個9元素向量，則數獨就變成了9x9x9的三維數組。

而當所有向量都只含有一個1，八個0的時候，就得到了數獨的解。

那麼所謂同一數字在橫排、豎排、所在九宮格內只能出現一次

在numpy裡應該怎麼理解？

由於已經確定了紅框1的第一位是1，所以除了紅框以外，所有紅框相關的格（也就是有顏色的那些格），第一位都必須是 0

根據以上的規律，可以將解法建立如下：

1、根據給定唯一數，設置初始三維數組；

2、根據唯一數情況，剔除相關格（唯一數所在的橫排、豎排、九宮格）的可能性；

3、重複第2步，直至無法再進一步剔除；

4、任選一格（當然最好是只有兩個數字可能性的格子），假設為其中一個數字；

5、重複第2步，直至無法再進一步剔除，或出現錯誤；

6、如果第5步出現錯誤，則退回第4步，假設該格為其他可能的數字；

7、如果第5步是無法再進一步剔除，則重複第4步；

8、直到出現所有向量都只含有一個1的時候，表示得到一個解

代碼

導入numpy模塊

設置一個類，這個類只儲存初始數獨問題，以及所有該數獨的答案（如果不止一個的話），可以列印數獨，以及所有答案

class Sudoku:    def __init__(self):        self.sudoku = np.zeros([9, 9, ], dtype=np.int8)        self.sudoku_final = []
        def start_puzzle(self, sequence):        if isinstance(sequence, str):            if len(sequence) == 81:                for index, number in enumerate(sequence):                    num = int(number)                    if num > 0:                        self.sudoku[index // 9][index - index // 9 * 9] = num            else:                raise Exception("sequence lenth is not 81")        else:            raise Exception("sequence type error, need 81 lenth string of numbers")        return
            def print_sudoku(self, sudoku=False):        if isinstance(sudoku, bool):            sudoku = self.sudoku        for index, array in enumerate(sudoku):            if index % 3 == 0:                print('+-' * 3)            item = array.astype(str)            print(f'{" ".join(item[:3])}| {" ".join(item[3:6])}| {" ".join(item[6:])}|')        return
        def print_answers(self):        if len(self.sudoku_final) == 0:            print('Failed to find any solution, sorry~')            return        elif len(self.sudoku_final) == 1:            print('There is only 1 solution')        else:            print(f'There are {len(self.sudoku_final)} solutions')        for solution in self.sudoku_final:            self.print_sudoku(solution)        return
設置一個類，這個類相當於草稿紙，用於：
class Draft:    def __init__(self):        self.sudoku = np.ones([9, 9, 9, ], dtype=np.int8)        self.alter = False
    def initiation(self, s):        for y, array in enumerate(s.sudoku):            for x, number in enumerate(array):                if number != 0:                    self.sudoku[y][x] = np.zeros([9, ], dtype='int8')                                                                                self.sudoku[y, x, number - 1] = 1        return
    def duplicate(self):        new_draft = Draft()        new_draft.sudoku = self.sudoku + 1 - 1        return new_draft
    def add_solution(self, sudoku):        """the result must be checked"""        index = np.where(self.sudoku == 1)[2]        index += 1        solution = index.flatten()        solution.resize((9, 9))        sudoku.sudoku_final.append(solution)        return
    def finish_check(self):        draft_array = np.sum(self.sudoku, axis=2).ravel()        if (draft_array == 1).all():            return True        else:            return False
    def _set_origin(self):        origin = self.sudoku + 1        origin -= 1        return origin
    def alter_check(self, origin):        return (origin != self.sudoku).any()
                def last_number(self):        matrix = np.sum(self.sudoku, axis=2)        if (matrix == 0).any():            return False        origin = self._set_origin()        index = np.where(matrix == 1)        for i in range(len(index[0])):            y = index[0][i]            x = index[1][i]            position = np.where(self.sudoku[y, x] == 1)            if not len(position[0]):                return False            number = position[0][0]            self.sudoku[y, x, number] = 0            self.sudoku[y, :, number] = 0            self.sudoku[:, x, number] = 0            self.sudoku[y - y % 3:y - y % 3 + 3, x - x % 3:x - x % 3 + 3, number] = 0            self.sudoku[y, x, number] = 1        if self.alter_check(origin):            self.alter = True        else:            self.alter = False        return True
    def depletion_last_number(self):        """A while loop to deplete the 'last number'"""        result = True        self.alter = True        while self.alter:            self.alter = False            result = self.last_number()            if not result:                break        return result
    def least_possible_cell(self):        """choose a cell with least possible number"""        possible_matrix = np.sum(self.sudoku, axis=2)        for possibility in range(2, 8):            if (possible_matrix == possibility).any():                positions = np.where(possible_matrix == possibility)                y = positions[0][0]                x = positions[1][0]                return y, x
    def propose_hypothesis(self, y, x, index):        """duplicate a draft and propose the hypothesis"""        new_draft = self.duplicate()        new_draft.sudoku[y][x] = np.zeros([9, ], dtype='int8')        new_draft.sudoku[y][x][index] = 1        return new_draft
    def backtrack(self, sudoku):        """backtracking method to the exhaustion of any possibilities"""                                                        y, x = self.least_possible_cell()        hypo_index = np.where(draft.sudoku[y][x] == 1)        for index in hypo_index[0]:            new_draft = self.propose_hypothesis(y, x, index)            new_draft.constrain(sudoku)        return
    def constrain(self, sudoku):        """constrain the possibliity"""        result = self.depletion_last_number()        if not result:            return        finish = self.finish_check()        if finish:            print('find 1 solution.')            self.add_solution(sudoku)            return        self.backtrack(sudoku)        return
導入計時器，運行程序
看看能不能成功解決問題
puzzle = '001039000095600000006000780708450900000970305100000000000800020002000400900000500's = Sudoku()s.start_puzzle(puzzle)s.print_sudoku()
draft = Draft()draft.initiation(s)draft.constrain(s)
s.print_answers()
列印結果如下：
秒解，完美，撒花~
最後：
代碼已上傳全球最大同性交友網站GitHub（並不是）
https://github.com/artsuki/Sudoku-Solver