Bonjour à tous. Aujourd'hui, je vais expliquer un programme qui produit des réponses de plusieurs Allemands en utilisant une méthode appelée recherche de priorité en profondeur. Il est difficile d'expliquer l'exemple, veuillez donc nous le faire savoir dans les commentaires s'il y a des lacunes dans l'article.
n est un nombre naturel et N = n ^ 2. À ce stade, créez un tableau composé d'un total de N ^ 2 carrés avec N lignes et N colonnes horizontalement, puis divisez-le en n ^ 2 sections constituées de n lignes et n colonnes avec des lignes épaisses. 
À ce stade, écrivez un nombre de 1 à N dans chaque cellule. Cependant, toutes les trois conditions suivantes doivent être remplies.
Il y a une carte (problème) dans laquelle les nombres sont écrits à mi-chemin, comme dans [Exemple d'entrée 1] et [Exemple d'entrée 2] ci-dessous. Écrivez les nombres naturels 1, 2, 3, ..., N dans les espaces vides de ces cartes et créez un programme qui génère les cartes (réponses) qui satisfont aux conditions ci-dessus (A) à (C).
Comment créer un programme pour créer une réponse dans Supreme peut être grossièrement divisé en deux étapes.
La raison pour laquelle on n'examine que les carrés (y, x) en 1 ci-dessus est que la récurrence ne se produit pas. (D'après mon expérience, les nombres sont entrés dans un seul carré)
Commencez par créer un programme pour vérifier si les nombres 1 à N sont utilisés un par un dans la colonne verticale x.
Dans les carrés (x, 0), (x, 1), ..., (x, N-1), comptez le nombre de 1 à N dans le tableau. À ce stade, True est renvoyé si chaque nombre est utilisé un par un, 1 est 1 et 2 est 1 ... N est 1 et False est renvoyé s'il n'est pas utilisé.
```python
#Découvrez si la réponse est dans la colonne
def checkQuestionRow(self,Row):
#Un tableau qui stocke le nombre de nombres compris entre 1 et N
num = [0 for m in range((self.N + 1))]
#Vertical 0e colonne-vertical(N-1)Scannez jusqu'à la colonne
for x in range(0,self.N):
#Découvrez combien de 1 à N sont inclus
for m in range(1,self.N+1):
#(x,Row)Lorsque la valeur du carré est m
if m == self.question[x][Row]:
#Le nombre est le nombre de m+1
num[m] = num[m] + 1
#Colonne(x)Renvoie False si plus d'un nombre est utilisé dans
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
```
Ici, le même jugement que dans le cas de la verticale (colonne) peut être effectué. ```python def checkQuestionCol(self,Col): #Un tableau qui stocke le nombre de nombres compris entre 1 et N num = [0 for m in range((self.N + 1))] #Horizontal 0ème ligne-horizontal(N-1)Scannez vers la ligne for y in range(0,self.N): for m in range(1,self.N+1): if m == self.question[Col][y]: num[m] = num[m] + 1 #Renvoie False si plus d'un nombre est utilisé dans la ligne for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Les blocs sont considérés comme des blocs de colonnes verticaux, des blocs de lignes horizontaux, etc. Par exemple, dans le cas de 4 * 4 (n = 2, N = 4), les lignes épaisses viennent au 0e et au 2e. La ligne épaisse est 1 <= k <= n à la fois verticalement et horizontalement, et elle arrive à la (k * n-1) ème place. , K * nth est le point de départ, k * (n + 1) est le point final.
Remplacez ce k par colBlock et rowBlock, et vérifiez si les nombres 1 à N sont inclus un par un du point de départ au point final des blocs verticaux et horizontaux. ```python # 2*2，3*Vérifiez si un chiffre de 1 à N apparaît pour chaque bloc de 3 def checkQuestionBlock(self,rowBlock,colBlock): #Point de départ du bloc(colBlock* n ,rowBlock* n)Définir startCol = colBlock * self.n startRow = rowBlock * self.n #Point final du bloc(colBlock* {n+1} ,rowBlock* {n+1})Définir endCol = (colBlock + 1) * (self.n) endRow = (rowBlock + 1) * (self.n) #Un tableau qui stocke le nombre de nombres compris entre 1 et N num = [0 for m in range((self.N + 1))] #Analyser bloc par bloc for y in range(startCol,endCol): for x in range(startRow,endRow): for m in range(1,self.N+1): if m == self.question[y][x]: num[m] = num[m] + 1 #Renvoie False si plus d'un nombre est utilisé dans le bloc for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Enfin, toutes les conditions (A) à (C) sont résumées. Si l'un des éléments (A) à (C) n'est pas satisfait, False est renvoyé. ```python #Courant(x,y)Découvrez si la solution est correcte def checkQuestion(self,x,y):
#Tout d'abord, vérifiez si toutes les lignes contiennent des nombres de 1 à N
if self.checkQuestionRow(x) == False:
return False
#Ensuite, vérifiez si toutes les colonnes contiennent des nombres de 1 à N.
if self.checkQuestionCol(y) == False:
return False
#Enfin, vérifiez si chaque bloc contient un nombre de 1 à N
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
<h2> 2: Placez un nombre dans le carré (Recherche en profondeur d'abord) </ h2>
<p> Suivez la procédure ci-dessous pour placer des nombres dans les carrés de quelques Allemands. </ p>
<ol> <li> Ecrivez la condition de terminaison de récursive. Principalement lorsque la colonne atteint N, la récursive est coupée. </ li> <li> Si un nombre est déjà placé dans le carré (y, x), le carré (y, x + 1). Lorsqu'il est déjà à la fin du côté, il revient au carré (0, y + 1). </ li> <li> Si le carré (y, x) n'a pas déjà de nombre, essayez d'abord de mettre un nombre de 1 à N dans le carré (y, x). En conséquence de sa mise, True est retourné lorsque les conditions (A) à (C) sont satisfaites. De plus, reculez vers le carré (y, x + 1) ou (0, y + 1) de la même manière qu'en 2. </ li> <li> 3. Si tous les nombres de 1 à N ne remplissent pas les conditions du carré (y, x), avant de mettre la valeur du carré (y, x) dans {0} revenir. </ li> </ ol>
<p> De cette façon, en creusant les uns après les autres, et si les conditions ne sont pas remplies, revenez en arrière et reconsidérez la méthode de recherche comme <b> Depth-First Search </ b>. Dire. </ p>
```python
#Recherchez un certain nombre de solutions allemandes plutôt qu'une recherche prioritaire
def solve(self,question,x=0,y=0):
#Fin récursive lorsque vous atteignez la colonne suivante après la dernière colonne
if x == 0 and y == self.N:
return True
#Lorsqu'un nombre est déjà placé dans le carré
if self.question[y][x] != 0:
#Lorsque vous atteignez la dernière ligne, regardez le début de la colonne suivante
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Examinez la ligne suivante si ce n'est pas la dernière ligne
else:
if self.solve(self.question,x+1,y):
return True
#Quand aucun nombre n'est placé dans le carré
else:
for m in range(1,self.N+1):
#Tout d'abord, massez le nombre i(x,y)Temporairement mis en
self.question[y][x] = m
#Si le jugement est rendu, la masse(x,y)Déterminer la valeur de avec m
if self.checkQuestion(x,y) == True:
self.question[y][x] = m
#Pour le débogage
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(m) + ")")
#Lorsque vous atteignez la dernière ligne, regardez le début de la colonne suivante
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Examinez la ligne suivante si ce n'est pas la dernière ligne
else:
if self.solve(self.question,x+1,y):
return True
#Si le jugement ne passe pas, restaurez les carrés
self.question[y][x] = 0
return False
* Lors de la création du programme pour cette partie, @ wsldenli " Résoudre les mathématiques avec Python -Qiita J'ai imité.
Sudoku.py
import os
import sys
class Sudoku():
#Initialiser les données
def __init__(self):
#Petite taille de cadre
self.n = 2
#Définir le contour et la fin du numéro
self.N = self.n * self.n
#Initialisez tous les tableaux de problèmes avec 0
self.question = [[0 for i in range((self.N))] for j in range((self.N))]
#Découvrez si la réponse est correcte pour rampant
def checkQuestionRow(self,Row):
#Un tableau qui stocke le nombre de nombres compris entre 1 et N
num = [0 for m in range((self.N + 1))]
#Horizontal 0ème ligne-horizontal(N-1)Scannez vers la ligne
for x in range(0,self.N):
#Découvrez combien de 1 à N sont inclus
for m in range(1,self.N+1):
#(x,Row)Lorsque la valeur du carré est m
if m == self.question[x][Row]:
#Le nombre est le nombre de m+1
num[m] = num[m] + 1
#Renvoie False si plus d'un nombre est utilisé dans la colonne Row
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Verticale:Vérifiez si les nombres 1 à N apparaissent un par un dans la colonne Col
#Basique, même comportement que checkQuestionRow
def checkQuestionCol(self,Col):
#Un tableau qui stocke le nombre de nombres compris entre 1 et N
num = [0 for m in range((self.N + 1))]
#Vertical 0e colonne-horizontal(N-1)Scannez jusqu'à la colonne
for y in range(0,self.N):
for m in range(1,self.N+1):
if m == self.question[Col][y]:
num[m] = num[m] + 1
#Renvoie False si plus d'un nombre est utilisé dans la colonne
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
# 2*2，3*Vérifiez si un chiffre de 1 à N apparaît pour chaque bloc de 3
def checkQuestionBlock(self,rowBlock,colBlock):
#Point de départ du bloc(colBlock* n ,rowBlock* n)Définir
startCol = colBlock * self.n
startRow = rowBlock * self.n
#Point final du bloc(colBlock* {n+1} ,rowBlock* {n+1})Définir
endCol = (colBlock + 1) * (self.n)
endRow = (rowBlock + 1) * (self.n)
#Un tableau qui stocke le nombre de nombres compris entre 1 et N
num = [0 for m in range((self.N + 1))]
#Analyser bloc par bloc
for y in range(startCol,endCol):
for x in range(startRow,endRow):
for m in range(1,self.N+1):
if m == self.question[y][x]:
num[m] = num[m] + 1
#Renvoie False si plus d'un nombre est utilisé dans le bloc
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Courant(x,y)Découvrez si la solution est correcte
def checkQuestion(self,x,y):
#Vérifiez d'abord si toutes les lignes Row contiennent des nombres jusqu'à N
if self.checkQuestionRow(x) == False:
return False
#Ensuite, vérifiez si toutes les colonnes Col contiennent des nombres de 1 à N.
if self.checkQuestionCol(y) == False:
return False
#Enfin, vérifiez si chaque bloc contient un nombre de 1 à N
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
#Recherchez un certain nombre de solutions allemandes plutôt qu'une recherche prioritaire
def solve(self,question,x=0,y=0):
#Fin récursive lorsque vous atteignez la colonne suivante après la dernière colonne
if x == 0 and y == self.N:
return True
#Lorsqu'un nombre est déjà placé dans le carré
if self.question[y][x] != 0:
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
else:
if self.solve(self.question,x+1,y):
return True
#Quand aucun nombre n'est placé dans le carré
else:
for m in range(1,self.N+1):
self.question[y][x] = m
#Pour le débogage
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
if self.checkQuestion(x,y) == True:
self.question[y][x] = m
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
else:
if self.solve(self.question,x+1,y):
return True
self.question[y][x] = 0
#Pour le débogage
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
return False
#Fonction principale
if __name__ == '__main__':
#Données de problème
Sudoku = Sudoku()
Sudoku.question =[[1,0,3,4],[3,0,0,2],[0,3,0,0],[2,0,0,3]]
# Sudoku.question =[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]
print("Question")
print(Sudoku.question)
Sudoku.solve(Sudoku.question,0,0)
print("Answer")
print(Sudoku.question)
Recommended Posts