Implémentation de Supreme Solver dans Python 3

L'autre jour, en surfant sur le net, j'ai trouvé l'article suivant: "Le numéro le plus difficile au monde créé par un expert en mathématiques sur 3 mois" .. Que ce soit vrai ou non, j'ai essayé de résoudre ce problème avec Python3. La méthode backtrack est utilisée pour l'implémentation. En bref, cela signifie que vous résolvez par la force (´ ・ ω ・ `)

import itertools

class Sudoku(object):
    def __init__(self):
        self.matrix = [[0 for _ in range(9)] for _ in range(9)] #0 si vide
    
    #Résolvez un puzzle numéroté donné
    #Remplit les cellules vides les unes après les autres et renvoie True si toutes les cellules vides sont remplies.(Faux si non rempli)
    def solve(self):
        #Méthode d'élimination:Remplissez l'espace qui est décidé un seul
        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 #Si tous les carrés sont déjà remplis

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

        #Méthode Backtrack:
        #     1.Mettez un nombre dans un espace vide
        #     2.Découvrez s'il y a un nombre dans la cellule vide suivante
        #     3. 2.Si vous n'entrez pas, revenez en arrière
        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)

            #Piste arrière
            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

    #Stocker le numéro qui peut être mis dans une certaine cellule dans l'ensemble
    def __find_numbers(self, i, j):
        used_numbers = set()
        #Examiner la même ligne et la même colonne
        for x in range(9): used_numbers |= {self.matrix[x][j], self.matrix[i][x]}

        #Examinez le même bloc
        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

La réponse est la même que GIGAZINE, donc ça devrait aller (`・ ω ・ ´) Shakin