解決數獨問題用人工智慧還是量子計算？

作為一種有趣的棋盤遊戲，數獨誕生100周年之後，它是如何成為計算研究的焦點之一的呢?探索如何使用人工智慧或量子計算機從頭開始創建一個智能數獨求解器。

在深入探究之前，先來了解一下歷史

馬克•布洛赫說:&34;那麼，讓我們來談談著名的數獨遊戲是如何誕生的吧。這個故事可以追溯到19世紀末，起源於法國。法國日報《世紀報》(Le Siecle)發布了一款9x9大小的猜謎遊戲，它需要算術運算而不是邏輯運算，它的數字是兩位數，而不是1- 9。它的遊戲性質與數獨遊戲(Sudoku)類似，即把橫排、列和對角線的數字相加，也會得到相同的數字。1979年，退休的建築師和puzzler Howard Garns被認為是現代數獨遊戲的創造者，該遊戲以數字地名的名義首次在戴爾雜誌上發表。1986年，日本一家名為Nikoli的拼圖公司首次以Sudoku的名字出版了這個拼圖。

在解決數獨遊戲的問題框架

數獨是一個約束滿足問題(CSP)的真實例子，因為變量集、域集和約束集都是有限的。我們必須在一個9x9表中輸入1-9之間的數字，這樣每一行、每列和每3x3子表中的數字都只包含一個數字。 Sudoku也存在另一種變化，即Diagonal Sudoku，它在表對角線的每個對角線中都規定了一組額外的約束，每個數字必須準確地具有一次特徵。 我們知道約束滿足域，最優解必須滿足所有約束，或更具體地說，它應該遵守遊戲規則。 最優解將滿足集合中的所有約束，從而解決難題。

計算上，可以用非確定性多項式時間（NP）解決求解數獨的約束，因為可以使用一些非常特殊的蠻力算法來解決約束，並且也可以在多項式時間內測試解集的有效性，其中輸入 該問題與多項式長度的一組解有關。 完全解決的數獨就是拉丁方格的示例（如Euler所述，n x n數組填充有n個不同的符號）。 數獨問題可以認為是圖形著色問題，其中我們僅需要使用9種顏色對圖形進行著色，而裸露的字母可以認為是部分顏色。

使用人工智慧算法集滿足約束

計算科學的基本原理是依靠邏輯來滿足某些約束的能力。 在解決數獨問題時，我們必須訓練求解器以尋找除基本規則外的一些特定的獲勝模式。 因此，問題在於系統不僅在盲目地遵循規則，而且在考慮其近期和長期影響的同時做出一些決策。 這些模式稱為啟發式。 類似於巧遇遊戲知識和技巧的專家玩家，僅了解基本規則並不能使他們成為遊戲專家。 因此，當我們開發算法並解決問題時，我們必須牢記有用的啟發式方法，我們還應將其包含在程序中，以使其在獲勝時變得更聰明，更有用。

對於我們的Sudoku Solver，我們將輸入81個數字的序列作為字符串，並用&39;（句號）表示未解決的數字。 為了解決該問題，我們將&34;替換為可以放入該單元格的所有可能數字。

根據數獨的限制，我們不能在任何單元格附近的行，列或3x3子正方形中多次使用一個數字。 在對角數獨的情況下，我們還必須考慮相同的約束。 我們首先用所有可能的數字1到9替換句點。我們使用以下grid_values函數以編程方式進行此操作。

