[Pygame] Sudoku solution with backtracking

위의 그림과 같은 Sudoku  문제가 있을때 그것을 푸는 코드를 작성해볼것입니다.

 

 

import pygame
 
 
WIDTH = 550
background_color = (251,247,245)
original_grid_element_color = (52, 31, 151)
green = (0, 255, 0)
blue = (0, 0, 128)
buffer = 5
BLACK = (0, 0, 0)
 
grid     = [[0, 0, 0, 0, 0, 0, 0, 2, 8],
           [0, 6, 0, 0, 0, 0, 0, 0, 7],
           [0, 0, 0, 4, 0, 1, 0, 0, 0],
           [5, 0, 0, 9, 7, 0, 3, 0, 0],
           [2, 0, 4, 0, 0, 8, 0, 0, 0],
           [3, 0, 0, 0, 0, 4, 5, 0, 0],
           [1, 3, 0, 0, 9, 0, 0, 0, 0],
           [0, 5, 7, 0, 0, 0, 0, 9, 0],
           [0, 0, 8, 3, 1, 7, 0, 0, 0]]
 
 
def isEmpty(num):
    if num == 0:
        return True
    return False
 
def isValid(position, num):
     #Check for Column, row and sub-grid
    
    #Checking row
    for i in range(0, len(grid[0])):
        if(grid[position[0]][i] == num):
            return False
    
    #Checking column
    for i in range(0, len(grid[0])):
        if(grid[i][position[1]] == num):
            return False
    
    #Check sub-grid  
    x = position[0]//3*3
    y = position[1]//3*3
    #Gives us the box number
    
    for i in range(0,3):
        for j in range(0,3):
            if(grid[x+i][y+j]== num):
                return False
    return True
 
 
try_count = True
solved = 0
try_solve = 1
 
def sudoku_solver(win):
    global try_count
    global try_solve
 
    myfont = pygame.font.SysFont('Comic Sans MS', 35)
 
    for i in range(0,len(grid[0])):
        for j in range(0, len(grid[0])):
            if(isEmpty(grid[i][j])):               
                for k in range(1,10):
                    if isValid((i,j), k):                                         
                        grid[i][j] = k
                        pygame.draw.rect(win, background_color, ((j+1)*50 + buffer, (i+1)*50+ buffer,50 -2*buffer , 50 - 2*buffer))
                        value = myfont.render(str(k), True, (0,0,0))
                        win.blit(value, ((j+1)*50 +15,(i+1)*50))
                        pygame.display.update()
 
                        pygame.time.delay(10)
 
                        text = myfont.render("Try_solve : " + str(try_solve), True, green, blue)
                        win.blit(text, (100, 3))                      
                        pygame.display.update()         
                                               
                        sudoku_solver(win)
                        
                        #Exit condition
                        global solved
 
                        if(solved == 1):
                            return
                        else:
                          grid[i][j] = 0
 
                          if(try_count):
                            try_solve += 1
                            try_count = False                           
                          else:
                              try_count = True
                                                                 
                        pygame.draw.rect(win, background_color, ((j+1)*50 + buffer, (i+1)*50+ buffer,50 -2*buffer , 50 - 2*buffer))
                        pygame.display.update()        
                return                      
    solved = 1
    
def main():    
   
    pygame.init()
    win = pygame.display.set_mode((WIDTH, WIDTH))
    pygame.display.set_caption("Sudoku")
    win.fill(background_color)
    myfont = pygame.font.SysFont('Comic Sans MS', 35)
    
    for i in range(0,10):
        if(i%3 == 0):
            pygame.draw.line(win, (0,0,0), (50 + 50*i, 50), (50 + 50*i ,500 ), 4 )
            pygame.draw.line(win, (0,0,0), (50, 50 + 50*i), (500, 50 + 50*i), 4 )
 
        pygame.draw.line(win, (0,0,0), (50 + 50*i, 50), (50 + 50*i ,500 ), 2 )
        pygame.draw.line(win, (0,0,0), (50, 50 + 50*i), (500, 50 + 50*i), 2 )
    pygame.display.update()
    
    for i in range(0, len(grid[0])):
        for j in range(0, len(grid[0])):
            if(0<grid[i][j]<10):
                value = myfont.render(str(grid[i][j]), True, original_grid_element_color)
                win.blit(value, ((j+1)*50 + 15, (i+1)*50 ))
    pygame.display.update()
            
    sudoku_solver(win)
 
    
    
    
    while True: 
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                return
 
    
   
main()

 

인터넷에 돌아다니는 코드를 사용해서  제가 이해하는 용도로 약간 수정하고

얼마나 시도 되는가에 대한 counter를 추가로 작성하였습니다.

시도된다는 기준은  풀이를 쭉 하다가 잘못되면 지우고 다시 하는 과정을 카운터 1로 하였는데 정확히 구연되었는가는 모르겠네여.