二进制数独游戏规则和玩法视频技巧，解决数独问题用人工智能还是量子计算?

二进制数独游戏规则和玩法视频技巧

##二进制数独游戏规则和玩法视频技巧

在探索数字世界的奥秘时，我们经常会遇到一些独特而迷人的游戏。今天，我们将深入探讨二进制数独——一种结合了经典数独和二进制计算的智力挑战。通过本篇内容，你将了解到这一游戏的规则、技巧以及如何通过视频学习来提升你的解题能力。

###二进制数独的基础规则

1.**棋盘布局**：与经典数独类似，二进制数独通常在9x9的棋盘上进行。每个格子可以填入0或1，代表二进制的两种状态。

2.**区域限制**：棋盘被分为不同的区域，每个区域的数字之和必须是二进制数，且满足特定的二进制数值。

3.**行列限制**：每一行和每一列也必须是有效的二进制数。

4.**数字重复性**：每个数字（0或1）在每行、每列以及每个指定区域内必须出现一次且仅一次。

###视频技巧概览

为了帮助你更快地掌握二进制数独，我们收集了一些关键的视频技巧供你参考。

二、数独怎么玩

数独的玩法规则如下：

具体规则：

1、数独棋盘是一个9x9的方阵，被分成3x3的九个小格子，每个小格子内再分为3x3的九个小方格子，可以使用纸和笔或者电脑程序进行游戏。

2、在初始状态下，数独棋盘中的某些单元格已经被填入了一个数字，称为“已知格”，通常使用数字1至9表示已知格，未知格则用空白或者“0”表示。

3、玩家需要用1~9的数字填入每个空白格子，要求每个数字在同一行、同一列和同一宫格中都只能出现一次，直到将整个数独棋盘填完为止。

4、数独的难度取决于已知格的数量和位置，更多的已知格会使游戏变得更容易。

5、在游戏过程中，需要不断尝试填写数字，直到找到符合要求的数字，这需要一定的逻辑推理能力和耐心。

6、数独棋盘中的每个空白格子只能填入一个数字。如果填入的数字在同一行、同一列或者同一宫格中已经出现，那么就需要重新填写。

7、当玩家将数独棋盘填写完整并符合要求时，即为游戏胜利。

数独简介：

数独是一种逻辑推理游戏，通过将数字填入9x9的棋盘中的空白格子，使每一行、每一列和每一个九宫格内的数字都不重复，最终完成整个棋盘的填写。

数独意义：

1、锻炼逻辑思维能力：

数独需要玩家通过逻辑推理和排除法来填写数字，培养了玩家的逻辑思维能力和问题解决能力。玩家需要观察、分析和判断，从而提升思维的灵活性和逻辑思考的能力。

2、提高注意力和集中力：

数独需要玩家对整个棋盘进行细致的观察，并且注意到每一个单元格的变化和可能的数字选择。通过数独游戏，可以提高玩家的注意力和集中力，培养耐心和细致观察的能力。

3、放松心灵，减轻压力：

数独可作为一种休闲娱乐活动，让人们暂时放下繁忙的生活和工作压力，专注于填写数字的乐趣。这种关注于问题解决的过程，有助于放松心灵，并且使人感到一种成就和满足感。

4、培养耐心和毅力：

数独是一项需要耐心和毅力的游戏，填写整个棋盘可能需要一些时间和多次尝试。通过坚持不懈地解决数独难题，可以培养玩家的耐心和毅力，学会面对挑战并努力解决问题。

解决数独问题用人工智能还是量子计算？

原创2020-09-2409:07·deephub

作为一种有趣的棋盘游戏，数独诞生100周年之后，它是如何成为计算研究的焦点之一的呢?探索如何使用人工智能或量子计算机从头开始创建一个智能数独求解器。

在深入探究之前，先来了解一下历史

