当前位置:首页 > Python技术文章 > python3.6数独问题的解决

怎样解决python3.6数独问题

  • 发布时间:
  • 作者:码农之家原创
  • 点击:186

这篇文章主要知识点是关于python、python3.6、数独、python实现自动解数独小程序 的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下相关资源

Python金融实战(严玉星)

本书是Python金融实战类指南,指导金融大数据分析过程,从Python的安装、基础语法,再到一系列简单的编程示例,序渐进地引导读者学习Python

查看详情

python3.6数独问题的解决

算法比较暴力,直接用穷举的方式一个一个去试,所以程序运行时间会比较长,运行时间视数独而定。
不过从一开始到运行成功,整个过程却是一波三折,设计算法就花了不少时间,然后就是不断地去调试,找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()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

python实现自动解数独小程序

跟朋友最近聊起来数独游戏,突发奇想使用python编写一个自动计算数独解的小程序。

数独的规则不再过多阐述,在此描述一下程序的主要思路:

(当前程序只针对于简单的数独,更复杂的还待深入挖掘)

1.计算当前每个空格可能的取值集合,并将空格顺序值对应取值集合置于字典中;

2.对取值集合位数为1,即空格处为单一取值的进行赋值,(填入动作),重复1刷新字典直到字典为空位置;

当前实现如下:

1.将数独输入列表中,并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置的当前可能取值:

#编辑数独题目,将题目输入列表中
question = [6,0,7,0,0,0,9,0,3,
  0,0,8,0,0,7,0,0,0,
  3,0,0,0,8,2,0,7,5,
  0,1,2,3,0,5,0,0,0,
  0,0,6,0,0,0,5,0,0,
  0,0,0,4,0,6,7,1,0,
  2,6,0,7,4,0,0,0,8,
  0,0,0,8,0,0,6,0,0,
  7,0,5,0,0,0,1,0,9]
 
# print(question[0])
 
