Python 3.6 实现暴力穷举法求解数独问题
发布时间：2026-10-13| 4人浏览过
本文介绍使用Python 3.6通过暴力穷举法解决数独问题的过程。算法直接尝试所有可能值，虽运行时间较长但逻辑简单。文中详细记录了从递归调用导致的栈溢出错误，到通过修改递归深度及改用循环退出机制的调试经历，并提供了完整代码及运行结果对比。
该算法采用较为直接的暴力穷举策略，通过逐一尝试每个空格的数值来寻找解，因此程序运行耗时较长，具体时长取决于数独谜题的难度。从算法设计到最终成功运行，过程充满波折：前期花费大量时间设计逻辑，后期则需不断调试以修复Bug。起初为了简化代码，直接在sudoku类中递归调用blank方法，但计算量过大导致编译器抛出“RecursionError: maximum recursion depth exceeded while calling a Python object”（超过最大递归深度）的错误。尽管将递归深度限制提升至100000，仍引发了堆栈溢出问题。最终的解决方式较为粗暴：将递归逻辑改写为while循环，一旦满足条件便直接调用exit(0)强制结束程序。
运行结果：
再试一个其他的数独：
此次运行速度显著提升，仅耗时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()
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