马克?布洛赫说:"历史被称为学科之母。"那么，让我们来谈谈著名的数独游戏是如何诞生的吧。这个故事可以追溯到19世纪末，起源于法国。法国日报《世纪报》(LeSiecle)发布了一款9x9大小的猜谜游戏，它需要算术运算而不是逻辑运算，它的数字是两位数，而不是1-9。它的游戏性质与数独游戏(Sudoku)类似，即把横排、列和对角线的数字相加，也会得到相同的数字。1979年，退休的建筑师和puzzlerHowardGarns被认为是现代数独游戏的创造者，该游戏以数字地名的名义首次在戴尔杂志上发表。1986年，日本一家名为Nikoli的拼图公司首次以Sudoku的名字出版了这个拼图。

在解决数独游戏的问题框架

数独是一个约束满足问题(CSP)的真实例子，因为变量集、域集和约束集都是有限的。我们必须在一个9x9表中输入1-9之间的数字，这样每一行、每列和每3x3子表中的数字都只包含一个数字。Sudoku也存在另一种变化，即DiagonalSudoku，它在表对角线的每个对角线中都规定了一组额外的约束，每个数字必须准确地具有一次特征。我们知道约束满足域，最优解必须满足所有约束，或更具体地说，它应该遵守游戏规则。最优解将满足集合中的所有约束，从而解决难题。

计算上，可以用非确定性多项式时间（NP）解决求解数独的约束，因为可以使用一些非常特殊的蛮力算法来解决约束，并且也可以在多项式时间内测试解集的有效性，其中输入该问题与多项式长度的一组解有关。完全解决的数独就是拉丁方格的示例（如Euler所述，nxn数组填充有n个不同的符号）。数独问题可以认为是图形着色问题，其中我们仅需要使用9种颜色对图形进行着色，而裸露的字母可以认为是部分颜色。

使用人工智能算法集满足约束

计算科学的基本原理是依靠逻辑来满足某些约束的能力。在解决数独问题时，我们必须训练求解器以寻找除基本规则外的一些特定的获胜模式。因此，问题在于系统不仅在盲目地遵循规则，而且在考虑其近期和长期影响的同时做出一些决策。这些模式称为启发式。类似于巧遇游戏知识和技巧的专家玩家，仅了解基本规则并不能使他们成为游戏专家。因此，当我们开发算法并解决问题时，我们必须牢记有用的启发式方法，我们还应将其包含在程序中，以使其在获胜时变得更聪明，更有用。

对于我们的SudokuSolver，我们将输入81个数字的序列作为字符串，并用'。'（句号）表示未解决的数字。为了解决该问题，我们将"。"替换为可以放入该单元格的所有可能数字。

根据数独的限制，我们不能在任何单元格附近的行，列或3x3子正方形中多次使用一个数字。在对角数独的情况下，我们还必须考虑相同的约束。我们首先用所有可能的数字1到9替换句点。我们使用以下grid_values函数以编程方式进行此操作。

#Forthesakeofcaluclationwetakerowsasalphaneumericandcolumnsasnumeric.rows='ABCDEFGHI'columns='123456789'boxes=[r+cforrinrowsforcincolumns]#everypossiblecellcombinationinthegrid.defgrid_values(grid):"""TakeintheUnsolvedSudokuSequenceandreplacestheunsolvedboxesinitiallywithallpossiblevalueswhichcangetintothatcell.Lastlyreturnsadictionarycontainingthevaluesatallcellpositionsalongwithcells."""values=[]every_digits='123456789'forningrid:ifc=='.':#replacingeveryunsolvedvaluewitheverypossiblevalueinitially.values.append(every_digits)else:#ifalreadysolved，causingitnochange.values.append(c)assertlen(values)==81returndict(zip(boxes，values))#returningthesudokugridwithallpossiblecellvalues.

首先在所有未解决的单元格中分配所有可能的值。

现在，我们用1到9之间的所有可能数字替换了未解决的单元格，从数独的基本规则中我们知道，如果数字已经在该行，列和3x3子字段中使用过，我们就不能使用它两次。因此，让我们消除它们，如果我们在未解决的网格中遇到它们时，我们最初已经用所有可能的数字填充了它们。因此，让我们看一下如何使用消除python方法从未解决的单元中消除那些不相关的数字。

