Essayez de résoudre le Sudoku à une vitesse explosive en utilisant Numpy

Qu'est-ce que le Sudoku

Sudoku est l'un des puzzles à crayon qui place les nombres de 1 à 9 dans un cadre carré 9x9 divisé en blocs 3x3. Aussi appelé "Number Place (Nampure)". (De Wikipedia)

Il semble.

Bien sûr, il ne remplit pas les chiffres sans réfléchir et il comporte les restrictions suivantes.

数独の解答.jpg (Je l'ai emprunté à un site qui résume des choses intéressantes et utiles en mathématiques)

Je voulais en faire un problème pour les juniors qui sont nouveaux dans la programmation, mais je vais l'écrire car il y avait peu d'articles qui ont été écrits de manière inattendue.

politique

Eh bien, cela fait simplement la même chose qu'un humain. Considérez le nombre suivant. 20090929101557.jpg

Par exemple, si vous recherchez 1, vous trouverez ** un endroit où seulement 1 peut tenir dans chaque colonne, ligne et bloc **.

Nous allons définir un indicateur indiquant que chaque numéro existe pour chaque cellule et coder le travail de recherche de colonnes, de lignes et de blocs pour lesquels le nombre total d'indicateurs est de 1.

Pour chaque carré, il y a un nombre spécifique

Dans l'Allemagne suprême mentionnée ci-dessus, l'indicateur d'existence peut être réglé sur "1" comme suit. (Ci-après, un tableau à deux dimensions qui suit ces règles est appelé une couche.) Ci-dessous une image. (Carrés rouges et numériques ... 0, verts ... 1)

asdfvar.jpg

Puis calculez le total pour chaque ligne, chaque colonne, chaque bloc. Avec cela, lorsque le total devient 1, le nombre sera confirmé **.

Dans cet exemple, vous pouvez trouver exactement trois emplacements à mettre à jour. fdvrvravger.jpg

De cette façon, il semble que cela puisse être résolu facilement en introduisant simplement le drapeau d'existence.

Maintenant, écrivons réellement le code.

Vérifiez chaque ligne

def check_row(layer):
    rows = np.where(np.sum(layer, axis=1)==1)[0]
    w = np.where(layer[rows] == 1)
    cols = w[1][np.argsort(w[0])]
    return rows, cols

De cette manière, essentiellement np.sum et np.where sont utilisés pour extraire les cellules qui remplissent les conditions.

Vérifiez chaque colonne

La même chose est vraie pour les colonnes.

def check_col(layer):
    cols = np.where(np.sum(layer, axis=0)==1)[0]
    w = np.where(layer[:,cols] == 1)
    rows = w[0][np.argsort(w[1])]
    return rows, cols

Vérifiez chaque grille

def check_grid(layer):
    rows, cols = list(), list()
    for row in range(3):
        for col in range(3):
            grid = self.layer[row*3:(row+1)*3, col*3:(col+1)*3 ]
            if np.sum(grid) == 1:
                point = np.where(grid==1)
                rows.append(point[0][0]+row*3)
                cols.append(point[1][0]+col*3)
    return rows, cols

Contrôle de fonctionnement

Maintenant, essayons les fonctions jusqu'à ce point.

layer = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 1, 0, 0, 1, 1, 0, 0, 0],
                  [1, 0, 0, 0, 1, 1, 0, 0, 0],
                  [0, 0, 0, 0, 0, 1, 0, 0, 0],
                  [0, 0, 0, 0, 1, 1, 0, 0, 1],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 1, 0, 0, 0, 0, 0, 0, 1],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [1, 1, 0, 0, 0, 0, 1, 0, 1]])
print(check_row(layer))
#(array([3], dtype=int64), array([5], dtype=int64))

print(check_col(layer))
#(array([8], dtype=int64), array([6], dtype=int64))

print(check_grid(layer))
#([4], [8])

Ça marche bien.

Vérifiez chaque couche

En fait, cela fonctionne déjà, mais comme c'est un gros problème, je vais ajouter une autre fonction.

Jusqu'à présent, nous nous sommes concentrés sur une seule couche. Cependant, comme Sugoku est composé de neuf nombres de 1 à 9, vous devriez également envisager de comparer les couches. En d'autres termes, ** dans n'importe quelle cellule, si l'indicateur d'existence est défini sur chaque couche dans une seule couche, l'emplacement peut être déterminé **.

def check_all_layer(layers):
    nums = list()
    sum_map = np.sum(layers, axis=0)
    if np.any(sum_map==1):
        rows, cols = np.where(sum_map==1)
        for row, col in zip(rows, cols):
            idx = np.where(layers[:,row,col])[0][0]
            nums.append(idx+1)
    return rows, cols, nums

layers = np.zeros((9,9,9))
layers[3,5,7] = 1

print(check_all_layer(layers))
#(array([5], dtype=int64), array([7], dtype=int64), [4])

Mettre à jour lorsqu'un numéro est attribué

Lorsque les numéros sont finalisés, les couches doivent également être mises à jour. En considérant une couche de matrice 3D 9x9x9, la fonction de mise à jour de la couche peut être écrite comme suit:

