Résolution du plus petit indice numba du monde avec Numpy & Numba

introduction

J'ai l'impression d'être épuisé par la résolution de maths avec Python, mais j'ai décidé d'écrire un article car ce serait un code qui n'existe que dans ma mémoire. (La raison principale est que c'était pénible d'écrire un article, mais je vais l'écrire parce que les vacances de printemps ont été prolongées d'un mois à Corona et j'ai beaucoup de temps.)

politique

Recherche de priorité de profondeur. Mettez temporairement les nombres qui satisfont aux conditions de l'allemand suprême dans les cellules vides par ordre croissant. Essayez de faire la même chose avec d'autres carrés, même si vous les mettez. S'il y a une contradiction quelque part, corrigez l'hypothèse faite juste avant. Ceci est répété sérieusement. Un jour, la contradiction ne se produira pas et tous les blancs seront remplis avec les valeurs supposées. C'est la bonne réponse.

image.png Source de la figure

la mise en oeuvre

Vérifier que les hypothèses répondent aux exigences de l'Allemagne

«Index» est compté de 0 à 81 du coin supérieur gauche vers la droite. En prenant la figure ci-dessus à titre d'exemple, l '«index» des nombres roses «5, 3, 6, 9, 8» dans le bloc 3x3 supérieur gauche est «0, 1, 9, 19, 20», respectivement.

def fillable(table, index, value):
    """Dans la matrice en cours de calcul, vérifiez si la valeur supposée être la bonne réponse satisfait à la condition de plusieurs Allemands.

    Parameters
    -------
        table : np.ndarray of int
La matrice en cours de calcul. 2D-array。
        index : int
L'emplacement du carré supposé. La 1ère ligne est 0~8,La deuxième ligne est 9~17, ...
        value : int
Numéro supposé.

    Returns
    -------
        bool
Est-il possible que l'hypothèse soit correcte dans la matrice en cours de calcul?
    """

    row = index // 9
    col = index % 9

    fillable_in_row = value not in table[row, :]
    fillable_in_col = value not in table[:, col]
    fillable_in_block = value not in table[
                                     (row // 3) * 3: (row // 3 + 1) * 3,
                                     (col // 3) * 3: (col // 3 + 1) * 3,
                                     ]

    return fillable_in_row and fillable_in_col and fillable_in_block

Je pense que c'est une implémentation assez naturelle car elle n'utilise que la syntaxe de base de Python.

En supposant

def fill(table_flat):
    """Résolvez le nombre d'Allemands par recherche de priorité de profondeur.

    Parameters
    -------
        table_flat : np.ndarray of int
Le problème de plusieurs Allemands. 1D-array

    Returns
    -------
        np.ndarray of int
Une matrice à laquelle les hypothèses sont attribuées. forme= (9, 9)
    """

    for tmp_i, tmp_val in enumerate(table_flat):

        if tmp_val == 0:
            fillable_vals = [val
                             for val in range(tmp_val + 1, 10)
                             if fillable(table_flat.reshape(9, 9), tmp_i, val)]

            for new_val in fillable_vals:
                table_flat[tmp_i] = new_val

                if fill(table_flat).all():
                    break
            else:
                table_flat[tmp_i] = 0
                break
    return table_flat.reshape(9, 9)

Je vais l'expliquer ligne par ligne.

Considérez dans l'ordre du carré avec le plus petit indice.

for tmp_i, tmp_val in enumerate(table_flat):

J'ai oublié de le dire, mais je suppose que vous le saisissez sous la forme «espace vide de question == 0». Par conséquent, ce processus doit être envisagé uniquement lorsque la cellule est vide.

if tmp_val == 0:

Une notation d'inclusion de liste légèrement plus longue. Les hypothèses suivantes devraient être supérieures aux hypothèses actuelles. Cependant, l'hypothèse qui ne remplit pas les conditions de Susumu est supprimée. La vérification utilise la fonction «fillable». De plus, j'ai oublié de mentionner que «index» est plus facile à faire avec des nombres qu'avec des tapples, donc l'entrée du problème est supposée être un vecteur 1x81 d'une matrice 9x9 (aplatir). Cependant, comme il est nécessaire d'extraire en blocs 3x3 selon les règles, remodeler uniquement à ce moment.

fillable_vals = [val
                 for val in range(tmp_val + 1, 10)
                 if fillable(table_flat.reshape(9, 9), tmp_i, val)]

Essayez de remplacer le nombre de réponses correctes possibles dans le carré.

for new_val in fillable_vals:
    table_flat[tmp_i] = new_val

** C'est le point. ** ** Tout d'abord, l'instruction «for / else» sera décrite. Entre l'instruction ʻelse lorsque l'instruction forse termine normalement. Le cas où l'instruction «for» n'est pas terminée est lorsque l'instruction «for» n'est pas encore terminée mais que «break» se produit. Au fait, même lorsque l'instructionfor est inactive, elle se termine normalement, donc elle entre l'instruction ʻelse. Donc, ici, vous devez faire attention à la position de break.

Réexécute la matrice supposée comme argument de la fonction fill. numpy.ndarray.all () renvoie True s'il n'y a pas de nombres différents de zéro. Cette fois, l'espace vide du problème est défini sur == 0, donc en d'autres termes, le comportement de ʻall () peut être reformulé en numérologie. S'il n'est pas résolu, remettez la valeur de masse supposée à 0 et terminez l'examen. Si vous faites return avec la valeur retournée à 0, il sera transmis à ʻif fill (table_flat) .all ():` et le processus pour corriger l'hypothèse sera exécuté.

    for ~~~Abréviation~~~:
     ~~~Abréviation~~~
        if fill(table_flat).all():
            break
    else:
        table_flat[tmp_i] = 0
        break
return table_flat.reshape(9, 9)

Méthode d'exécution

Il peut être exécuté en organisant la fonction «fill» et la fonction «fillable» dans le même fichier, et en plaçant le vecteur d'ordre 81 avec la ligne numéro un dans l'argument de la fonction «fill».

Accélérer (le plus petit problème d'indice au monde)

Même à l'heure actuelle, les problèmes ordinaires peuvent être résolus en quelques millisecondes à quelques secondes. Cependant, il a été vaincu par un problème. C'est le plus petit indice au monde de l'Allemagne. image.png

Lorsque j'ai essayé de résoudre ce problème avec le code actuel, je me suis senti désolé pour mon ordinateur. J'ai décidé d'accélérer avec numba ici.

Modifications ① import

ʻImport` numba au début du fichier

from numba import njit, int64, bool_

Changement (2) Ajout d'un décorateur

Définissez les types d'entrée et de sortie comme @ njit (sortie, entrée). ** C'était l'endroit le plus bondé cette fois. ** Si vous voulez utiliser numpy.ndarray.reshape (), vous devez utiliser ʻint64 [:: 1] . (Il a été écrit quelque part dans la documentation officielle de numba. [Ici](http://numba.pydata.org/numba-doc/0.12.1/tutorial_firststeps.html#signature).) En fait, ʻint8 semble être bon au lieu de ʻint64, mais cela n'a pas fonctionné alors je l'ai laissé par défaut. (Est-il spécifié comme dtype = int8`?)

#Une fonction qui entre un tableau bidimensionnel de int et deux ints et retourne bool
@njit(bool_(int64[:, :], int64, int64))
def fillable(table, index, value):

#Une fonction qui entre un tableau unidimensionnel de int et retourne un tableau bidimensionnel de int
@njit(int64[:, :](int64[::1]))
def fill(table_flat):

Modifier ③ Supprimer l'opération ʻin`

numba devrait supporter un peu la syntaxe Python, mais j'ai eu une erreur avec l'opération ʻin dans la fonction fillable. (Fillable_in_row = valeur absente de la table [row,:]` etc.) Par conséquent, la fonction «fillable» a été réimplémentée sans utiliser l'opération «in».

def fillable(table, index, value):

    row = index // 9
    col = index % 9
    block = lambda x: ((x // 3) * 3, (x // 3 + 1) * 3)

    same_in_areas = False
    for area in [
        table[row, :], table[:, col],
        table[block(row)[0]:block(row)[1], block(col)[0]:block(col)[1]].flatten()
    ]:
        for i in area:
            same_in_areas |= (i == value)

    return not same_in_areas

L'instruction «for» «in» semble correcte. Mettez le nombre entré dans les blocs verticaux et horizontaux de la cellule que vous voulez vérifier dans ʻi` et tournez-le. On vérifie si le «i» correspond à la valeur supposée «valeur», c'est-à-dire que le même nombre existe dans les blocs verticaux et horizontaux et ne satisfait pas la condition du nombre. Dans ce cas, l'erreur numba ne s'est pas produite.

Code entier

suudoku.py


def fillable(table, index, value):
    """Dans la matrice en cours de calcul, vérifiez si la valeur supposée être la bonne réponse satisfait à la condition de plusieurs Allemands.

    Parameters
    -------
        table : np.ndarray of int
La matrice en cours de calcul. 2D-array。
        index : int
L'emplacement du carré supposé. La 1ère ligne est 0~8,La deuxième ligne est 9~17, ...
        value : int
Numéro supposé.

    Returns
    -------
        bool
Est-il possible que l'hypothèse soit correcte dans la matrice en cours de calcul?
    """

    row = index // 9
    col = index % 9

    fillable_in_row = value not in table[row, :]
    fillable_in_col = value not in table[:, col]
    fillable_in_block = value not in table[
                                     (row // 3) * 3: (row // 3 + 1) * 3,
                                     (col // 3) * 3: (col // 3 + 1) * 3,
                                     ]

    return fillable_in_row and fillable_in_col and fillable_in_block


def fill(table_flat):
    """Résolvez le nombre d'Allemands par recherche de priorité de profondeur.

    Parameters
    -------
        table_flat : np.ndarray of int
Le problème de plusieurs Allemands. 1D-array

    Returns
    -------
        np.ndarray of int
Une matrice à laquelle les hypothèses sont attribuées. forme= (9, 9)
    """

    for tmp_i, tmp_val in enumerate(table_flat):

        if tmp_val == 0:
            fillable_vals = [val
                             for val in range(tmp_val + 1, 10)
                             if fillable(table_flat.reshape(9, 9), tmp_i, val)]

            for new_val in fillable_vals:
                table_flat[tmp_i] = new_val

                if fill(table_flat).all():
                    break
            else:
                table_flat[tmp_i] = 0
                break
    return table_flat.reshape(9, 9)

suudoku_faster.py


from numba import njit, int64, bool_


@njit(bool_(int64[:, :], int64, int64))
def fillable(table, index, value):

    row = index // 9
    col = index % 9
    block = lambda x: ((x // 3) * 3, (x // 3 + 1) * 3)

    same_in_areas = False
    for area in [
        table[row, :], table[:, col],
        table[block(row)[0]:block(row)[1], block(col)[0]:block(col)[1]].flatten()
    ]:
        for i in area:
            same_in_areas |= (i == value)

    return not same_in_areas


@njit(int64[:, :](int64[::1]))
def fill(table_flat):

    for tmp_i, tmp_val in enumerate(table_flat):

        if tmp_val == 0:
            fillable_vals = [val
                             for val in range(tmp_val + 1, 10)
                             if fillable(table_flat.reshape(9, 9), tmp_i, val)]

            for new_val in fillable_vals:
                table_flat[tmp_i] = new_val

                if fill(table_flat).all():
                    break
            else:
                table_flat[tmp_i] = 0
                break
    return table_flat.reshape(9, 9)

suudoku_input.py


from suudoku import fill as fill_slow
from suudoku_faster import fill as fill_fast
import matplotlib.pyplot as plt
import numpy as np
from time import time

table =  [0, 0, 0, 8, 0, 1, 0, 0, 0,
          0, 0, 0, 0, 0, 0, 4, 3, 0,
          5, 0, 0, 0, 0, 0, 0, 0, 0,
          0, 0, 0, 0, 7, 0, 8, 0, 0,
          0, 0, 0, 0, 0, 0, 1, 0, 0,
          0, 2, 0, 0, 3, 0, 0, 0, 0,
          6, 0, 0, 0, 0, 0, 0, 7, 5,
          0, 0, 3, 4, 0, 0, 0, 0, 0,
          0, 0, 0, 2, 0, 0, 6, 0, 0]

#Le premier tour de numba comprend non seulement le temps de calcul mais aussi le temps de compilation, alors laissez-le tourner au ralenti une fois.
fill_fast(np.array(table).copy())

start = time()
ans = fill_fast(np.array(table).copy())
finish = time()

print("répondre")
print(ans)
print()
print(f"Temps de calcul(sec): {finish - start:5.7}")

fig, ax = plt.subplots(figsize=(6, 6))
fig.patch.set_visible(False)
ax.axis("off")

colors = np.where(table, "#F5A9BC", "#ffffff").reshape(9, 9)
picture = ax.table(cellText=ans, cellColours=colors, loc='center')
picture.set_fontsize(25)
picture.scale(1, 3)

ax.axhline(y=0.340, color="b")
ax.axhline(y=0.665, color="b")
ax.axvline(x=0.335, color="b")
ax.axvline(x=0.665, color="b")

fig.tight_layout()
plt.show()

production

Si c'est un problème normal, cela prend environ 0,01 seconde, mais quel type de problème prend 100 secondes ... En passant, ce numéro le plus difficile au monde peut être résolu normalement.

répondre
[[2 3 4 8 9 1 5 6 7]
 [1 6 9 7 2 5 4 3 8]
 [5 7 8 3 4 6 9 1 2]
 [3 1 6 5 7 4 8 2 9]
 [4 9 7 6 8 2 1 5 3]
 [8 2 5 1 3 9 7 4 6]
 [6 4 2 9 1 8 3 7 5]
 [9 5 3 4 6 7 2 8 1]
 [7 8 1 2 5 3 6 9 4]]

Temps de calcul(sec): 101.6835

image.png

Recommended Posts

Résolution du plus petit indice numba du monde avec Numpy & Numba
Trouvez le plus petit index qui atteint le seuil de somme cumulée avec numpy
Mathématiques Todai 2016 résolues avec Python
Trouvez la position au-dessus du seuil avec NumPy