Résolvez le nombre d'Allemands avec une recherche prioritaire en profondeur. La priorité de la création de programme est
Je l'ai fait dans l'ordre de. Je sacrifie la vitesse.
Il est représenté par un tableau général à deux dimensions.
def values_from_grid(grid):
"Créer des valeurs de tableau bidimensionnelles à partir de texte"
values = []
digits = "123456789"
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
grid_int = map(lambda x: int(x) if x != "." else 0, chars)
count = 0
row = []
for i in grid_int:
row.append(i)
count += 1
if count % 9 == 0: #Fractionner ligne par ligne
values.append(row)
row = []
return values
Une fonction qui lit le texte et le convertit en un tableau à deux dimensions. Le format du texte est un blanc représenté par 0 ou., Et les autres nombres sont enregistrés dans l'ordre. Si c'est 81 caractères, c'est OK. Il correspond aux formats de texte suivants.
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Vérifiez récursivement avec la recherche de priorité de profondeur. Comment appeler
values = values_from_grid(Données suprêmes)
solver(values)
est. Transmettez les valeurs à la fonction de solveur. Après résolution, values est un tableau de réponses.
De la cellule supérieure gauche à la cellule inférieure droite, appliquez les nombres 1 à 9 un par un. À ce stade, le nombre n'est appliqué que lorsque le nombre à appliquer n'est pas dans le carré "vertical / horizontal / 3x3". x est l'axe horizontal et y est l'axe vertical. Lorsque x atteint 8, c'est-à-dire lorsqu'il atteint la fin de l'axe horizontal Vérifiez la première cellule de la rangée du bas avec l'axe vertical vers le bas et l'axe horizontal défini sur 0. Lorsque la dernière cellule est atteinte, le problème a été résolu et True est renvoyé.
def solver(values, x=0, y=0):
"Résolvez le nombre"
if y > 8: #Terminé lorsque le pointeur atteint la fin
return True
elif values[y][x] != 0: #S'il n'est pas vide, ignorez-le
if x == 8: #Passer à la ligne suivante après avoir atteint 8 colonnes
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
else:
for i in range(1, 10):#Essayez tous les nombres de 1 à 9
if check(values, x, y, i): #Vérifier
values[y][x] = i #Si OK, entrez un nombre
if x == 8: #Passer à la ligne suivante après avoir atteint 8 colonnes
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
values[y][x] = 0 #Revenir à 0 lors du retour
return False
La valeur de retour est «True» ou «False». Si vous pouvez le résoudre, c'est "True".
Vérifiez la zone de l'axe horizontal, de l'axe vertical et de 3 * 3. Une fonction qui appelle chaque fonction.
def check(values, x, y, i):
if row(values, y, i) and column(values, x, i) and block(values, x, y, i):
return True
return False
Prend la valeur de l'axe vertical indiquant la ligne actuelle comme argument pour vérifier l'axe horizontal. i est le nombre que vous essayez d'entrer. Vérifiez l'axe horizontal un par un, s'il est le même que le nombre que vous essayez d'entrer, Faux, sinon Créez une liste de True et vérifiez-la avec la fonction all. Si tous sont True, True est renvoyé sans duplication de nombres. S'il y a ne serait-ce qu'un doublon, False est renvoyé.
def row(values, y, i):
"Vérifiez le côté"
return all(True if i != values[y][_x] else False for _x in range(9))
Je viens de changer la vérification de l'axe horizontal en axe vertical.
def column(values, x, i):
"Vérifier la verticale"
return all(True if i != values[_y][x] else False for _y in range(9))
La fonction suivante a été créée en référence à Implémentation d'un solveur allemand en Python. En divisant le nombre de 0 à 8 par 3 et en multipliant la valeur avec les fractions supprimées par 3, on obtient respectivement 0, 3 et 6. La théorie est que vous pouvez voir le bloc auquel appartient le carré.
def block(values, x, y, i):
"Vérifier les blocs 3x3"
xbase = (x // 3) * 3
ybase = (y // 3) * 3
return all(True if i != values[_y][_x] else False
for _y in range(ybase, ybase + 3)
for _x in range(xbase, xbase + 3))
problème
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Répondre
[8, 5, 9, 6, 1, 2, 4, 3, 7]
[7, 2, 3, 8, 5, 4, 1, 6, 9]
[1, 6, 4, 3, 7, 9, 5, 2, 8]
[9, 8, 6, 1, 4, 7, 3, 5, 2]
[3, 7, 5, 2, 6, 8, 9, 1, 4]
[2, 4, 1, 5, 9, 3, 7, 8, 6]
[4, 3, 2, 9, 8, 1, 6, 7, 5]
[6, 1, 7, 4, 2, 5, 8, 9, 3]
[5, 9, 8, 7, 3, 6, 2, 4, 1]
Ce programme a pris environ 23 secondes dans mon environnement pour résoudre ce puzzle. D'autre part, le programme dans Résoudre n'importe quel puzzle de Sudoku le résout en 0,01 seconde. C'est Résolvez tous les puzzles allemands. Ceci est dû au fait que la stratégie de «remplissage» est exécutée et que les carrés qui ne sont toujours pas remplis sont recherchés uniquement pour les valeurs qui peuvent être prises pour chaque carré pour trouver une solution. Ce programme vérifie de 1 à 8 même s'il ne contient que 9 carrés, et lors de la vérification des carrés verticaux, horizontaux et 3x3, des carrés se chevauchent, mais ils sont également vérifiés individuellement. Faire. Donc c'est lent.
Résolvez tous les puzzles allemands Implémentation d'un solveur allemand en Python
Recommended Posts