def update(layers, idx, row, col):
    layers[idx,row, : ] = 0 #Direction de la ligne
    layers[idx, : ,col] = 0 #Direction de la colonne
    layers[ : ,row,col] = 0 #Direction du calque
    row, col = row//3*3, col//3*3
    layers[idx, row:row+3, col:col+3] = 0 #intervalle

finalement

Je ne l'ai pas du tout vérifié car c'est juste un petit code que j'ai écrit quand j'étais excité de parler avec mes seniors Si vous avez des erreurs, veuillez me contacter.

Merci d'avoir lu jusqu'au bout.

Code réel

Comme il a été implémenté dans une classe, il est légèrement différent du code ci-dessus, mais cela résoudra le nombre en environ 0,01 seconde.

Je l'ai écrit avec de la colle, donc je n'ai pas du tout confirmé l'opération, mais ça marche probablement.

sudoku.py



class sudoku_solver(object):
    def __init__(self, question):
        self.p = np.array(problem)
        self.layer = np.ones((9,9,9))
        self.__init_layer()
        self.update_list = list()

    def solve(self):
        count=0
        while np.sum(self.layer)!=0 or count<100:
            for i in range(9):
                self.check_row(i)
                self.check_col(i)
                self.check_grid(i)
            self.check_all_layer()
            self.__update()
            count+=1

    #Fonction de mise à jour
    def __update(self):
        for idx, row, col in self.update_points:
            self.__update_point(idx, row, col)
        self.update_points=list()

    def __update_point(self, idx, row, col):
        #Mise à jour de la réponse
        self.p[row, col] = idx+1
        #Mise à jour de la couche
        self.layer[idx,row, : ] = 0 #Direction de la ligne
        self.layer[idx, : ,col] = 0 #Direction de la colonne
        self.layer[ : ,row,col] = 0 #Direction du calque
        row, col = row//3*3, col//3*3
        self.layer[idx, row:row+3, col:col+3] = 0 #intervalle

    #Fonction d'initialisation de couche
    def __init_layer(self):
        for idx in range(9):
            (rows, cols) = np.where(self.p==idx+1)
            for row, col in zip(rows, cols):
                self.__update_point(idx, row, col)

    #Fonction de confirmation de ligne
    def check_row(self, idx):
        rows = np.where(np.sum(self.layer[idx], axis=1)==1)[0]
        w = np.where(self.layer[idx][rows] == 1)
        cols = w[1][np.argsort(w[0])]

        for row, col in zip(rows, cols):
            self.update_list.append((idx, row, col))

    #Fonction de confirmation de colonne
    def check_col(self, idx):
        cols = np.where(np.sum(self.layer[idx], axis=0)==1)[0]
        w = np.where(self.layer[idx][:,cols] == 1)
        rows = w[0][np.argsort(w[1])]

        for row, col in zip(rows, cols):
            self.update_list.append((idx, row, col))

    #Fonction de confirmation de plage
    def check_grid(self, idx):
        for row in range(3):
            for col in range(3):
                grid = self.layer[idx, row*3:(row+1)*3, col*3:(col+1)*3 ]
                if np.sum(grid) == 1:
                    point = np.where(grid==1)
                    row = point[0][0]+row*3
                    col = point[1][0]+col*3
                    self.update_list.append((idx,row,col))

    #Fonction de confirmation de direction de couche
    def check_all_layer(self):
        sum_map = np.sum(self.layer, axis=0)
        if np.any(sum_map==1):
            rows, cols = np.where(sum_map==1)
            for row, col in zip(rows, cols):
                idx = np.where(self.layer[:,row,col])[0][0]
                self.update_list.append((idx,row,col))

Recommended Posts

Essayez de résoudre le Sudoku à une vitesse explosive en utilisant Numpy
Essayez l'analyse de corrélation multivariée à l'aide du lasso graphique à une vitesse explosive
Créez des projets d'apprentissage automatique à une vitesse explosive à l'aide de modèles
Essayez de le résoudre de différentes manières (SAT, CSP)
Implémentez l'API à une vitesse explosive en utilisant Django REST Framework
Je veux résoudre SUDOKU
Créez un serveur Web API à une vitesse explosive en utilisant HUG
Essayez d'utiliser pynag pour configurer Nagios
Essayez d'obtenir des statistiques en utilisant e-Stat
Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules
Essayez de détecter les mouvements de fusion en utilisant AnyMotion
Essayez d'utiliser Excel en utilisant Python (Xlwings)
J'ai essayé de laisser optuna résoudre le nombre
Essayez de résoudre le problème du fizzbuzz avec Keras
Comment créer des fichiers volumineux à haute vitesse
Essayez d'utiliser django-import-export pour ajouter des données csv à django
Modèle Python qui effectue une analyse des journaux à une vitesse explosive
Essayez de résoudre le problème de l'héritage de classe Python
Essayez d'utiliser Blueprint avec Flask pour séparer les contrôleurs
Comment accélérer Scicit-Learn comme Conda Numpy
Essayez de résoudre le diagramme homme-machine avec Python
J'ai essayé d'utiliser PyCaret à la vitesse la plus rapide
Essayez de créer un serveur HTTP en utilisant Node.js
Chaque fois que j'essaye de lire un fichier csv en utilisant des pandas, j'obtiens une erreur numpy.