python十种算法（最难数独不过如此）

算法是编程的核心，是计算机解决问题的方法流程，简单说来，算法就是解决问题的步骤。如果用我们熟知的事物来类比，算法就像是菜谱，按照正确的顺序遵从这些步骤做菜，做出的菜会很美味。同样的道理，计算机按照算法描述的流程来执行程序，会得出美妙的计算结果。

学习Python编程不仅仅是学习Python编程语言本身，计算机算法也同样的重要。计算机语言和技术日新月异，但万变不离其宗的永远是算法。算法就是编程的内功、精髓。因此，要想学好编程，掌握算法知识必不可少。

易嘉编程趣味算法系列将基于Python3为各位同学讲解日常工作、生活和学习中常用的算法。一起来看一个实际的问题场景，到底怎样巧妙地利用算法解决场景中的问题呢？

Part.1

问题场景：

小明的爷爷喜欢读报纸，更喜欢钻研报纸上的数独题，一天，小明爷爷对报纸上一个标题为世界上最难的数独题发起挑战。

这个数独题是芬兰数学家因卡拉花费3个月时间设计出来的，号称世界上迄今难度最大的数独游戏，而且只有一个答案。因此卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。

现在该如何通过Python编程快速准确地解决这个问题呢？

首先，分析问题，明确问题会用到的知识，并设计解决问题的步骤；

其次，找出解决步骤对应的算法，编写程序代码来实现这个算法；

最后，运行程序代码，即可得出结果。

Part.2

分析思路：

解答这个数独题，那么我们最应该做的是先了解数独的游戏规则。

这题正好是一个以9宫数独题，在9阶方阵中，包含了81个小格（九列九行），其中又再分成九个小正方形（称为宫），每宫有九小格。数独（sudoku）是一种在宫格里面填数的小游戏，标准数独的规则一般都只有三点：

• 每行内的数字为1-9且不重复；
• 每列内的数字为1-9且不重复；
• 每宫内的数字为1-9且不重复。

所以，做这个数独题的时候就需要我们填入的数字符合数独的游戏规则。

做数独题，最常用的方法就是尝试法，一个数一个数的去尝试，如果填入的数字不符合数独规则就换一个数去试，如果所有的数都不符合时，就需要回退到上一步，将上一步的数字换掉，重新进行新一轮的尝试。

这就好像是在走迷宫一样，没有地图，没有引导，面对每一个岔路口都只能以尝试探索的方式深入，进而找到出口，在这个尝试探索的过程中，一旦发现线路不对，就需要返回岔路口，一旦发现当前岔路口都不能走，则需要返回上一岔路口，重新选择路线去尝试。

实际上这个解题思路就是我们计算机算法中的回溯算法.

算法：回溯算法（Backtracking algorithm）

回溯算法，又称试探法，选优搜索法。回溯算法的核心思想刚才已经阐述了。能够应用回溯算法解决的问题大都具备以下特点：

• 问题的答案有多个元素，且它至少有一个解；
• 问题需要满足一些约束条件（如：数独规则约束）；
• 寻找答案的方式在每一步相同。

回溯算法是在尝试过程中，逐步构建最终的答案。

Part.3

Python代码实现 :

程序运行结果：

答案填在原题中就是：

回溯算法实质上一种深度优先的算法，许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

正如上例，在回溯算法面前，号称世界上最难的数独题也不过如此，轻轻松松就能得到解决。怎么样？是不是感觉算法真的很强大？

易嘉编程后续将会和大家分享更多的Python算法趣味例子，一起进步。

想了解更多Python算法的朋友可以关注我们易嘉编程yjbc88888888。