columns_reversed=columns[::-1]#reversingthecolumnsforcalculatingtheDiagonalUnits.defmake_combinations(m，n):"""Takesininputofgenerallyiterablesandcreatesallpossiblecombintationoutofthem.args:a:stringiterableb:stringiterablereturn:listofallpossiblecombination."""return[x+yforxinmforyinn]row_units=[make_combinations(r，columns)forrinrows]column_units=[make_combinations(rows，c)forcincolumns]sub_square_units=[make_combinations(m，n)formin('ABC'，'DEF'，'GHI')fornin('123'，'456'，'789')]diagonal_1_units=[[rows[i]+columns[i]foriinrange(len(rows))]]diagonal_2_units=[[rows[i]+columns_reversed[i]foriinrange(len(rows))]]diagonal_units=diagonal_1_units+diagonal_2_unitsall_units=row_units+column_units+square_units+diagonal_unitsunits=dict((b，[uforuinall_unitsifbinu])forbinboxes)peers=dict((b，set(sum(units[b]，[]))-{b})forbinboxes)defeliminate(values):"""Eliminatetheredundantnumbersfromtheunsolvedcellsifthenumberalreadyappearedonceinthepeerofthecurrentcell.Whatwedohereisweerasethatredundantnumberfromtheunsolvedvaluecellsifappearedonce."""solved_cells=[boxforboxinvalues.keys()iflen(values[box])==1]#cellissolvedifthere'sonlyonedigitforboxinsolved_cells:value_at_cell=values[box]#retrievethecurrentvalueatthatcell.forpeerinpeers[box]:#checkforthecell'speersifthevalueappearsagain.values[peer]=values[peer].replace(value_at_cell，'')returnvalues#returnthemodifiedvaluesdictionary.

因此，在满足这些约束的同时，有时我们会遇到一些只能放置一个数字的单元格，但除该数字外，其他数字对于该特定单元格都不再可行。我们首先要填写这些内容。有了适当的解决方案。我们称此为"唯一选择"，它是解决数独网格单元的最简单的启发式方法。

defonly_choice(values):"""IfinordertosatisfytheconstraintsoftheSudokuPuzzlethereisonlyasingleviableoptionwefillintheCellwiththatoptiononlyandtherebyobtainasolveforthecell."""forunitinall_units:#searchingacrossallthevicinityofthecell.fordigitin'123456789':to_be_filled=[cellforcellinunitifunitinvalues[unit]]iflen(to_be_filled)==1:#ifthereexistsonlyasinglecellintheunitwhichisnotsolvedvalues[to_be_filled[0]]=digit#Wefillinthecellwithitsproperanswer.returnvalues

在迄今为止围绕约束满足的过程中，可能会出现以下情况：一个单元中将有两个未解决的像元（考虑行，列和3x3子正方形），其中只能分配两个特定的剩余数。因此，这两个数字可以有效地从同一单元中其他单元格上的可能数字中删除。这种启发式方法称为裸双胞胎。该算法的实现专门制作了网格值的深层副本，并检查了裸胎双胞胎的可行性，即是否存在两个仅能接受两个特定值的未解决像元，如果可行，它将继续进行并从其他两个值中删除这两个值同一单元中的单元格。我们使用如下所示的nude_twins函数以编程方式实现它：

defnaked_twins(values):\t"""\tIftherearetwounsolvedcellsinasameunitexistsuchthatitcanonlybefilledbyonly\ttwospecificdigits，thenthosetwodigitscanbesafelyremovedfromallothercellsinthesameunit.\t"""\ttwins_possible=[unitforunitinvalues.keys()iflen(values[unit])==2]\ttwins=[[unit1，unit2]forunit1intwins_possibleforunit2inpeers[unit1]\t\t\t\t\tifset(values[unit1])==(set(values[unit2]))]#confimedNakedTwins\tfortwinintwins:\t\tunit1=twin[0]\t\tunit2=twin[2]\t\tpeers1=set(peers[unit1])\t\tpeers2=set(peers[unit2])\t\tcommon_peers=peers1peers2#findingtheintersectionbetweenthepeersofthetwonakedtwinelement\t\tforpeerincommon_peers:\t\t\tiflen(values[peer])>1:\t\t\t\tforvalueinvalues[unit1]:\t\t\t\t\tvalues[peer]=values[peer].replace(val，''))#Erasingthevalues.\treturnvalues

