python - 在 pygame 应用程序中实施时的数独求解器性能问题
问题描述
昨天我使用回溯创建了一个数独求解器,它的工作方式与预期的一样,没有性能问题。我决定创建一个 pygame 应用程序,您可以用鼠标和键盘填写单元格,然后按“解决”按钮完成拼图。我将 Solver 算法中的确切代码复制粘贴到 pygame 应用程序(可在 Solver 类中找到)。
在 pygame 应用程序中,大多数时候您都可以填写单元格并解决难题,因此它可以正常工作。然而,在下面发现的更难的谜题中,我遇到了 CPU 问题,导致应用程序使用我所有的 CPU 并最终崩溃(我在 Mac OS 上。I5 的 HighS 系统):
总结一下我的问题:数独求解器算法在不从 pygame 应用程序中调用时工作正常,(电报谜题大致在 2.s 中解决),但是当从 pygame 应用程序中调用时,它可以解决简单的谜题,但是较难的会导致应用程序由于 CPU 过度使用而崩溃。
代码如下:
class Sudoku():
def __init__(self):
self.W,self.H = (600,600)
pygame.init()
pygame.mixer.quit()
self.screen = pygame.display.set_mode((self.W+200,self.H))
self.clock = pygame.time.Clock()
self.board = Board()
self.focused = None
self.solve = Button((0,140,0),650,200,100,50,"Solve")
self.solver = Solver(self.board.sudoku)
self.run()
### Takes care of pygame events from mouse and keyboard
def events(self):
for event in pygame.event.get():
if event.type == pygame.QUIT:
self.quit()
if event.type == pygame.MOUSEBUTTONUP:
self.focused = self.getCellFromMousePos(pygame.mouse.get_pos())
if self.solve.isOver(pygame.mouse.get_pos()):
self.solver.solve()
if event.type == pygame.KEYDOWN:
print("key")
if self.focused!=None:
try:
self.board.set_value(self.focused[0],self.focused[1],int(event.unicode))
except:
pass
## Calls paint functions from working units (button, board)
def paint(self):
self.screen.fill((255,229,204))
self.board.paint(self.screen,self.W,self.H)
self.solve.draw(self.screen)
pygame.display.flip()
## Main loop
def run(self):
self.running = True
while self.running:
self.dt = self.clock.tick(60)/1000
self.update()
## Update called from main loop
def update(self):
self.events()
self.paint()
## Set value on board (Unused)
def set_value(self,row,col,value):
self.board.set_value(row,col,value)
## Get a cell (0-9,0-9) from the mouse position.
def getCellFromMousePos(self,coord):
return (math.floor(coord[0]/(self.W/9)),math.floor(coord[1]/(self.H/9)))
class Board():
def __init__(self):
self.sudoku = [ [0]*9 for _ in range(9) ]
self.font = pygame.font.SysFont('comicsans',81)
## Takes a preset board as input - NOT USED
def set_preset(self,board):
if len(board)==9 and len(board[1])==9:
for row in board:
for cell in row:
if board[row][cell]>9 or board[row][cell]<0:
return None
self.sudoku = board
## Sets value in a cell
def set_value(self,row,col,value):
if self.value_is_valid(value):
self.sudoku[row][col] = value
## Check if an value is valid
def value_is_valid(self,value):
if int(value)<=9 and int(value)>=0:
return True
return False
## Paints grid and numbers to pygame.screen
def paint(self,screen,width,height):
## DRAW background board itself:
for row in range(10):
k = row*(height/9)
pygame.draw.line(screen,(0,0,0),(0,k),(width,k))
for col in range(10):
k = col*(width/9)
pygame.draw.line(screen,(0,0,0),(k,0),(k,height))
## Draw numbers:
for r in range(9):
for c in range(9):
value = self.sudoku[r][c]
if value != 0:
text = self.font.render(str(value),2,(0,0,0))
screen.blit(text,((width/9)*r+(text.get_width()/2),(height/9)*c))
## Just a button.
class Button:
def __init__(self,color,x,y,width,heigth,text):
self.x = x
self.y = y
self.width = width
self.heigth = heigth
self.text = text
self.color = color
def draw(self,window):
pygame.draw.rect(window,self.color,(self.x,self.y,self.width,self.heigth))
if self.text!="":
font = pygame.font.SysFont('comicsans',61)
text = font.render(self.text,2,(0,0,0))
window.blit(text,(self.x+(self.width/2 - text.get_width()/2), self.y + (self.heigth/2 -text.get_height()/2)))
def isOver(self,pos):
if pos[0] > self.x and pos[0]< (self.x+self.width):
if pos[1]> self.y and pos[1]< self.y+self.heigth:
return True
return False
## Solving algorithm
class Solver:
def __init__(self,board):
self.sudoku = board
def valid(self,row,column,value):
original = self.sudoku[row][column]
self.sudoku[row][column] = value
validity = self.duplicates()
self.sudoku[row][column] = original
return not validity
## Checks if an array contains duplicates
def arrayContainsDuplicates(self,array):
if len(array) == len(set(array)):
return False
return True
## Trims an array from empty spaces (0's)
def trimarray(self,array):
trimmed = []
for cell in array:
if cell != 0:
trimmed.append(cell)
return trimmed
## Finds the next empty cell. Used for backtracking.
def find_empty(self):
for i in range(len(self.sudoku)):
for j in range(len(self.sudoku[i])):
if self.sudoku[i][j] == 0:
return (i,j)
return None
## Checks if the board contains any duplicates in rows, blocks and columns.
def duplicates(self):
for row in self.sudoku:
if self.arrayContainsDuplicates(self.trimarray(row)):
return True
for col in map(list,zip(*self.sudoku)):
if self.arrayContainsDuplicates(self.trimarray(col)):
return True
blocks=[[self.sudoku[int(m//3)*3+i][(m%3)*3+j] for i in range(3) for j in range(3)] for m in range(9)]
for block in blocks:
if self.arrayContainsDuplicates(self.trimarray(block)):
return True
return False
## Backtrakcing solving algorithm.
def solve(self):
find = self.find_empty()
if not find:
return True
else:
row,col = find
for i in range(1,10):
if self.valid(row,col,i):
self.sudoku[row][col] = i
if self.solve():
return True
else:
self.sudoku[row][col] = 0
s = Sudoku()
解决方案
试试这个求解器:
known = [ [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, 6,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]
]
import random
groups = [ p//27*3+p%9//3 for p in range(81) ]
colNums = [ set(range(1,10)) for _ in range(9) ]
rowNums = [ set(range(1,10)) for _ in range(9) ]
grpNums = [ set(range(1,10)) for _ in range(9) ]
sudoku = [ [0]*9 for _ in range(9) ]
for pos in range(81):
row,col,group = pos//9,pos%9,groups[pos]
fixed = known[row][col]
if fixed:
sudoku[row][col] = fixed
colNums[col].discard(fixed)
rowNums[row].discard(fixed)
grpNums[group].discard(fixed)
pos = 0
availables = [ None for _ in range(81)]
while pos < 81:
row,col,group = pos//9,pos%9,groups[pos]
number = sudoku[row][col]
fixed = known[row][col]
if number != 0 and not fixed:
sudoku[row][col] = 0
colNums[col].add(number)
rowNums[row].add(number)
grpNums[group].add(number)
if availables[pos] is None:
availables[pos] = {fixed} if fixed else colNums[col] & rowNums[row] & grpNums[group]
if availables[pos]:
number = fixed or min(availables[pos])
if not fixed:
sudoku[row][col] = number
colNums[col].discard(number)
rowNums[row].discard(number)
grpNums[group].discard(number)
availables[pos].discard(number)
pos += 1
else:
availables[pos] = None
pos -= 1
if pos < 0 : break
if pos < 81:
print("FAILED!")
else :
for r,line in enumerate(sudoku):
print(*[line[i:][:3] for i in range(0,9,3)],"\n"*(r%3==2))
它在 0.15 秒内找到解决方案(不包括打印时间):
[8, 4, 9] [2, 7, 1] [3, 5, 6]
[2, 1, 3] [6, 5, 4] [8, 7, 9]
[6, 7, 5] [8, 9, 3] [2, 4, 1]
[3, 5, 2] [9, 6, 7] [1, 8, 4]
[1, 8, 7] [3, 4, 5] [6, 9, 2]
[9, 6, 4] [1, 8, 2] [7, 3, 5]
[7, 2, 1] [4, 3, 9] [5, 6, 8]
[4, 3, 8] [5, 2, 6] [9, 1, 7]
[5, 9, 6] [7, 1, 8] [4, 2, 3]
注意:如果情况可能,最多需要 4 秒钟才能确定没有解决方案。这意味着对于一个极其复杂的问题,最坏的情况是不到 4 秒。据说世界上最难的问题在 0.11 秒内解决)
推荐阅读
- node.js - 在同一个数组中查找后如何获取多个数组
- apache-spark - 如何使用气流触发 google dataproc 作业并传递参数
- microsoft-graph-api - 用户重置\更新密码时的 Webhook\更改通知
- javascript - Javascript 类导入调用只需要一个参数
- xamarin.forms - Xamarin Android 绑定未实现接口问题
- python - “TypeError:open() 在我的解析代码中得到了一个意外的关键字参数‘newline’”
- python - 颜色条定位 Matplotlib
- typescript - 按对象键的通用数据
- php - 从 iframe 获取实际 php 格式的源代码的任何方法
- html - 需要在网页内运行.exe游戏文件