完成数独的算法 python,如何用python写一个数独程序
最近突然对数独感兴趣，玩了好几天。慢慢摸索出了一些解题规律，想知道能否通过代码自动化来实现。我在五一假期试着写了一些代码，效果还可以，至少比一些网上教程慢不了多少，所以放在这里和大家分享。
由于我是Python的新手，许多语句可能不够简洁。请原谅我。
完整的代码可以在github link:https://github.com/linking9230/sudoku.git找到
一、数独输入我准备了两套数独题作为测试，一套是难度，一套是专家难度。
困难：
专家：
我把数据放到一个CSV文件里，空格用0代替，方便阅读和识别。
第二，实现数独的代码大家应该都很清楚，就是每个格子的值是1-9中的一个，不能在行、列、九宫格中重复。这个游戏的难点在于每个单元格中可以填充的数字很多，这就使得我们必须找到正确的数字。
当我真的在玩的时候，我有很多技巧可以相对快速地找到正确的数字。但是对于编程来说，代码的优势在于计算速度快。因此，利用穷举思想可以快速找到正确的数字。
所以，我的第一个想法是用递归循环来解决问题。
——————————————————————————————————————
首先，我需要得到一个可以在任何单元格中填充的值的列表。代码如下：
def para(I):r=I//9 c=I % 9 RR=r//3 Cr=c//3 rr_d=RR * 3 3 cr_d=Cr * 3 Cr _ u=Cr * 3 3 return r，c，rr_d，rr_u，cr_d，cr_u def ql(m，i): f_l=[0，1，2，3，4，5，6，7，8，9] r，c，RR _ d，rr_u，cr_d，Cr _ dflatten()))q _ l=[x for x in f _ l if x not in a]返回q _ l，r，c第一个函数的目的是将99的数独矩阵展开成811的一维列表，方便我循环。利用para函数可以从一维链表的索引返回9*9矩阵的参数，得到单元格所在九宫格的范围(rr_d，rr_u，cr_d，cr_u为九宫格的上下限)。
第二个功能也很好理解。我把行、列、九宫格中的值全部收集起来，用一个集合来复制，这样剩下没有出现的数字就是这个单元格中可以选择的值，以列表的形式返回。
——————————————————————————————————————
然后，你可以通过递归循环来解决问题(我后来才知道，这个递归循环，其实就是深度优先循环，或者DFS算法，也是一招)。
DEF (m，n，I，l，flag):# m:matrix # n:flatten matrix # I:第I个单元格#l:最后一个空单元格的位置if flag==0: for j in range (i，l 1): if n [j]==0: break q _ l，r j) if len(q_l)==0: flag=-1返回flag if j==l and len(q_l)1: flag=-1返回q _ l中t的标志：m[r， c]=t k=j1ifk==L1:flag=1 return flag else:flag=0 flag=DG(m，n，k，l，flag)if flag==1:break if flag=-1:m[r，c]=0 return flag if flag==1:return flag这样在列表中循环，首先选择第一个数字填入矩阵，然后找到下一个要填入的单元格，同样获取列表，然后选择第一个值填入。
当然，你这样填，有很大概率会出问题。一旦出现错误，将会发生的情况是，在空单元格中，可填充值的列表为none。当这种情况发生时，我们停止递归，返回到上一级，选择下一个数字来填充上一个空单元格的列表，然后继续递归循环。如果已经尝试了前面的空单元格的所有可填充列表，并且在下一级仍有错误，则返回到上一级，选择列表中的下一个可选值，依此类推。
之后，我们必须能够在最后选择适当和正确的值，以便递归可以顺利进行，直到填充最后一个单元格。理论上，在最后一个单元格，它的可填列表中一定只剩下一个数字，所以我们在这里可以判断，一旦它的可填列表大于1，就说明之前填的数字是错的，需要回到上一级。
在这个过程中，我用一个flag参数来控制程序是返回上一级还是继续下一级循环。Flag=-1表示此时有错误，所以不继续循环，返回上一级。当flag=0时，继续递归循环。当flag=1时，表示所有数据都已正确填写，任务完成，无需继续递归。
在函数中，我返回flag来将下一级的决策发送回上一级。这也是debug的试错。如果不是return，上一级的标志不会改变，永远是0。
还有一点很重要，当第k个单元格的可填充值列表循环完成后，标志仍然是-1。当需要返回到第k-1个单元格时，必须将第k个单元格的编号改为0，否则将保留列表中的最后一个编号，从而导致错误。
最后，将上述内容整合到一个求解函数中。
Def solver 1 (m，n): #在reversed中为I寻找最后一个空单元格(range (1，81)):if n[I]==0:l=I break flag=0i=0 flag=DG(m，n，I，l，flag)return m的困难版本的运算时间为0.045秒。
——————————————————————————————————
完成这一步后，我开始思考如何进一步提高算法的速度。当然，我不懂那些高级的编程技巧。我能改进的就是引入一些人为的先验技能。
查找列表中只有一个项目的空间。
这个操作往往是我实际数独游戏的第一步。由于周围有数字的单元格的影响，有些空格只能用一个数字来填充，而那个数字必须是解。代码如下：def wy (m，n):flag=0 for I in range(81):if n[I]==0:q _ l，r，c=ql (m，i) if len (q _ l)==1: m [r，c]=q _ l .当再也找不到新的唯一值空间时，开始上述深度遍历循环。
主要功能代码如下：
def solver2(m，n): flag=1 while flag==1: m，n，flag=wy(m，n) l=0 for i in reversed(range(1，81)): if n[i]==0: l=i break if l！=0: flag=0i=0flag=DG (m，n，I，l，flag) RETURN M运行后，难度版的运行时间为0.021秒，而专家版的运行时间为5.15秒。
————————————————————————————————————
找到可填写列表中的唯一项目。
这个手法有点高深，但不难理解。在一行中，假设有多个空格，每个空格的可填写值是一个列表，比如[1，3，5]，[1，3，6，9]，[3，6，9]。在这种情况下，我们可以看到数字1、3、6和9可能都出现在多个空格中，但数字5只能出现在第一个空格中。因此，我们可以判断第一个空格应该填数字5。
同样的判定，也能适用在一列中，或者一个九宫格中。因此就有了如下的算法：def dq_l(m，n):dql={ } for I in range(81):if n[I]==0:q _ l，r，c=ql(m，I)dql[I]=q _ l返回dql #检查一行中所有可用的列表并查找只存在于一个单元格中的值def h_c(m，n): flag=0 dql=dq_l(m，n)for I in range(9):la=[]k _ l=[x for x in range(x flag=1 break dql={ } return m，n，flag #检查一列中所有可用的列表并查找只存在于一个单元格中的值def v_c(m，n): flag=0 dql=dq_l(m，n)for I in range(9):la=[]k _ l=[x for x in range(I，73 i，9)if x in dql .keys()]for k in k _ l:la=dql[k]CT=Counter(la)lb=[]for j，v in return m，n，flag #检查一个正方形中的所有可用列表，并查找只存在于一个单元格中的值def n_c(m，n): flag=0 dql=dq_l(m，n) c_l=[x for x in range(0，9，3)] [x for x in range(27，36，3)] [x for x in range(54，63，3)]for I in range(9):la=[]u=c _ l[I]n _ l=[x for x in range(x for j，v in CT .items():如果v==1:lb。追加(j)for t in lb:for k _ l:if t in dql[k]:r，c，_，_，_，_=para(k) n[k]=t m[r，c]=t k _ l . remove(k)flag=1 break dql={ } return m，n，flag在上述代码中，我先是建立了一个数据查询语言函数，目的是将所有空格的可填值做成一个字典，字典的键是空格的次序，值是列表。
接着，在h_c函数中，我逐行进行检查。先获取行中所有空格的位置，在数据查询语言字典中，将所有空格的列表集合起来，并使用计数器函数进行统计，找到仅出现一次的数字。一行中有可能会出现不止一个出现次数为一的数字，因此获得的是一个列表。那么在列表中循环，反向去找到该数字对应的空格，将该数字在矩阵中填入即可。
同时要注意，对于同一行有多个唯一值的情况，每循环一个数，就要将该数从列表中删除，避免臭虫。
v_c为逐列检测，北卡罗来纳州为逐个单元格检测。由于每一次填入值都会对其他单元格产生影响，因此我们在主函数中也是用循环，并利用旗来调控。当再也找不到唯一值时，再使用深度优先搜索循环。
def solver3(m，n): flag=1 while flag==1: m，n，flag=h_c(m，n) m，n，flag=v_c(m，n) m，n，flag=n_c(m，n) l=0 for i in reversed(range(1，81)): if n[i]==0: l=i break if l！=0: i=0标志=0标志=dg(m，n，I，l，标志)返回m困难版的运行时间为0.026秒，专家版的运行时间已经压缩到了2.59秒，节省了将近一半的时间。
总之，只有使用深度遍历才能找到唯一的值。深度遍历来查找行和列中的唯一值。深度遍历难度版0.0450.0210.026，专家版5.1275.4652.628。可以看出，对于相对简单的数独矩阵，第二种方法可以显著提高计算性能，但对于较难的矩阵，第三种方法的改善效果更显著。
以上都是个人摸索的过程，后续优化有思路。欢迎分享。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。