现在，我们尝试通过重复应用这三个约束满足算法并检查它是否卡住并且无法进一步减少，来尽可能地减少难题。我们通过使用reduce_puzzle函数以编程方式执行此操作。我们要做的是在for循环中调用前三个函数，并在网格值的输入和输出序列中的已解决单元数相同时终止该函数，这意味着不能再进一步减小它仅约束满足算法。

defreduce_puzzle(values):\t"""\tApplyingthe4ConstraintSatisfactionAlgorithmsuntilitisnotfurtherreducible.\tCheckingiftheNumberofSolvedCellsbetweentheiteration.\t"""\tsolved_values=[unitforunitinvalues.keys()iflen(values[unit])==1]#consideringsolvedcells\tstuck=False#booleanflagtodeterminetheendofloop\twhilenotstuck:\t\tprev_solved_values=len([unitforunitinvalues.keys()iflen(values[unit])==1])#checkpoint1\t\tvalues=eliminate(values)#applyingEliminationCSP\t\tvalues=only_choice(values)#applyingOnlyChoiceCSP\t\tvalues=naked_twins(values)#applyingNakedTwinsCSP\t\tafter_solved_values=len([unitforunitinvalues.keys()iflen(values[unit])==1])\t\tstuck=after_solved_values==prev_solved_values#Gettingoutofloopisthenumberofsolvedcellisstillthesameasthepreviousiteration.\t\t\t\tiflen([unitforunitinvalues.keys()iflen(values[unit])==0]):\t\t\treturnFalse#ifthere'sproblemsintheinternalrepresentationofthesudokugridreturnFalse.\treturnvalues\t\t\t#returnthereducedgridvalues.\t

如果数独网格仍未通过约束满足问题解决，则部分解决方案将到达输出，其中一些单元格仍将分配给某些可能的值。在这种情况下，我们要做的是使用搜索树搜索那些位置中的最佳数字集。我们使用深度优先搜索（DFS）算法遍历搜索树。因此，基本上，使用DFS，我们用相同的网格创建了几个实例，并为每个尚未解决的单元尝试了不同的可能分配。我们递归地要求CSP算法根据搜索结果减少网格。我们以编程方式实现它，如下所示：

defsearch(values):\t"""\tRecursiveDepth-FirstSearch:Ifthesudokugridisnotfurtherreduciblebyconstraintsatisfaction\tafewofthecellswillbeleftwithdifferentoptionsandwithDFSwithsearchfortheoptimal\tvaluesforthoseyet-unsolvedcells.\t"""\tvalues=reduce_puzzle(values)#WecalltheReductionFunctiontoreducethepuzzlefurtherbasedonthesearchresultsacrossiterations.\tifvaluesisFalse:\t\treturnFalse\tifall(len(values[b])==1forbinboxes):\t\tprint("SudokuProblemSolved!")\t\treturnvalues\tm，n=min((len(values[b])，b)forbinboxesiflen(values[b])>1)\tforvalueinvalues[n]:\t\tnew_sudoku=values.copy()\t\tnew_sudoku[n]=value\t\tattempted=search(new_sudoku)\t\tifattempted:\t\t\treturnattempted\t\t

我们使用displaysudoku函数将输入的字符串序列显示为二维9x9Sudoku网格：

defdisplay(values):"""Displaythevaluesasa2-Dgrid.Input:Thesudokuindictionaryform"""width=1+max(len(values[b])forbinboxes)line='+'.join(['-'*(width*3)]*3)forrinrows:print(''.join(values[r+c].center(width)+('|'ifcin'36'else'')forcincols))ifrin'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网格。首先，什么是模拟退火？对于这样的优化问题，我们的想法是使用一些次优启发式算法，并获得最优的启发式算法集以获得最优解。我们在这里使用DWaveAQC模型（糖尿病量子计算）来采样满足前面讨论的约束的最佳解决方案。...

