Trình giải Sudoku trong Python mà không cần quay lại

Tôi luôn thích giải các câu đố toán học và luôn phải vật lộn với việc tìm kiếm các bài toán thú vị và thử thách để thực hành viết mã. Điều đó nói rằng, khi ý tưởng viết một kịch bản giải Sudoku theo cách tinh vi hơn thay vì chỉ sử dụng phương pháp quay lui xuất hiện trong đầu tôi, tôi bắt đầu nghĩ về giải pháp ngay lập tức.

Quay lui, nghĩa là đặt khá nhiều số vào các ô trống và kiểm tra xem bảng Sudoku có còn hợp lệ hay không dường như là một cách giải quyết vấn đề không hiệu quả. Giải pháp cuối cùng sẽ được tìm thấy [nếu có giải pháp], nhưng tại sao không thử áp dụng logic bổ sung cho nó?

Tôi đã triển khai một số quy tắc để thực hiện quay lui dễ dàng hơn. Mỗi ô được giải quyết trước sẽ giảm đáng kể tập hợp các giải pháp và làm cho tập lệnh chạy ngắn hơn nhiều. Hai quy tắc tôi quyết định áp dụng là những quy tắc mà bất kỳ ai đã từng giải Sudoku đều sử dụng và có thể mô tả

1. Tìm một ô chỉ có thể nhập một số.
   

   
   Không cần nhiều nỗ lực để tìm các ô chỉ có thể nhập một số. Bạn chọn một ô và nghĩ về các khả năng bằng cách loại bỏ các số đã được viết sẵn trong ô, cột và hàng đã cho. Bạn thấy chỉ có một lựa chọn? .

2. Tìm hộp/cột/hàng mà số chỉ có thể được đặt trong một ô.
   

   
   Đã đến lúc áp dụng logic đảo ngược tại đây. Thay vì tìm kiếm một ô chỉ có một khả năng khiến nó hợp lệ, bạn hãy tìm một ô, cột hoặc hàng và kiểm tra xem một trong các số bị thiếu trong ô đó có thể chỉ được đặt vào một vị trí hay không.

Sau khi xác định các quy tắc này, tôi quyết định tìm cách chạy tập lệnh của mình. Đây là sơ đồ thuật toán đơn giản hóa mô tả cách thức hoạt động của phần đầu tiên trong tập lệnh của tôi

Đơn giản như nó là. Các quy tắc đơn giản mà tất cả chúng ta đã áp dụng để giải Sudoku. Điều thú vị nhất vẫn chưa đến. quay lui

Khi tôi lần đầu tiên nghĩ về việc triển khai quay lui trong mã của mình, tôi không biết rằng đệ quy không phải là cách tốt nhất để viết thuật toán trong Python. Tôi đã triển khai đầy đủ một cách để giải quyết vấn đề theo cách đệ quy, vì quay lui dường như là một ví dụ hoàn hảo về việc sử dụng nó và phải viết lại phần mã này, khá nhiều từ đầu. Vẫn là bài học để đời. Rốt cuộc, đây là cách tôi triển khai quay lui

Với điều đó được giải thích, đây là mã của tôi

import time #used to check script's run time

#class representing a single cell of sudoku board
class Cell:
    def __init__[self, row_number, column_number, value]:
        self.row = row_number #0 thru 8
        self.column = column_number #0 thru 8
        self.box = self.set_box_number[] #0 thru 8
        self.value = value #0 if empty cell
        self.possibilities = self.set_initial_possibilities[] #empty list or 1 thru 9

    #set box number based on row and column number
    def set_box_number[self]:
        box_number = int[self.column/3]
        box_number += int[self.row/3]*3
        return box_number

    #set possibilities to empty list if cell not empty or 1 thru 9
    def set_initial_possibilities[self]:
        if self.value != 0:
            return []
        else:
            return [*range[1, 10]] 


#class solving sudoku in 'human' way
class Solver:
    def __init__[self, board]:
        self.cells = []
        for row_no, row in enumerate[board]:
            for col_no, val in enumerate[row]:
                self.cells.append[Cell[row_no, col_no, val]]

    #get all cells from box
    def get_cells_from_box[self, box_number]:
        return [cell for cell in self.cells if box_number == cell.box]

    #get all cells from column
    def get_cells_from_column[self, column_number]:
        return [cell for cell in self.cells if column_number == cell.column]

    #get all cells from row
    def get_cells_from_row[self, row_number]:
        return [cell for cell in self.cells if row_number == cell.row] 

    #get all cells within same box, column and row as given cell
    def get_conflicting_cells[self, given_cell]:
        return {cell for cell in self.cells if given_cell.box == cell.box or given_cell.column == cell.column or given_cell.row == cell.row} 

    #remove not valid possibilities from all cells
    def set_all_cells_possibilities[self]:
        for cell in self.cells:
            self.remove_cell_value_from_others_possibilities[cell]

    #look for a cell with single possibility and solve it
    def find_and_solve_cell_with_one_possibility[self]:
        for cell in self.cells:
            if len[cell.possibilities] == 1:
                self.solve_cell[cell, cell.possibilities[0]]
                return True
        return False

    #look for unique possibilities in all boxes, column and rows
    def find_and_solve_unique_possibilities[self]:
        for number in range [0, 8]:
            if self.if_unique_possibility_within_cells[self.get_cells_from_box[number]]:
                return True
            if self.if_unique_possibility_within_cells[self.get_cells_from_column[number]]:
                return True
            if self.if_unique_possibility_within_cells[self.get_cells_from_row[number]]:
                return True
        return False

    #look for unique possibility in group of cells
    def if_unique_possibility_within_cells[self, same_group_cells]:
        counts = [0] * 10
        for cell in same_group_cells:
            for possibility in cell.possibilities:
                counts[possibility] += 1
        if 1 in counts:
            unique_value = counts.index[1]
            for cell in same_group_cells:
                if unique_value in cell.possibilities:
                    self.solve_cell[cell, unique_value]
                    return True
            return False

    #solve cell and remove its value from other cells possibilities
    def solve_cell[self, given_cell, value]:
        given_cell.value = value
        given_cell.possibilities = []
        self.remove_cell_value_from_others_possibilities[given_cell]

    #remove cell value from possibilites of cells within same box, column and row
    def remove_cell_value_from_others_possibilities[self, given_cell]:
        for conflicting_cell in self.get_conflicting_cells[given_cell]:
            try:
                conflicting_cell.possibilities.remove[given_cell.value]
            except:
                continue

    #main algorithm of the class
    def run[self]:
        while[True]:
            if not self.find_and_solve_cell_with_one_possibility[]:
                if not self.find_and_solve_unique_possibilities[]:
                    break


