python3.6数独问题的解决
作者:Jayshon_Jaa 发布时间:2022-06-21 20:40:32
标签: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,然后退出结束。
当然,算法还可以再优化一下,可以不用那么暴力,先列出可能的值然后再填入,这样可以大大缩小整个程序的运行时间,但是……懒得优化了,就这样吧,又不是不能用(笑~)。
运行结果:
再试一个其他的数独:
这回就快得多了,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
0
投稿
猜你喜欢
- 本文为大家分享了两段PHP分页类,很实用,供大家参考,具体内容如下<?php class Page { private $
- PyQt中MainWindow, QWidget以及Dialog的区别和选择1. Qt界面分类在Qt Designer设计界面时,首先需要选
- 一提到数字图像处理,可能大多数人就会想到matlab,但matlab也有自身的缺点:1、不开源,价格贵2、软件容量大。一般3G以上,高版本甚
- 面向对象的程序设计随着程序的设计的复杂性增加,结构化程序设计方法又不够用了。不够用的根本原因是“代码重用”的时候不方便。面向对象的方法诞生了
- 举例如下,一个服务器端的form 代码自动被解释成客户端代码:服务器端代码: &l
- 很多人都将<数据库设计范式>作为数据库表结构设计“圣经”,认为只要按照这个范式需求设计,就能让设计出来的表结构足够优化,既能保证
- 先吐槽一下opencv 3.1.0的版本cv2.sift和surf就不能用了 看解释是说 什么 "non-free",,
- 如下所示:import matplotlib.pyplot as pltimport numpy as npdef readfile(fil
- 概念json是一种通用的数据类型一般情况下接口返回的数据类型都是json长得像字典,形式也是k-v{ }其实json是字符串字符串不能用ke
- 很多互联网应用程序都提供了全文搜索功能,用户可以使用一个词或者词语片断作为查询项目来定位匹配的记录。在后台,这些程序使用在一个SELECT查
- 在Linux或者Windows下想要查看目录树都可以通过tree命令来实现,两个操作系统中的操作也很相似。使用Linux时,最初以为这是sh
- Python转json时出现中文乱码设置报文头# -*- coding:gbk -*- 连接数据库设置编码mysql = MyS
- 让ASP搭配MYSQL所需要工具mysql-4.1.11-win32 myodbc-3.51.11-1-dll myodbc-3.51.11
- 考虑以下python程序:#!/usr/bin/env pythonimport syssys.stdout.write("std
- 先看一个实例这是我用asp写的一个搜索一个字符串里面第一张图片地址的函数(当然你可以将values那里换一个得到所有图片地址)functio
- 官方文档:http://www.layui.com/demo/layedit.html官网文档目前是不支持layedit扩展式的。自己手动实
- 前言通常执行 python 程序要有相应的 Python 环境,但某些特定场景下,我们可能并不愿意这么麻烦的去配置这些环境(比如将写好的脚本
- PyQt5安装之前安装过anaconda,里面是含有pyqt的,在环境里搜索可以看到,但是针对实际开发,并没有全部的qt5工具,所以需要再次
- 接触编程的朋友都听过正则表达式,在python中叫re模块,属于文字处理服务里面的一个模块。re里面有一个方法叫match,接下来的文章我来
- 很久以前做的东西,发出来大家玩玩!<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0