作为一种有趣的棋盘游戏，数独诞生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翻译组