python - 在 pygame 应用程序中实现时的数独求解器性能问题

Question

昨天，我使用回溯创建了一个数独求解器，它的工作原理与预期一致，没有性能问题。我决定创建一个 pygame 应用程序，您可以使用鼠标和键盘填充单元格，然后按“解决”按钮来完成拼图。我将 Solver 算法中的确切代码复制粘贴到 pygame 应用程序(可在 Solver 类中找到)。

在 pygame 应用程序中，您可以在大多数情况下填充单元格并解决谜题，因此它可以按预期工作。然而，在下面发现的更难的谜题中，我遇到了 CPU 问题，导致应用程序使用了我的所有 CPU 并最终崩溃(我在 Mac 操作系统上。具有 I5 的 HighS 系统):

Puzzle from telegraph

总结一下我的问题: 当不从 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()

Answer 1

尝试这个求解器:

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 秒。据说世界hardest 0.11 秒内解决)