作為一種有趣的棋盤游戲，數獨誕生100周年之后，它是如何成為計算研究的焦點之一的呢?探索如何使用人工智能或量子計算機從頭開始創建一個智能數獨求解器，
在深入探究之前，先來了解一下歷史
馬克?布洛赫說:“歷史被稱為學科之母，”那么，讓我們來談談著名的數獨游戲是如何誕生的吧，這個故事可以追溯到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個數字的序列作為字串，并用’，’（句號）表示未解決的數字， 為了解決該問題，我們將“，”替換為可以放入該單元格的所有可能數字，
根據數獨的限制，我們不能在任何單元格附近的行，列或3x3子正方形中多次使用一個數字， 在對角數獨的情況下，我們還必須考慮相同的約束， 我們首先用所有可能的數字1到9替換句點，我們使用以下grid_values函式以編程方式進行此操作，
# For the sake of caluclation we take rows as alphaneumeric and columns as numeric.
rows = 'ABCDEFGHI'
columns = '123456789'
boxes = [r + c for r in rows for c in columns] #every possible cell combination in the grid.
def grid_values(grid):
"""
Take in the Unsolved Sudoku Sequence and replaces the unsolved boxes initially with all
possible values which can get into that cell. Lastly returns a dictionary containing the
values at all cell positions along with cells.
"""
values = []
every_digits = '123456789'
for n in grid:
if c == '.': # replacing every unsolved value with every possible value initially.
values.append(every_digits)
else: # if already solved, causing it no change.
values.append(c)
assert len(values) == 81
return dict(zip(boxes, values)) #returning the sudoku grid with all possible cell values.
首先在所有未解決的單元格中分配所有可能的值，
現在，我們用1到9之間的所有可能數字替換了未解決的單元格，從數獨的基本規則中我們知道，如果數字已經在該行，列和3x3子欄位中使用過，我們就不能使用它兩次， 因此，讓我們消除它們，如果我們在未解決的網格中遇到它們時，我們最初已經用所有可能的數字填充了它們， 因此，讓我們看一下如何使用消除python方法從未解決的單元中消除那些不相關的數字，
columns_reversed = columns[::-1] #reversing the columns for calculating the Diagonal Units.
def make_combinations(m, n):
"""
Takes in input of generally iterables and creates all possible combintation out of them.
args:
a: string iterable
b: string iterable
return : list of all possible combination.
"""
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 ('ABC', 'DEF', 'GHI')
for n in ('123','456','789')]
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_units
all_units = row_units + column_units + square_units + diagonal_units
units = 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):
"""
Eliminate the redundant numbers from the unsolved cells if the number already appeared once
in the peer of the current cell.
What we do here is we erase that redundant number from the unsolved value cells if appeared once.
"""
solved_cells = [box for box in values.keys() if len(values[box]) == 1] # cell is solved if there's only one digit
for box in solved_cells:
value_at_cell = values[box] # retrieve the current value at that cell.
for peer in peers[box]: # check for the cell's peers if the value appears again.
values[peer] = values[peer].replace(value_at_cell, '')
return values # return the modified values dictionary.
因此，在滿足這些約束的同時，有時我們會遇到一些只能放置一個數字的單元格，但除該數字外，其他數字對于該特定單元格都不再可行， 我們首先要填寫這些內容， 有了適當的解決方案， 我們稱此為“唯一選擇”，它是解決數獨網格單元的最簡單的啟發式方法，
def only_choice(values):
"""
If in order to satisfy the constraints of the Sudoku Puzzle there is only a single viable option
we fill in the Cell with that option only and thereby obtain a solve for the cell.
"""
for unit in all_units: #searching across all the vicinity of the cell.
for digit in '123456789':
to_be_filled = [cell for cell in unit if unit in values[unit]]
if len(to_be_filled) == 1: # if there exists only a single cell in the unit which is not solved
values[to_be_filled[0]] = digit # We fill in the cell with its proper answer.
return values
在迄今為止圍繞約束滿足的程序中，可能會出現以下情況：一個單元中將有兩個未解決的像元（考慮行，列和3x3子正方形），其中只能分配兩個特定的剩余數， 因此，這兩個數字可以有效地從同一單元中其他單元格上的可能數字中洗掉， 這種啟發式方法稱為裸雙胞胎， 該演算法的實作專門制作了網格值的深層副本，并檢查了裸胎雙胞胎的可行性，即是否存在兩個僅能接受兩個特定值的未解決像元，如果可行，它將繼續進行并從其他兩個值中洗掉這兩個值 同一單元中的單元格， 我們使用如下所示的nude_twins函式以編程方式實作它：
def naked_twins(values):
"""
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.
"""
twins_possible = [unit for unit in values.keys() if len(values[unit]) == 2]
twins = [[unit1, unit2] for unit1 in twins_possible for unit2 in peers[unit1]
if set(values[unit1]) == (set(values[unit2]))] #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 #finding the intersection between the peers of the two naked twin element
for peer in common_peers:
if len(values[peer]) > 1:
for value in values[unit1]:
values[peer] = values[peer].replace(val, '')) # Erasing the values.
return values
現在，我們嘗試通過重復應用這三個約束滿足演算法并檢查它是否卡住并且無法進一步減少，來盡可能地減少難題， 我們通過使用reduce_puzzle函式以編程方式執行此操作， 我們要做的是在for回圈中呼叫前三個函式，并在網格值的輸入和輸出序列中的已解決單元數相同時終止該函式，這意味著不能再進一步減小它 僅約束滿足演算法，
def reduce_puzzle(values):
"""
Applying the 4 Constraint Satisfaction Algorithms until it is not further reducible.
Checking if the Number of Solved Cells between the iteration.
"""
solved_values = [unit for unit in values.keys() if len(values[unit]) == 1] # considering solved cells
stuck = False #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]) #checkpoint 1
values = eliminate(values) # applying Elimination CSP
values = only_choice(values) # applying Only Choice CSP
values = naked_twins(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 # Getting out of loop is the number of solved cell is still the same as the previous iteration.
if len([unit for unit in values.keys() if len(values[unit]) == 0]):
return False # if there's problems in the internal representation of the sudoku grid return False.
return values # return the reduced grid values.
如果數獨網格仍未通過約束滿足問題解決，則部分解決方案將到達輸出，其中一些單元格仍將分配給某些可能的值， 在這種情況下，我們要做的是使用搜索樹搜索那些位置中的最佳數字集， 我們使用深度優先搜索（DFS）演算法遍歷搜索樹， 因此，基本上，使用DFS，我們用相同的網格創建了幾個實體，并為每個尚未解決的單元嘗試了不同的可能分配， 我們遞回地要求CSP演算法根據搜索結果減少網格， 我們以編程方式實作它，如下所示：
def search(values):
"""
Recursive Depth-First Search: If the sudoku grid is not further reducible by constraint satisfaction
a few of the cells will be left with different options and with DFS with search for the optimal
values for those yet-unsolved cells.
"""
values = reduce_puzzle(values) # We call the Reduction Function to reduce the puzzle further based on the search results across iterations.
if values is False:
return False
if all(len(values[b]) == 1 for b in boxes):
print("Sudoku Problem Solved!")
return values
m, n = min((len(values[b]), b) for b in boxes if len(values[b]) > 1)
for value in values[n]:
new_sudoku = values.copy()
new_sudoku[n] = value
attempted = search(new_sudoku)
if attempted:
return attempted
我們使用display sudoku函式將輸入的字串序列顯示為二維9x9 Sudoku網格：
def display(values):
"""
Display the values as a 2-D grid.
Input: The sudoku in dictionary form
"""
width = 1 + max(len(values[b]) for b in boxes)
line = '+'.join(['-' * (width * 3)] * 3)
for r in rows:
print(''.join(values[r + c].center(width) + ('|' if c in '36' else '')
for c in cols))
if r in 'CF':
print(line)
return
為了解決數獨序列，我們將上述函式呼叫如下：
if __name__ == "__main__":
diag_sudoku_grid = '2.............62....1....7...6..8...3...9...7...6..4...4....8....52.............3'
values = grid_values(diag_sudoku_grid)
values = reduce_puzzle(values)
values = search(values)
display(values)
輸出如下所示，其中一組演算法已成功計算出答案，
解決數獨作為約束滿足問題的量子方法
現在，我們將嘗試使用“量子模擬退火”解決簡單的Sudoku網格， 首先，什么是模擬退火？ 對于這樣的優化問題，我們的想法是使用一些次優啟發式演算法，并獲得最優的啟發式演算法集以獲得最優解， 我們在這里使用DWave AQC模型（糖尿病量子計算）來采樣滿足前面討論的約束的最佳解決方案，…
使用DWave Kerberos混合采樣器：
在本示例中，我們正在使用DWave隨附的混合求解器， 它通過運行并行搜索來找出最佳的啟發式方法， 它是一種混合求解器，因為它同時使用了量子計算和經典的計算特性， 它也是一個分解采樣器，在處理時使用異步作業流， 它包含在DWave Systems的Ocean SDK軟體包中， 要開始本地開發，請確保您的系統上安裝了Python 3.5+，然后發出以下命令，
python -m pip install --upgrade pip
pip install dwave-ocean-sdk
使用二進制二次模型（BQM）進行計算
我們無法構造直接準備將其饋送到Quantum Computers的約束，我們需要一個中間表示來將其饋入， 這就是為什么我們將使用BQM的原因，幸運的是，DWave Ocean SDK已經提供了一種稱為“組合”的工具，可用于將約束滿足問題歸結為BQM， 首先，顧名思義，二進制二次模型本身就是一個方程系統，它是二次的，用二進制表示， 由于計算的復雜性更高，Quantum計算機使用這些計算可以大大加快開發程序， 因此，在游戲中，我們決定使用dimod的組合工具，該工具將回傳一個二進制二次模型，該模型對于其輸入變數和內部變數的k個組合中的每一個均最小，
我們首先從dwave-ocean-sdk匯入必要的軟體包，并在實際讀入Sudoku Grid之前進行一些完整性檢查，
import dimod
import math
import sys
import dimod.generators.constraints import combinations
from hybrid.reference import KerberosSampler
def prettify(row, col, digit):
return "{row}, {col}_{digit}".format(row, col, digit)
def read_matrix(filename):
with open(filename, 'r') as f:
all_lines = f.read()
lines = []
for line in all_lines:
new_line = line.rstrip()
if new_line:
new_line = list(map(int, new_line.split(' ')))
lines.append(new_line)
return lines
def sanity_check(matrix):
n = len(matrix)
m = int(math.sqrt(n))
unique_digits = set(range(1, 1+n))
for row in matrix:
if set(row) != unique_digits:
print("Error in row", row)
return false
for j in range(n):
col = [matrix[i][j] for i in range(n)]
if set(col) != unique_digits:
print("Error in column", col)
subsquare_idx = [(i, j) for i in range(m) for j in range(m)]
for r_scalar in range(m):
for c_scalar in range(m):
subsquare = [matrix[i + r_scalar * m ][j + c_scalar * m] for i, j in subsquare_idx]
if set(subsquare) != unique_digits:
print('Error in sub-square', subsquare)
return True
return True
現在，我們使用Sudoku Grid的行，列和子正方形索引的所有可用變陣列合，使用組合工具來創建二進制二次模型，
def main():
if len(sys.argv) > 1:
filename = sys.argv[1]
matrix = read_matrix(filename)
n = len(matrix)
m = int(math.sqrt(n))
digits = range(1, n+1)
bqm = dimod.BinaryQuadraticModel({}, {}, 0.0, dimod.SPIN)
for row in range(n):
for col in range(n):
node_digits = [prettify(row, col, digit) for digit in digits]
one_digit_bqm = combinations(node_digits, 1)
bqm.update(one_digit_bqm)
for row in range(n):
for digit in digits:
row_nodes = [prettify(row, col, digit) for col in range(n)]
row_bqm = combinations(row_nodes, 1)
bqm.update(row_bqm)
for col in range(n):
for digit in digits:
col_nodes = [prettify(row, col, digit) for row in range(n)]
col_bqm = combinations(col_nodes, 1)
bqm.update(col_bqm)
if __name__ == "__main__":
main()
就是這樣， 我們已經成功實作了兩種智能解決方案，其中一種使用經典計算，并且使用了功能非常強大的人工智能啟發式演算法，甚至可以解決對角數獨網格， 第二種方法使用異步混合啟發式采樣器，該采樣器也恰好使用絕熱量子計算模型的模擬退火來將約束滿足問題轉換為二進制二次模型以對其進行采樣，從而獲得最佳采樣解，
作者：Swastik Nath
deephub翻譯組
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/125975.html
標籤：其他