| 使用python解数独并给出所有可能解 | 您所在的位置：网站首页 › 数独解题答案是唯一的吗 › 使用python解数独并给出所有可能解 |
使用python解数独并给出所有可能解
|
文章目录
一、两种数独1. 只有唯一解题过程的数独2. 存在多种解题过程的数独
二、解题步骤1.获得数独2.按照上述规律创建某个数字temp的可能性表3.模拟逻辑推断选择最适合放置数字的行/列/块4. 解决只有唯一解题过程的数独5. 解决可能有多种解题过程的数独
总结
本文介绍了如何参照人类逻辑和适当遍历利用python解决数独 一、两种数独 1. 只有唯一解题过程的数独既根据“一行中的该数字唯一，一列中的该数字唯一，一个3*3的小块中的该数字唯一”的规律能够得出在某行某列某块中该数字唯一能放置的地方并放置，重复此过程进而解完的数独，可能部分放置的先后有差，但每步都能确定一个格子应该放什么。 2. 存在多种解题过程的数独在尝试唯一解的过程中，发现无法按照上述规则进行下一步解。往往情况是对于所有数（ 1~9 ）而言，每行每列每块都有不止一个可能放置的地方，这时需要挨个尝试这些地方，得出最终解，而最终解也可能有多个。 二、解题步骤 1.获得数独定义一个9*9的二维列表list99来表示数独：0表示空格子 list99=[[0,0,0,0,0,0,5,0,0], [0,0,0,0,4,0,0,0,3], [0,8,9,0,1,0,0,0,0], [0,0,6,0,0,0,0,1,0], [0,0,0,0,0,5,0,0,0], [0,9,0,2,0,3,0,0,0], [0,0,0,0,0,6,0,0,0], [3,0,2,0,0,0,0,0,0], [0,0,0,0,9,0,0,8,0]] 2.按照上述规律创建某个数字temp的可能性表new99（）创建一个全为0的9*9列表， 遍历81个格子，如果在list99中该行/该列/该块temp出现的次数多于0次（意味着该格子不可能填这个数字），将全为0的列表的该格子值0改为1表示改格子已占有，我将这个列表称为可能性图，wherex（）将会返回list99关于数字temp的可能性图 部分代码如下： show_times_in_col/row/square（）将会返回数字temp在list99中某行/列/块出现的次数。 #查看数字X(temp)在九宫格（list99）里可能出现的地方，返回可能性九宫格 def wherex(temp,list99): list00=new99() #行列查重 for i in range(9): for j in range(9): if(show_times_in_col(list99,j,temp)!=0 or show_times_in_row(list99,i,temp)!=0 or list99[i][j]!=0): list00[i][j]=1 # 区块查重 for i in range(1,4): for j in range(1,4): if(show_times_in_square(list99,i,j,temp)!=0): for ii in range(i*3-3,i*3): for jj in range(j*3-3,j*3): list00[ii][jj]=1 return list00
需要判断出这种“某行/列/块中只有一个0的情况”，为了便于后面解决存在多种解法的数独，该方法返回的是 在某个数的可能性表中的某行/列/块mostpro_exa_num_post中有最少的0最少有mostpro_exa_num_pro个0这个数mostpro_exa_num（如果mostpro_exa_num为0，代表数独已解完或数独遇到了死解，这个将会在后面解决多种解法的数独中用到） show_post_in_col/row/square将会以二维列表的形式返回数字0在该i行/列/块的绝对坐标（[行，列], [行，列]…） 核心代码如下： def show_mostpro_exa_num(list99): mostpro_exa_num=0 mostpro_exa_num_pro=9 mostpro_exa_num_post=[] for anum in range(1,10): prolist=wherex(anum,list99) for i in range(9): if(show_times_in_col(prolist,i,0)!=0 and show_times_in_col(prolist,i,0) |
上面是原数独，下图为原数独而言数字3的可能性图，观察得知第三行只有一个地方能填3，下一步即是将3填入list99，下面是让程序模拟这种逻辑推断 
【本文地址】
公司简介
联系我们