[PYTHON] 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.
- Le même numéro ne doit pas exister dans une colonne
- Le même numéro ne doit pas exister sur une ligne
- Le même numéro ne doit pas exister dans un bloc
(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.
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
- Messe qui peut exister ... 1
- Une masse qui peut ne pas exister ... 0
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)
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. 
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