[PYTHON] 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.
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.
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