#class solving sudoku with backtracking algorithm
class Backtrack[]:
    def __init__[self, cells]:
        self.cells = cells
        self.unsolved_cells = [cell for cell in self.cells if cell.value == 0]

    #get all cells within same box, column and row as given cell
    def get_conflicting_cells_values[self, given_cell]:
        return {cell.value for cell in self.cells if given_cell.box == cell.box or given_cell.column == cell.column or given_cell.row == cell.row} 

    #check validity of sudoku if cell is set to given value
    def if_solution_valid[self, given_cell, cell_value_to_check]:
        return not cell_value_to_check in self.get_conflicting_cells_values[given_cell]

    #check current cell value and pick next of its possibilities
    def get_next_possibility[self, given_cell]:
        if given_cell.value == 0:
            return given_cell.possibilities[0]
        else:
            return given_cell.possibilities[given_cell.possibilities.index[given_cell.value]+1]

    #main algorithm of the class
    def run[self]:
        current_cell_number = 0
        while [current_cell_number >= 0 and current_cell_number  take step back and work on previous cell
                current_cell.value = 0
                current_cell_number -= 1
            else:
                #possibility valid -> change cell value and proceed to next cell
                if self.if_solution_valid[current_cell, next_possibility]:
                    current_cell.value = next_possibility
                    current_cell_number += 1
                #possibility not valid -> change cell value and repeat process
                else:
                    current_cell.value = next_possibility


#class responsible for printing sudoku board in readable form
class Printer[]:
    def __init__[self, cells]:
        self.cells = cells

    #print sudoku board
    def print[self]:
        last_cell_row_no = 0
        for cell in self.cells:
            if last_cell_row_no != cell.row:
                print[]
            print[cell.value, end = " "]
            last_cell_row_no = cell.row
        print["\n- - - - - - - - -"]


#class responsible for checking if sudoku solution is valid
class Validator[]:
    def __init__[self, cells]:
        self.cells = cells

    #check if sudoku solution is valid
    def if_valid[self]:
        for cell in self.cells:
            if cell.value == 0:
                return False
        return True

    #print sudoku validity
    def print[self]:
        if self.if_valid[]:
            print["Sudoku solved!"]
        else:
            print["Sudoku is not valid!"]


### main part below ###
def main[]:

    #sudoku to solve
    sudoku_to_solve = [
    [0, 0, 0, 0, 0, 0, 2, 0, 0],
    [0, 8, 0, 0, 0, 7, 0, 9, 0],
    [6, 0, 2, 0, 0, 0, 5, 0, 0],
    [0, 7, 0, 0, 6, 0, 0, 0, 0],
    [0, 0, 0, 9, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 2, 0, 0, 4, 0],
    [0, 0, 5, 0, 0, 0, 6, 0, 3],
    [0, 9, 0, 4, 0, 0, 0, 7, 0],
    [0, 0, 6, 0, 0, 0, 0, 0, 0]
    ]

    start_time = time.time[] #start timer to measure run time

    solver = Solver[sudoku_to_solve]

    printer=Printer[solver.cells]
    printer.print[]

    solver.set_all_cells_possibilities[] #checks possibilities for all cells
    solver.run[] #comment this line to leave everything to backtracking

    backtrack=Backtrack[solver.cells]
    backtrack.run[]

    printer=Printer[backtrack.cells]
    printer.print[]

    validator=Validator[backtrack.cells]
    validator.print[]

    print["Run time: %s seconds" % [time.time[] - start_time]]

if __name__ == "__main__":
    main[]

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

Mã tuân theo ý tưởng được hiển thị trong sơ đồ thuật toán. một cách để giải Sudoku nhanh hơn là chỉ quay lui. Điều này có thể được chứng minh. chạy tập lệnh hai lần, lần đầu tiên với bộ giải. run[] bị bỏ qua và thứ hai không có dòng đó [hoặc có # trước nó] để bỏ qua phần đơn giản hóa Sudoku trước khi quay lui bắt đầu. Tùy thuộc vào độ phức tạp, thời gian chạy có thể giảm đáng kể. Trong ví dụ được viết trong tập lệnh, thời gian chạy của tôi là khoảng. 6. 9 so với 64 giây

Điều này có thể còn nhanh hơn nếu sử dụng các quy tắc giải Sudoku phức tạp hơn. Tôi sẽ để nó như bây giờ, vì tôi hài lòng với kết quả. Những quy tắc đơn giản này đã giúp tìm ra giải pháp nhanh hơn nhiều

Sudoku có thể được giải quyết mà không cần quay lại không?

Có một thuật toán để giải Sudoku?

Bạn có thể giải Sudoku mà không cần đoán không?

thuật toán kẻ lừa đảo là gì?