python3.6数独问题的解决

作者:Jayshon_Jaa 时间:2022-06-21 20:40:32 

算法比较暴力,直接用穷举的方式一个一个去试,所以程序运行时间会比较长,运行时间视数独而定。
不过从一开始到运行成功,整个过程却是一波三折,设计算法就花了不少时间,然后就是不断地去调试,找bug。刚开始的时候为了省事直接在sudoku类中递归调用blank,但是老哥还是too young too simple,sometimes navie,计算量实在是太大了,后面编译器直接抛出 “RecursionError: maximum recursion depth exceeded while calling a Python object” 超过最大递归深度的错误。在把递归深度改到100000之后,又出现了堆栈溢出问题。当然,解决办法也是相当地暴力:把递归放入while循环中,一旦符合条件就直接exit(0),整个程序直接gg,然后退出结束。
当然,算法还可以再优化一下,可以不用那么暴力,先列出可能的值然后再填入,这样可以大大缩小整个程序的运行时间,但是……懒得优化了,就这样吧,又不是不能用(笑~)。

运行结果:

python3.6数独问题的解决

再试一个其他的数独:

python3.6数独问题的解决

这回就快得多了,11秒就完成了,比第一个数独不知高到哪里去了

代码如下所示:


import copy
import time

t1=time.time()
origin = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]]

class sudoku:
def debug(self): # 调试
for list in origin:
 print(list)
print("\n")

def check_repetition(self,list):#判断表中是否有重复值,0除外
flag=0
for i in range(1,10):
 if list.count(i)>=2:
 return 1
 else:
 flag=flag+1
if flag==9:
 return 0

def check_row(self,row):#检测横向是否有重复值,无则为返回0,有则返回1
list = origin[row] # 横向
r1 = self.check_repetition(list)
if r1 == 0:
 return 0
else :
 return 1

def check_column(self,column):#检测纵向是否重复值,无则为返回0,有则返回1
list = [] # 纵向
for num in origin:
 list.append(num[column])
r2 = self.check_repetition(list)
if r2==0:
 return 0
else:
 return 1

def check_square(self,x,y):#检测九宫格是否有重复值,无则为返回0,有则返回1
x,y=y,x
if x>=9 or y>=9:
 return
square = []#九宫格
for i in range(0+y//3*3, 3+y//3*3):
 for j in range(0+x//3*3, 3+x//3*3):
 square.append(origin[i][j])
r3 = self.check_repetition(square)
if r3==0:
 return 0
else:
 return 1

def check(self,x,y):#检测是否有重复值,无则为0,有则不为0
r1 = self.check_row(x)
r2 = self.check_column(y)
r3 = self.check_square(x, y)
result=r1+r2+r3
return result

def get_next(self): # 获得下一个空值,返回row,column值
i = 0
for list in origin:
 try: # 当0不在列表中时,跳过
 column = list.index(0)
 row = origin.index(list)
 res = (row, column)
 return res
 except ValueError:
 i = i + 1
 if i == 9:
  t2=time.time()
  print("总用时={}".format(t2 - t1))
  exit(0)

def poi(self,row, column): # 位置修正
if row == 0 and column == -1:
 return
if row == 8 and column == 9:
 return
if column == -1:
 column = 8
 row = row - 1
if column == 9:
 column = 0
 row = row - 1
return (row, column)

def get_last(self,row, column):
origin[row].insert(column, 0)
origin[row].pop(column + 1)
column = column - 1 # 获得上一个已填值的行、列位置
row, column = self.poi(row, column)#位置修正
r = origin[row][column] * compare[row][column]
while r != 0:
 column = column - 1
 row, column = self.poi(row, column)
 r = origin[row][column] * compare[row][column]
return (row, column)

def blank(self):
try:
 row,column=self.get_next()
except TypeError:#已填完
 exit(0)
j=0
flag=0
for i in range(1,10):
 origin[row].insert(column,i)
 origin[row].pop(column+1)
 self.debug()
 r = self.check(row, column)
 if r==0:#无重复值
 return
 else:
 j = j + 1
 if j==9:
  flag=1
  break
if flag==1:
 row, column = self.get_last(row, column)
 value=origin[row][column]
 self.debug()
 while value == 9:
 row, column = self.get_last(row, column)
 value = origin[row][column]
 self.debug()
 while value<9:
 for k in range(value+1,10):
  origin[row].insert(column, k)
  origin[row].pop(column + 1)
  self.debug()
  r=self.check(row,column)
  if r!=0:#有重复
  if k==9:
   row, column = self.get_last(row, column)
   value=origin[row][column]
   self.debug()
   while value==9:
   row, column = self.get_last(row, column)
   value = origin[row][column]
   self.debug()
   break
  else:
  return

if __name__=="__main__":
compare = copy.deepcopy(origin)
sudoku = sudoku()
while 1:
sudoku.blank()

来源:https://blog.csdn.net/Jayshon_Jaa/article/details/83040821

标签:python,python3.6,数独
0
投稿

猜你喜欢

  • 彻底弄懂Python中的回调函数(callback)

    2021-02-26 23:51:57
  • Python 12306抢火车票脚本 Python京东抢手机脚本

    2023-02-13 14:22:21
  • Python利用Pydub实现自动分割音频

    2022-10-08 22:02:48
  • python关于变量名的基础知识点

    2023-07-27 14:21:43
  • matplotlib.pyplot画图 图片的二进制流的获取方法

    2021-03-25 09:38:00
  • 基于PyTorch实现一个简单的CNN图像分类器

    2021-08-16 21:52:31
  • Python文件时间操作步骤代码详解

    2022-02-17 03:26:25
  • JavaWeb实现显示mysql数据库数据

    2024-01-20 09:39:43
  • sql server中Select count(*)和Count(1)的区别和执行方式

    2024-01-23 11:47:39
  • Python多进程分块读取超大文件的方法

    2023-12-07 02:19:28
  • spark: RDD与DataFrame之间的相互转换方法

    2023-06-09 23:24:04
  • Python jiaba库的使用详解

    2022-05-11 22:20:46
  • 再谈CSS样式表书写风格

    2009-03-30 16:09:00
  • 大大改善用户体验的10个小细节

    2008-09-17 13:27:00
  • Python实现将Excel转换成xml的方法示例

    2023-01-19 23:02:53
  • 认清区别CSS的类class和id

    2007-10-08 12:02:00
  • JS页内查找关键词的高亮显示

    2013-07-18 21:13:54
  • SQL Server作业报错特殊案例分析

    2024-01-15 17:33:02
  • python docx的超链接网址和链接文本操作

    2021-06-05 22:10:55
  • SQL服务器无法启动的解决方法

    2024-01-16 04:47:20
  • asp之家 网络编程 m.aspxhome.com