使用DWaveKerberos混合采样器：

在本示例中，我们正在使用DWave随附的混合求解器。它通过运行并行搜索来找出最佳的启发式方法。它是一种混合求解器，因为它同时使用了量子计算和经典的计算特性。它也是一个分解采样器，在处理时使用异步工作流。它包含在DWaveSystems的OceanSDK软件包中。要开始本地开发，请确保您的系统上安装了Python3.5+，然后发出以下命令。

python-mpipinstall--upgradepippipinstalldwave-ocean-sdk

使用二进制二次模型（BQM）进行计算

我们无法构造直接准备将其馈送到QuantumComputers的约束，我们需要一个中间表示来将其馈入。这就是为什么我们将使用BQM的原因，幸运的是，DWaveOceanSDK已经提供了一种称为"组合"的工具，可用于将约束满足问题归结为BQM。首先，顾名思义，二进制二次模型本身就是一个方程系统，它是二次的，用二进制表示。由于计算的复杂性更高，Quantum计算机使用这些计算可以大大加快开发过程。因此，在游戏中，我们决定使用dimod的组合工具，该工具将返回一个二进制二次模型，该模型对于其输入变量和内部变量的k个组合中的每一个均最小。

我们首先从dwave-ocean-sdk导入必要的软件包，并在实际读入SudokuGrid之前进行一些完整性检查。

importdimodimportmathimportsysimportdimod.generators.constraintsimportcombinationsfromhybrid.referenceimportKerberosSamplerdefprettify(row，col，digit):return"{row}，{col}_{digit}".format(row，col，digit)defread_matrix(filename):withopen(filename，'r')asf:all_lines=f.read()lines=[]forlineinall_lines:new_line=line.rstrip()ifnew_line:new_line=list(map(int，new_line.split('')))lines.append(new_line)returnlinesdefsanity_check(matrix):n=len(matrix)m=int(math.sqrt(n))unique_digits=set(range(1，1+n))forrowinmatrix:ifset(row)!=unique_digits:print("Errorinrow"，row)returnfalseforjinrange(n):col=[matrix[i][j]foriinrange(n)]ifset(col)!=unique_digits:print("Errorincolumn"，col)subsquare_idx=[(i，j)foriinrange(m)forjinrange(m)]forr_scalarinrange(m):forc_scalarinrange(m):subsquare=[matrix[i+r_scalar*m][j+c_scalar*m]fori，jinsubsquare_idx]ifset(subsquare)!=unique_digits:print('Errorinsub-square'，subsquare)returnTruereturnTrue

现在，我们使用SudokuGrid的行，列和子正方形索引的所有可用变量组合，使用组合工具来创建二进制二次模型。

defmain():iflen(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)forrowinrange(n):forcolinrange(n):node_digits=[prettify(row，col，digit)fordigitindigits]one_digit_bqm=combinations(node_digits，1)bqm.update(one_digit_bqm)forrowinrange(n):fordigitindigits:row_nodes=[prettify(row，col，digit)forcolinrange(n)]row_bqm=combinations(row_nodes，1)bqm.update(row_bqm)forcolinrange(n):fordigitindigits:col_nodes=[prettify(row，col，digit)forrowinrange(n)]col_bqm=combinations(col_nodes，1)bqm.update(col_bqm)if__name__=="__main__":main()

就是这样。我们已经成功实现了两种智能解决方案，其中一种使用经典计算，并且使用了功能非常强大的人工智能启发式算法，甚至可以解决对角数独网格。第二种方法使用异步混合启发式采样器，该采样器也恰好使用绝热量子计算模型的模拟退火来将约束满足问题转换为二进制二次模型以对其进行采样，从而获得最佳采样解。

作者：SwastikNath

deephub翻译组