Implementierte Supreme Solver in Python 3

Neulich fand ich beim Surfen im Internet den folgenden Artikel: "Die schwierigste Zahl der Welt, die von einem Mathematikexperten über 3 Monate erstellt wurde" .. Ob es wahr ist oder nicht, ich habe versucht, dies mit Python3 zu lösen. Die Backtrack-Methode wird zur Implementierung verwendet. Kurz gesagt bedeutet dies, dass Sie mit Gewalt lösen (´ ・ ω ・ `)

import itertools

class Sudoku(object):
    def __init__(self):
        self.matrix = [[0 for _ in range(9)] for _ in range(9)] #0 wenn leer
    
    #Löse ein bestimmtes nummeriertes Rätsel
    #Füllt leere Zellen nacheinander und gibt True zurück, wenn alle leeren Zellen gefüllt sind.(Falsch, wenn nicht gefüllt)
    def solve(self):
        #Eliminierungsmethode:Füllen Sie den Bereich aus, für den nur einer entschieden ist
        while True:
            ls = []
            for i, j in itertools.product(range(9), repeat=2):
                if self.matrix[i][j] != 0: continue

                numbers = self.__find_numbers(i, j)
                if len(numbers) == 1: ls.append((i, j, numbers[0]))

            if len(ls) == 0: break
            for i, j, number in ls: self.matrix[i][j] = number


        blanks = [(i, j) for i, j in itertools.product(range(9), repeat=2) if self.matrix[i][j] == 0]
        if len(blanks) == 0: return True #Wenn alle Felder bereits ausgefüllt sind

        first_i, first_j = blanks[0]
        stack = [(0, first_number) for first_number in self.__find_numbers(first_i, first_j)]

        #Backtrack-Methode:
        #     1.Geben Sie eine Zahl in ein Leerzeichen ein
        #     2.Finden Sie heraus, ob sich in der nächsten leeren Zelle eine Nummer befindet
        #     3. 2.Wenn Sie nicht eingeben, gehen Sie zurück
        while stack:
            idx, number = stack.pop()
            i, j = blanks[idx]
            self.matrix[i][j] = number

            if idx == len(blanks) - 1: return True

            next_i, next_j = blanks[idx + 1]
            next_numbers = self.__find_numbers(next_i, next_j)

            #Zurück verfolgen
            if len(next_numbers) == 0:
                stack_top_idx = stack[-1][0]
                for temp_idx in range(stack_top_idx, idx + 1):
                    temp_i, temp_j = blanks[temp_idx]
                    self.matrix[temp_i][temp_j] = 0

            stack.extend((idx + 1, next_number) for next_number in next_numbers)

        return False

    #Speichern Sie die Nummer, die in einer bestimmten Zelle im Set abgelegt werden kann
    def __find_numbers(self, i, j):
        used_numbers = set()
        #Untersuchen Sie dieselbe Zeile und dieselbe Spalte
        for x in range(9): used_numbers |= {self.matrix[x][j], self.matrix[i][x]}

        #Untersuche denselben Block
        box_i_min, box_j_min = (i // 3) * 3, (j // 3) * 3
        for box_i, box_j in itertools.product(range(box_i_min, box_i_min + 3), \
                                              range(box_j_min, box_j_min + 3)):
            used_numbers.add(self.matrix[box_i][box_j])

        return set(range(1, 10)) - used_numbers

    def __str__(self):
        return "\n".join("".join(map(str, row)) for row in self.matrix)

if __name__ == "__main__":
    matrix = '''
        ..53.....
        8......2.
        .7..1.5..
        4....53..
        .1..7...6
        ..32....8.
        .6.5....9
        ..4....3.
        .....97..
    '''.split()

    sudoku = Sudoku()
    for i, j in itertools.product(range(9), repeat=2):
        if matrix[i][j] == ".": continue
        sudoku.matrix[i][j] = int(matrix[i][j])
    
    print(sudoku)
    sudoku.solve()
    print("========")
    print(sudoku)


# 005300000
# 800000020
# 070010500
# 400005300
# 010070006
# 003200080
# 060500009
# 004000030
# 000009700
# =========
# 145327698
# 839654127
# 672918543
# 496185372
# 218473956
# 753296481
# 367542819
# 984761235
# 521839764

Die Antwort ist die gleiche wie im GIGAZIN, also sollte es okay sein (`・ ω ・ ´) Shakin