#返回当前数独为0的空格中所有可能取值
def count_candidate_number(j):
 exist_all_number = [] #当前横竖大方格内所有出现的数字集
 candidate_number = [] #该方格内所有的数字候选集
 SD_Row = int(j) // 9 #行
 SD_Column = int(j) % 9 #列
 
 #用迭代器写
 exist_all_number_part1 = [question[i+SD_Row*9] for i in range(9)] #横-出现的所有数字集
 exist_all_number_part2 = [question[i*9+SD_Column] for i in range(9)] #竖-出现的所有数字集
 exist_all_number_part3 = [question[((j//9)//3)*27+((j % 9)//3)*3+i] for i in range(3)]+[question[((j//9)//3)*27+((j % 9)//3)*3+9+i] for i in range(3)]+[question[((j//9)//3)*27+((j % 9)//3)*3+18+i] for i in range(3)] #大方块-出现的所有数字集
 exist_all_number = list(set(exist_all_number_part1+exist_all_number_part2+exist_all_number_part3))  #对出现所有的数字集组合及去重
 # print(exist_all_number)
 
 #用循环写
 # for i in range(9):
 # if question[i+SD_Row*9] not in exist_all_number:
 #  exist_all_number.append(question[i+SD_Row*9])
 # if question[i*9 + SD_Cloumn] not in exist_all_number:
 #  exist_all_number.append(question[i*9 + SD_Cloumn])
 # # print(exist_all_number)
 
 #迭代器写
 candidate_number = [i for i in range(1, 10) if i not in exist_all_number] #对可能取值进行迭代输出
 
 #用循环写
 # for i in range(1,10):
 # if i not in exist_all_number:
 #  candidate_number.append(i)
 # print(candidate_number)
 
 return candidate_number

2.定义函数求解对应每个为0的位置的可能求解,并将位置信息与可能求解以键-键值的形式存储于字典中:

#对数组中每个为0的空格列出所有可能的取值数集,并放置于字典中
def all_possible_candidate_number():
 all_possible_candidate_number = {i:count_candidate_number(i) for i in range(81) if question[i] == 0}
 return all_possible_candidate_number
 # print(all_possible_candidate_number)

3.对每一个位置的可能求解进行判断,若可能解只有一个,则填入该解,循环直至数独求解完成

def main_count():
 answer_sudoku = question
 candidate_number_dic = {}
 while True:
 candidate_number_dic = all_possible_candidate_number() #在每次循环之前刷当前每个为0的空格,所有的取值集合
 if candidate_number_dic == {}:    #如果为空,则证明没有为0的空格,则为求解
  answer_sudoku = question    #对answer_sudoku赋值,并打印
  print("已求解",answer_sudoku)
  break
 else:
  for eachkey,eachValue in candidate_number_dic.items(): #对字典中位数为1的取值集合,既确定该数字变为当前应取值
  if len(eachValue) == 1:
   answer_sudoku[eachkey] = eachValue[0]
   print(eachkey,eachValue[0])   #打印对应键值及对应数值
  pass
 
if __name__ == '__main__':
 main_count()

程序运行结果:

D:\pythonwokr\venv\Scripts\python.exe D:/pythonwokr/数独.py
已求解 [6, 2, 7, 5, 1, 4, 9, 8, 3, 5, 4, 8, 9, 3, 7, 2, 6, 1, 3, 9, 1, 6, 8, 2, 4, 7, 5, 4, 1, 2, 3, 7, 5, 8, 9, 6, 9, 7, 6, 1, 2, 8, 5, 3, 4, 8, 5, 3, 4, 9, 6, 7, 1, 2, 2, 6, 9, 7, 4, 1, 3, 5, 8, 1, 3, 4, 8, 5, 9, 6, 2, 7, 7, 8, 5, 2, 6, 3, 1, 4, 9]
 
Process finished with exit code 0

程序到这里就结束了,下一步拓展是对于若不存在单独唯一解的情况,待续。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

以上就是本次给大家分享的关于Python的全部知识点内容总结,大家还可以在下方相关文章里找到python求最大值最小值的实、 Python调用C# Com dll组件的方、 Python工具整理推荐、 等python文章进一步学习,感谢大家的阅读和支持。

上一篇:python3调用百度翻译API实时翻译的实例代码

下一篇:Python list列表中删除多个重复元素的方法实例

展开 +

收起 -

python3.6数独问题 相关内容
Python3.6及TensorFlow的安装和配置流程(图解)

这篇文章主要为大家详细介绍了python3.6.3及TensorFlow安装配置方法图文教程,具有一定的参考价值,感兴趣的读者们可以参考一下

查看详情
python3.6 tkinter屏保小程序实现方法

这篇文章主要为大家详细介绍了python3.6 tkinter实现屏保小程序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

查看详情
Python轻松学:爬虫、游戏与架站

趣味的手绘画插画图片:文本说不清的事儿我们看来图说。 丰富多彩的程序编写实例:已不干瘪地讲基础理论,用实例和新项目表明任何。 涉及到內容普遍:遮盖PythonWeb、Python网络爬虫、游戏

查看详情
教孩子学编程:Python语言版

这是一本教孩子使用Python进行基础程序设计和解决问题的入门图书,针对变量、循环、函数等编程基础概念的介绍,可以帮助年轻的程序员构建所需的技能,适合任何想要通过Python学习编程的读

查看详情
11招玩转网络安全:用Python,更安全 查看详情
Python科学计算

本书详细介绍Python科学计算中最常用的扩展库NumPy、SciPy、matplotlib、Pandas、SymPy、TTK、Mayavi、OpenCV、Cython,涉及数值计算、界面制作、三维可视化、图像处理、提高运算效率等多方面的内容。所

查看详情
Python趣味编程入门与实战

将Python程序编写中常必须的基本知识、挑选构造、循环系统构造、大海龟制图、文档和文件夹名称实际操作、时间与時间解决、GUI程序运行、tkinter库绘图图型和制作动画、PyGame手机游戏融为一

查看详情
树莓派Python编程入门与实战

《树莓派Python编程入门与实战》经典系列 直观 循序渐进的树莓派Python编程学习教程 强调实践教学 以示例引导读者完成常见的任务。

查看详情
Python新手使用Django架站的16堂课

本书作者台湾大师带你活用Django Web Framework快速构建移动网站,以16堂课来介绍Python新手使用Django架站的要点,可作为Python Django的初学者的参考书籍

查看详情
python3.6数独问题 学习笔记
网友NO.149571

Python如何判断数独是否合法

介绍 该数独可能只填充了部分数字,其中缺少的数字用 . 表示。 注意事项 一个合法的数独(仅部分填充)并不一定是可解的。我们仅需使填充的空格有效即可。 解体思路 将数独按照行、列和块进行预处理,然后分别判断是否合法。 利用Python的表达式推导,匿名函数和 all 函数可以很方便的进行处理。 代码 class Solution:# @param board, a 9x9 2D array# @return a booleandef isValidSudoku(self, board): rows = [list(lst[::]) for lst in board] columns = [[lst[idx] for lst in board] for idx in range(9)] blocks_origin = [board[row][column] for x in [[0, 1, 2], [3, 4, 5], [6, 7, 8]] for y in [[0, 1, 2], [3, 4, 5], [6, 7, 8]] for row in x for column in y] # 利用一些技巧直接按块储存数据 blocks = [[blocks_origin[row * 9 + column] for column in range(9)] for row in range(9)] check = lambda lst: all([lst.count(x) == 1 for x in lst if x != '.']) # 判断一条记录(按某种方式排列……

网友NO.403924

Python判断有效的数独算法示例

本文实例讲述了Python判断有效的数独算法。分享给大家供大家参考,具体如下: 一、题目 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 1. 数字 1-9 在每一行只能出现一次。 2. 数字 1-9 在每一列只能出现一次。 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 数独部分空格内已填入了数字,空白格用 ‘.' 表示。 例1: 输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true 例2: 输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6",".……

网友NO.488339

python实现自动解数独小程序

跟朋友最近聊起来数独游戏,突发奇想使用python编写一个自动计算数独解的小程序。 数独的规则不再过多阐述,在此描述一下程序的主要思路: (当前程序只针对于简单的数独,更复杂的还待深入挖掘) 1.计算当前每个空格可能的取值集合,并将空格顺序值对应取值集合置于字典中; 2.对取值集合位数为1,即空格处为单一取值的进行赋值,(填入动作),重复1刷新字典直到字典为空位置; 当前实现如下: 1.将数独输入列表中,并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置的当前可能取值: #编辑数独题目,将题目输入列表中question = [6,0,7,0,0,0,9,0,3, 0,0,8,0,0,7,0,0,0, 3,0,0,0,8,2,0,7,5, 0,1,2,3,0,5,0,0,0, 0,0,6,0,0,0,5,0,0, 0,0,0,4,0,6,7,1,0, 2,6,0,7,4,0,0,0,8, 0,0,0,8,0,0,6,0,0, 7,0,5,0,0,0,1,0,9] # print(question[0]) #返回当前数独为0的空格中所有可能取值def count_cand……

网友NO.822243

python实现数独游戏 java简单实现数独游戏

使用python和java实现数独游戏,有比较才有收获哦。 1、Python版 #--coding:utf-8--import randomimport itertoolsfrom copy import deepcopydef make_board(m=3): numbers = list(range(1,m**2+1)) #可能出现的数字为1-9 board = None #board是数度二维列表 while board is None: board = get_board(m,numbers) return boarddef get_board(m,numbers): n = m**2 board = [[None for _ in range(n)] for _ in range(n)] for i,j in itertools.product(range(n),repeat=2): i0,j0 = i-i%m,j-j%m # i,j分别代表的是我们的行和列 # i0和j0代表的是board[i][j]所在的区块的起始位置 random.shuffle(numbers) #shuffle() 方法将序列的所有元素随机排序。 for x in numbers: if(x not in board[i] and all(row[j]!=x for row in board) and all(x not in row[j0:j0+m] for row in board[i0:i])): board[i][j] = x break else:#当循环正常结束时会执行else return None return boarddef print_board(board,m=3): numbers = list(range(1,m**2+1)) #每一行随机把5个数字变成Non……

网友NO.175209

python实现解数独程序代码

偶然发现linux系统附带的一个数独游戏,打开玩了几把。无奈是个数独菜鸟,以前没玩过,根本就走不出几步就一团浆糊了。 于是就打算借助计算机的强大运算力来暴力解数独,还是很有乐趣的。 下面就记录一下我写解数独程序的一些思路和心得。 一.数独游戏的基本解决方法 编程笼统的来说,就是个方法论。不论什么程序,都必须将问题的解决过程分解成计算机可以实现的若干个简单方法。俗话说,大道至简。对于只能明白0和1的计算机来说,就更需要细分步骤,一步一步的解决问题了。 首先来思考一下解数独的基本概念。 数独横九竖九共八十一个格子,同时又分为9个九宫格。规则很简单——需要每一个格中的数字,都保证与其所在横排和竖排以及九宫格内无相同数字。 所以我们的大概思路就是,从第一个空格开始试着填数,从 1 开始填,如果……

<
1
>

Copyright 2018-2020 xz577.com 码农之家

本站所有电子书资源不再提供下载地址,只分享来路

免责声明:网站所有作品均由会员网上搜集共同更新,仅供读者预览及学习交流使用,下载后请24小时内删除

版权投诉 / 书籍推广 / 赞助:QQ:520161757