python3.6数独问题的解决

yipeiwu_com5年前Python基础

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

运行结果:

再试一个其他的数独:

这回就快得多了,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()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

浅谈python脚本设置运行参数的方法

浅谈python脚本设置运行参数的方法

正在学习Django框架,在运行manage.py的时候需要给它设置要监听的端口,就是给这个脚本一个运行参数。教学视频中,是在Eclipse中设置的运行参数,网上Django大部分都是在...

Python匿名函数/排序函数/过滤函数/映射函数/递归/二分法

一. lamda匿名函数   为了解决一些简单的需求而设计的一句话函数 # 计算n的n次方 def func(n): return n**n print(func(10)) f...

在Pycharm terminal中字体大小设置的方法

如下所示: file->settings->Editor->General->Console里面的console commands history size 以上...

Python高级应用实例对比:高效计算大文件中的最长行的长度

前2种方法主要用到了列表解析,性能稍差,而最后一种使用的时候生成器表达式,相比列表解析,更省内存 列表解析和生成器表达式很相似: 列表解析 [expr for iter_var in i...

Python当中的array数组对象实例详解

Python当中的array数组对象实例详解

计算机为数组分配一段连续的内存,从而支持对数组随机访问; 由于项的地址在编号上是连续的,数组某一项的地址可以通过将两个值相加得出,即将数组的基本地址和项的偏移地址相加。 数组的基本地址...