39;ABCDEFGHI&39;123456789&every possible cell combination in the grid.def grid_values(grid): &34;&34;&34; values = [] every_digits = &39; for n in grid: if c == &39;: if already solved, causing it no change. values.append(c) assert len(values) == 81 return dict(zip(boxes, values)) reversing the columns for calculating the Diagonal Units.def make_combinations(m, n): &34;&34;&34; return [x + y for x in m for y in n]row_units = [make_combinations(r, columns) for r in rows]column_units = [make_combinations(rows, c) for c in columns]sub_square_units = [make_combinations(m, n) for m in (&39;, &39;, &39;) for n in (&39;,&39;,&39;)]diagonal_1_units = [[rows[i]+columns[i] for i in range(len(rows))]]diagonal_2_units = [[rows[i]+columns_reversed[i] for i in range(len(rows))]]diagonal_units = diagonal_1_units + diagonal_2_unitsall_units = row_units + column_units + square_units + diagonal_unitsunits = dict((b, [u for u in all_units if b in u]) for b in boxes)peers = dict((b, set(sum(units[b], [])) - {b}) for b in boxes)def eliminate(values): &34;&34;&34; solved_cells = [box for box in values.keys() if len(values[box]) == 1] 39;s only one digit for box in solved_cells: value_at_cell = values[box] check for the cell&39;& return the modified values dictionary.

因此，在滿足這些約束的同時，有時我們會遇到一些只能放置一個數字的單元格，但除該數字外，其他數字對於該特定單元格都不再可行。 我們首先要填寫這些內容。 有了適當的解決方案。 我們稱此為&34;，它是解決數獨網格單元的最簡單的啟發式方法。

def only_choice(values): &34;&34;&34; for unit in all_units: 39;123456789& if there exists only a single cell in the unit which is not solved values[to_be_filled[0]] = digit 34;&34; If there are two unsolved cells in a same unit exist such that it can only be filled by only two specific digits, then those two digits can be safely removed from all other cells in the same unit. &34;&confimed Naked Twins for twin in twins: unit1 = twin[0] unit2 = twin[2] peers1 = set(peers[unit1]) peers2 = set(peers[unit2]) common_peers = peers1 & peers2 39;& Erasing the values. return values

現在，我們嘗試通過重複應用這三個約束滿足算法並檢查它是否卡住並且無法進一步減少，來儘可能地減少難題。 我們通過使用reduce_puzzle函數以編程方式執行此操作。 我們要做的是在for循環中調用前三個函數，並在網格值的輸入和輸出序列中的已解決單元數相同時終止該函數，這意味著不能再進一步減小它 僅約束滿足算法。

def reduce_puzzle(values): &34;&34;&34; solved_values = [unit for unit in values.keys() if len(values[unit]) == 1] boolean flag to determine the end of loop while not stuck: prev_solved_values = len([unit for unit in values.keys() if len(values[unit]) == 1]) applying Elimination CSP values = only_choice(values) applying Naked Twins CSP after_solved_values = len([unit for unit in values.keys() if len(values[unit]) == 1]) stuck = after_solved_values == prev_solved_values if there& return the reduced grid values.

如果數獨網格仍未通過約束滿足問題解決，則部分解決方案將到達輸出，其中一些單元格仍將分配給某些可能的值。 在這種情況下，我們要做的是使用搜索樹搜索那些位置中的最佳數字集。 我們使用深度優先搜索（DFS）算法遍歷搜索樹。 因此，基本上，使用DFS，我們用相同的網格創建了幾個實例，並為每個尚未解決的單元嘗試了不同的可能分配。 我們遞歸地要求CSP算法根據搜索結果減少網格。 我們以編程方式實現它，如下所示：

def search(values): &34;&34;&34; values = reduce_puzzle(values) 34;Sudoku Problem Solved!&34;&34; Display the values as a 2-D grid. Input: The sudoku in dictionary form &34;&39;+&39;-&39;&39;|&39;36&39;&39;CF&34;__main__&39;2.............62....1....7...6..8...3...9...7...6..4...4....8....52.............3&34;量子模擬退火&34;組合&34;{row}, {col}_{digit}&39;r&39; &34;Error in row&34;Error in column&39;Error in sub-square&34;__main__": main()

就是這樣。 我們已經成功實現了兩種智能解決方案，其中一種使用經典計算，並且使用了功能非常強大的人工智慧啟發式算法，甚至可以解決對角數獨網格。 第二種方法使用異步混合啟發式採樣器，該採樣器也恰好使用絕熱量子計算模型的模擬退火來將約束滿足問題轉換為二進位二次模型以對其進行採樣，從而獲得最佳採樣解。

作者：Swastik Nath

deephub翻譯組