Hướng dẫn sudoku checker python - trăn kiểm tra sudoku
Đăng ký công nghệ với Tim!
Trong phần 1 của người giải quyết Sudoku này với hướng dẫn Python, tôi giải thích cách chúng ta sẽ giải quyết vấn đề và thảo luận về thuật toán được gọi là quay lại. Backtracking chỉ đơn giản là quay trở lại bước hoặc giải pháp trước đó ngay khi chúng tôi xác định rằng giải pháp hiện tại của chúng tôi không thể được tiếp tục thành một giải hoàn toàn. Chúng tôi sẽ sử dụng nguyên tắc quay lại này để thực hiện thuật toán sau.Sudoku solver with python tutorial I explain how we are going to go about solving the problem and discuss the algorithm known as backtracking. Backtracking is simply reverting back to the previous step or solution as soon as we determine that our current solution cannot be continued into a complete one. We will use this principle of backtracking to implement the following algorithm.Sudoku solver with python tutorial I explain how we are going to go about solving the problem and discuss the algorithm known as backtracking. Backtracking is simply reverting back to the previous step or solution as soon as we determine that our current solution cannot be continued into a complete one. We will use this principle of backtracking to implement the following algorithm. Thuật toán Bắt đầu với một bảng không hoàn chỉnh:
Chúng tôi sẽ hoàn thành khoảng một nửa thuật toán trong Phần 1. trong Phần 2 (nhìn bên dưới) chúng tôi sẽ thực hiện toàn bộ thuật toán. Mã phần 1board = [ [7,8,0,4,0,0,1,2,0], [6,0,0,0,7,5,0,0,9], [0,0,0,6,0,1,0,7,8], [0,0,7,0,4,0,2,6,0], [0,0,1,0,5,0,9,3,0], [9,0,4,0,6,0,0,0,5], [0,7,0,3,0,0,0,1,2], [1,2,0,0,0,7,4,0,0], [0,4,9,2,0,6,0,0,7] ] def print_board(bo): for i in range(len(bo)): if i % 3 == 0 and i != 0: print("- - - - - - - - - - - - - ") for j in range(len(bo[0])): if j % 3 == 0 and j != 0: print(" | ", end="") if j == 8: print(bo[i][j]) else: print(str(bo[i][j]) + " ", end="") def find_empty(bo): for i in range(len(bo)): for j in range(len(bo[0])): if bo[i][j] == 0: return (i, j) # row, col return None Phần 2Đăng ký công nghệ với Tim!
Trong Phần 2 của hướng dẫn này, chúng tôi sẽ hoàn thành thuật toán và tiếp tục hiểu cách thức hoạt động bằng cách chạy qua mã của chúng tôi từng bước. Chúng tôi sẽ sử dụng hàm đệ quy để thực hiện thuật toán được giải thích trong Phần 1. Mã phần 2board = [ [7,8,0,4,0,0,1,2,0], [6,0,0,0,7,5,0,0,9], [0,0,0,6,0,1,0,7,8], [0,0,7,0,4,0,2,6,0], [0,0,1,0,5,0,9,3,0], [9,0,4,0,6,0,0,0,5], [0,7,0,3,0,0,0,1,2], [1,2,0,0,0,7,4,0,0], [0,4,9,2,0,6,0,0,7] ] def solve(bo): find = find_empty(bo) if not find: return True else: row, col = find for i in range(1,10): if valid(bo, i, (row, col)): bo[row][col] = i if solve(bo): return True bo[row][col] = 0 return False def valid(bo, num, pos): # Check row for i in range(len(bo[0])): if bo[pos[0]][i] == num and pos[1] != i: return False # Check column for i in range(len(bo)): if bo[i][pos[1]] == num and pos[0] != i: return False # Check box box_x = pos[1] // 3 box_y = pos[0] // 3 for i in range(box_y*3, box_y*3 + 3): for j in range(box_x * 3, box_x*3 + 3): if bo[i][j] == num and (i,j) != pos: return False return True def print_board(bo): for i in range(len(bo)): if i % 3 == 0 and i != 0: print("- - - - - - - - - - - - - ") for j in range(len(bo[0])): if j % 3 == 0 and j != 0: print(" | ", end="") if j == 8: print(bo[i][j]) else: print(str(bo[i][j]) + " ", end="") def find_empty(bo): for i in range(len(bo)): for j in range(len(bo[0])): if bo[i][j] == 0: return (i, j) # row, col return None print_board(board) solve(board) print("___________________") print_board(board) Xây dựng GUIĐăng ký công nghệ với Tim!
Mã GUIĐể GUI này hoạt động, nó phải ở bên trong cùng thư mục với tệp được gọi là Solver.py. Bạn cũng phải cài đặt pygame trên hệ thống của bạn. Để tìm hiểu cách tải xuống/cài đặt pygame xem video này. Tải xuống mã: Tải xuống ngay GUI.py# GUI.py import pygame from solver import solve, valid import time pygame.font.init() class Grid: board = [ [7, 8, 0, 4, 0, 0, 1, 2, 0], [6, 0, 0, 0, 7, 5, 0, 0, 9], [0, 0, 0, 6, 0, 1, 0, 7, 8], [0, 0, 7, 0, 4, 0, 2, 6, 0], [0, 0, 1, 0, 5, 0, 9, 3, 0], [9, 0, 4, 0, 6, 0, 0, 0, 5], [0, 7, 0, 3, 0, 0, 0, 1, 2], [1, 2, 0, 0, 0, 7, 4, 0, 0], [0, 4, 9, 2, 0, 6, 0, 0, 7] ] def __init__(self, rows, cols, width, height): self.rows = rows self.cols = cols self.cubes = [[Cube(self.board[i][j], i, j, width, height) for j in range(cols)] for i in range(rows)] self.width = width self.height = height self.model = None self.selected = None def update_model(self): self.model = [[self.cubes[i][j].value for j in range(self.cols)] for i in range(self.rows)] def place(self, val): row, col = self.selected if self.cubes[row][col].value == 0: self.cubes[row][col].set(val) self.update_model() if valid(self.model, val, (row,col)) and solve(self.model): return True else: self.cubes[row][col].set(0) self.cubes[row][col].set_temp(0) self.update_model() return False def sketch(self, val): row, col = self.selected self.cubes[row][col].set_temp(val) def draw(self, win): # Draw Grid Lines gap = self.width / 9 for i in range(self.rows+1): if i % 3 == 0 and i != 0: thick = 4 else: thick = 1 pygame.draw.line(win, (0,0,0), (0, i*gap), (self.width, i*gap), thick) pygame.draw.line(win, (0, 0, 0), (i * gap, 0), (i * gap, self.height), thick) # Draw Cubes for i in range(self.rows): for j in range(self.cols): self.cubes[i][j].draw(win) def select(self, row, col): # Reset all other for i in range(self.rows): for j in range(self.cols): self.cubes[i][j].selected = False self.cubes[row][col].selected = True self.selected = (row, col) def clear(self): row, col = self.selected if self.cubes[row][col].value == 0: self.cubes[row][col].set_temp(0) def click(self, pos): """ :param: pos :return: (row, col) """ if pos[0] < self.width and pos[1] < self.height: gap = self.width / 9 x = pos[0] // gap y = pos[1] // gap return (int(y),int(x)) else: return None def is_finished(self): for i in range(self.rows): for j in range(self.cols): if self.cubes[i][j].value == 0: return False return True class Cube: rows = 9 cols = 9 def __init__(self, value, row, col, width ,height): self.value = value self.temp = 0 self.row = row self.col = col self.width = width self.height = height self.selected = False def draw(self, win): fnt = pygame.font.SysFont("comicsans", 40) gap = self.width / 9 x = self.col * gap y = self.row * gap if self.temp != 0 and self.value == 0: text = fnt.render(str(self.temp), 1, (128,128,128)) win.blit(text, (x+5, y+5)) elif not(self.value == 0): text = fnt.render(str(self.value), 1, (0, 0, 0)) win.blit(text, (x + (gap/2 - text.get_width()/2), y + (gap/2 - text.get_height()/2))) if self.selected: pygame.draw.rect(win, (255,0,0), (x,y, gap ,gap), 3) def set(self, val): self.value = val def set_temp(self, val): self.temp = val def redraw_window(win, board, time, strikes): win.fill((255,255,255)) # Draw time fnt = pygame.font.SysFont("comicsans", 40) text = fnt.render("Time: " + format_time(time), 1, (0,0,0)) win.blit(text, (540 - 160, 560)) # Draw Strikes text = fnt.render("X " * strikes, 1, (255, 0, 0)) win.blit(text, (20, 560)) # Draw grid and board board.draw(win) def format_time(secs): sec = secs%60 minute = secs//60 hour = minute//60 mat = " " + str(minute) + ":" + str(sec) return mat def main(): win = pygame.display.set_mode((540,600)) pygame.display.set_caption("Sudoku") board = Grid(9, 9, 540, 540) key = None run = True start = time.time() strikes = 0 while run: play_time = round(time.time() - start) for event in pygame.event.get(): if event.type == pygame.QUIT: run = False if event.type == pygame.KEYDOWN: if event.key == pygame.K_1: key = 1 if event.key == pygame.K_2: key = 2 if event.key == pygame.K_3: key = 3 if event.key == pygame.K_4: key = 4 if event.key == pygame.K_5: key = 5 if event.key == pygame.K_6: key = 6 if event.key == pygame.K_7: key = 7 if event.key == pygame.K_8: key = 8 if event.key == pygame.K_9: key = 9 if event.key == pygame.K_DELETE: board.clear() key = None if event.key == pygame.K_RETURN: i, j = board.selected if board.cubes[i][j].temp != 0: if board.place(board.cubes[i][j].temp): print("Success") else: print("Wrong") strikes += 1 key = None if board.is_finished(): print("Game over") run = False if event.type == pygame.MOUSEBUTTONDOWN: pos = pygame.mouse.get_pos() clicked = board.click(pos) if clicked: board.select(clicked[0], clicked[1]) key = None if board.selected and key != None: board.sketch(key) redraw_window(win, board, play_time, strikes) pygame.display.update() main() pygame.quit() solver.py# solver.py def solve(bo): find = find_empty(bo) if not find: return True else: row, col = find for i in range(1,10): if valid(bo, i, (row, col)): bo[row][col] = i if solve(bo): return True bo[row][col] = 0 return False def valid(bo, num, pos): # Check row for i in range(len(bo[0])): if bo[pos[0]][i] == num and pos[1] != i: return False # Check column for i in range(len(bo)): if bo[i][pos[1]] == num and pos[0] != i: return False # Check box box_x = pos[1] // 3 box_y = pos[0] // 3 for i in range(box_y*3, box_y*3 + 3): for j in range(box_x * 3, box_x*3 + 3): if bo[i][j] == num and (i,j) != pos: return False return True def print_board(bo): for i in range(len(bo)): if i % 3 == 0 and i != 0: print("- - - - - - - - - - - - - ") for j in range(len(bo[0])): if j % 3 == 0 and j != 0: print(" | ", end="") if j == 8: print(bo[i][j]) else: print(str(bo[i][j]) + " ", end="") def find_empty(bo): for i in range(len(bo)): for j in range(len(bo[0])): if bo[i][j] == 0: return (i, j) # row, col return None |