Fly to the sky & Return

[Pygame] Sudoku solution with backtracking 본문

프로그래밍/파이썬

[Pygame] Sudoku solution with backtracking

낼은어떻게 2023. 9. 24. 19:27
336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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()
 cs

 

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

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

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

 

 

'프로그래밍 > 파이썬' 카테고리의 다른 글

Ubuntu에서 아나콘다 설치하기  (0) 2023.02.06
chatGPT api 이용 sample code  (0) 2023.02.05
Exfread를 이용한 EXIF data 추출 및 날짜별 폴더 생성해서 사진 옮기기 .....2  (0) 2018.03.19
파이썬으로 엑셀 다루기.......2 엑셀로 달력을 만들어보자..  (0) 2017.12.28
파이썬으로 Excel 다루기 ..........1  (0) 2017.12.22
'프로그래밍/파이썬' Related Articles more