Hallo an alle. Heute werde ich ein Programm erklären, das Antworten von mehreren Deutschen mit einer Methode namens Tiefenprioritätssuche ausgibt. Es ist schwierig, das Beispiel zu erklären. Bitte teilen Sie uns in den Kommentaren mit, ob der Artikel Mängel aufweist.
n ist eine natürliche Zahl und N = n ^ 2. Erstellen Sie zu diesem Zeitpunkt eine Tafel, die aus insgesamt N ^ 2 Quadraten mit N Zeilen und N Spalten horizontal besteht, und teilen Sie sie weiter in n ^ 2 Abschnitte auf, die aus n Zeilen und n Spalten mit dicken Linien bestehen. 
Schreiben Sie zu diesem Zeitpunkt in jede Zelle eine Zahl von 1 bis N. Alle folgenden drei Bedingungen müssen jedoch erfüllt sein.
Es gibt eine Karte (Problem), in die Zahlen zur Hälfte geschrieben sind, wie in [Eingabebeispiel 1] und [Eingabebeispiel 2] unten. Schreiben Sie die natürlichen Zahlen 1,2,3, ..., N in die Leerzeichen dieser Karten und erstellen Sie ein Programm, das die Karten (Antworten) ausgibt, die die obigen Bedingungen (A) bis (C) erfüllen.
Das Verfahren zum Erstellen einer Antwort für eine Reihe von Deutschen kann grob in die folgenden zwei Phasen unterteilt werden.
Der Grund für die Untersuchung nur der Quadrate (y, x) in 1 oben ist, dass keine Wiederholung stattfindet. (Nach meiner Erfahrung werden Zahlen nur in ein Quadrat eingegeben)
Erstellen Sie zunächst ein Programm, um zu überprüfen, ob die Zahlen 1 bis N einzeln in der vertikalen x-Spalte verwendet werden.
Zählen Sie in den Quadraten (x, 0), (x, 1), ..., (x, N-1) die Anzahl von 1 bis N im Array. Zu diesem Zeitpunkt wird True zurückgegeben, wenn jede Zahl einzeln verwendet wird, 1 ist 1 und 2 ist 1 ... N ist 1, und False wird zurückgegeben, wenn sie nicht verwendet wird.
```python
#Finden Sie heraus, ob die Antwort in der Spalte steht
def checkQuestionRow(self,Row):
#Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind
num = [0 for m in range((self.N + 1))]
#Vertikal 0. Spalte-Vertikal(N-1)Scannen Sie bis zur Spalte
for x in range(0,self.N):
#Finden Sie heraus, wie viele 1 bis N enthalten sind
for m in range(1,self.N+1):
#(x,Row)Wenn der Wert des Quadrats m ist
if m == self.question[x][Row]:
#Die Zahl ist die Zahl von m+1
num[m] = num[m] + 1
#Säule(x)Gibt False zurück, wenn mehr als eine Zahl in verwendet wird
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
```
Hier sollte das gleiche Urteil wie im Fall der Vertikalen (Spalte) getroffen werden. ```python def checkQuestionCol(self,Col): #Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind num = [0 for m in range((self.N + 1))] #Horizontal 0. Linie-Horizontal(N-1)Scannen Sie zur Linie 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 #Gibt False zurück, wenn mehr als eine Zahl in der Zeile verwendet wird for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Blöcke werden als vertikale Colblocks, horizontale Rowblocks usw. beurteilt. Zum Beispiel kommen im Fall von 4 · 4 (n = 2, N = 4) die dicken Linien am 0. und 2 .. Die dicke Linie ist sowohl vertikal als auch horizontal 1 <= k <= n und kommt an die (k * n-1) -te Stelle. , K * nth ist der Startpunkt, k * (n + 1) ist der Endpunkt.
Ersetzen Sie dieses k durch colBlock und rowBlock und prüfen Sie, ob die Zahlen 1 bis N vom Startpunkt bis zum Endpunkt der vertikalen und horizontalen Blöcke einzeln enthalten sind. ```python # 2*2，3*Überprüfen Sie, ob für jeden 3er-Block eine Zahl von 1 bis N angezeigt wird def checkQuestionBlock(self,rowBlock,colBlock): #Startpunkt blockieren(colBlock* n ,rowBlock* n)Definieren startCol = colBlock * self.n startRow = rowBlock * self.n #Endpunkt blockieren(colBlock* {n+1} ,rowBlock* {n+1})Definieren endCol = (colBlock + 1) * (self.n) endRow = (rowBlock + 1) * (self.n) #Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind num = [0 for m in range((self.N + 1))] #Block für Block scannen 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 #Gibt False zurück, wenn mehr als eine Zahl im Block verwendet wird for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Schließlich werden alle Bedingungen (A) bis (C) zusammengefasst. Wenn einer der Punkte (A) bis (C) nicht erfüllt ist, wird False zurückgegeben. ```python #Aktuell(x,y)Finden Sie heraus, ob die Lösung korrekt ist def checkQuestion(self,x,y):
#Überprüfen Sie zunächst, ob alle Zeilen Zahlen von 1 bis N enthalten
if self.checkQuestionRow(x) == False:
return False
#Überprüfen Sie anschließend, ob alle Spalten Zahlen von 1 bis N enthalten.
if self.checkQuestionCol(y) == False:
return False
#Überprüfen Sie abschließend, ob jeder Block eine Zahl von 1 bis N enthält
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
<h2> 2: Platzieren Sie eine Zahl in das Quadrat (Tiefensuche) </ h2>
<p> Befolgen Sie die nachstehenden Anweisungen, um Zahlen auf die Quadrate einiger Deutscher zu setzen. </ p>
<ol> <li> Schreiben Sie die Beendigungsbedingung von rekursiv. Hören Sie auf zu rekursieren, hauptsächlich wenn die Spalte N erreicht. </ li> <li> Wenn bereits eine Zahl im Quadrat (y, x) platziert ist, das Quadrat (y, x + 1). Wenn es sich bereits am Ende der Seite befindet, kehrt es zum Quadrat (0, y + 1) zurück. </ li> <li> Wenn das Quadrat (y, x) noch keine Zahl hat, versuchen Sie zunächst, eine Zahl von 1 bis N in das Quadrat (y, x) einzufügen. Als Ergebnis wird True zurückgegeben, wenn die Bedingungen (A) bis (C) erfüllt sind. Ziehen Sie sich außerdem auf die gleiche Weise wie in 2 auf das Quadrat (y, x + 1) oder (0, y + 1) zurück. </ li> <li> 3. Wenn alle Zahlen von 1 bis N nicht die Bedingungen im Quadrat (y, x) erfüllen, bevor Sie den Wert des Quadrats (y, x) in {0} setzen. Rückkehr. </ li> </ ol>
<p> Gehen Sie auf diese Weise nacheinander und wenn die Bedingungen nicht erfüllt sind, gehen Sie einen Schritt zurück und überdenken Sie die Suchmethode als <b> Tiefensuche </ b>. Erzählen. </ p>
```python
#Suchen Sie nach einer Reihe deutscher Lösungen und nicht nach einer Suche mit Tiefenpriorität
def solve(self,question,x=0,y=0):
#Beenden Sie die Rekursive, wenn Sie die nächste Spalte nach der letzten Spalte erreichen
if x == 0 and y == self.N:
return True
#Wenn bereits eine Zahl im Quadrat steht
if self.question[y][x] != 0:
#Wenn Sie die letzte Zeile erreicht haben, sehen Sie sich den Anfang der nächsten Spalte an
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Untersuchen Sie die nächste Zeile, wenn es nicht die letzte Zeile ist
else:
if self.solve(self.question,x+1,y):
return True
#Wenn keine Zahl auf dem Quadrat steht
else:
for m in range(1,self.N+1):
#Massieren Sie zuerst die Zahl i(x,y)Vorübergehend einsetzen
self.question[y][x] = m
#Wenn das Urteil gefällt wird, die Masse(x,y)Bestimmen Sie den Wert von mit m
if self.checkQuestion(x,y) == True:
self.question[y][x] = m
#Zum Debuggen
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(m) + ")")
#Wenn Sie die letzte Zeile erreicht haben, sehen Sie sich den Anfang der nächsten Spalte an
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Untersuchen Sie die nächste Zeile, wenn es nicht die letzte Zeile ist
else:
if self.solve(self.question,x+1,y):
return True
#Wenn das Urteil nicht gefällt wird, stellen Sie die Quadrate wieder her
self.question[y][x] = 0
return False
* Beim Erstellen des Programms für diesen Teil wird @ wsldenlis " Lösen von Mathematik mit Python-Qiita Ich ahmte nach.
Sudoku.py
import os
import sys
class Sudoku():
#Daten initialisieren
def __init__(self):
#Kleine Rahmengröße
self.n = 2
#Definieren Sie den Umriss und das Ende der Nummer
self.N = self.n * self.n
#Initialisieren Sie alle Problem-Arrays mit 0
self.question = [[0 for i in range((self.N))] for j in range((self.N))]
#Finden Sie heraus, ob die Antwort für zügellos richtig ist
def checkQuestionRow(self,Row):
#Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind
num = [0 for m in range((self.N + 1))]
#Horizontal 0. Linie-Horizontal(N-1)Scannen Sie zur Linie
for x in range(0,self.N):
#Finden Sie heraus, wie viele 1 bis N enthalten sind
for m in range(1,self.N+1):
#(x,Row)Wenn der Wert des Quadrats m ist
if m == self.question[x][Row]:
#Die Zahl ist die Zahl von m+1
num[m] = num[m] + 1
#Gibt False zurück, wenn in der Spalte Row mehr als eine Zahl verwendet wird
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Vertikal:Überprüfen Sie, ob die Zahlen 1 bis N einzeln in Spalte Col erscheinen
#Grundlegendes Verhalten wie checkQuestionRow
def checkQuestionCol(self,Col):
#Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind
num = [0 for m in range((self.N + 1))]
#Vertikal 0. Spalte horizontal(N-1)Scannen Sie bis zur Spalte
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
#Gibt False zurück, wenn in der Spalte mehr als eine Zahl verwendet wird
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
# 2*2，3*Überprüfen Sie, ob für jeden 3er-Block eine Zahl von 1 bis N angezeigt wird
def checkQuestionBlock(self,rowBlock,colBlock):
#Startpunkt blockieren(colBlock* n ,rowBlock* n)Definieren
startCol = colBlock * self.n
startRow = rowBlock * self.n
#Endpunkt blockieren(colBlock* {n+1} ,rowBlock* {n+1})Definieren
endCol = (colBlock + 1) * (self.n)
endRow = (rowBlock + 1) * (self.n)
#Ein Array, in dem gespeichert wird, wie viele Zahlen von 1 bis N enthalten sind
num = [0 for m in range((self.N + 1))]
#Block für Block scannen
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
#Gibt False zurück, wenn mehr als eine Zahl im Block verwendet wird
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Aktuell(x,y)Finden Sie heraus, ob die Lösung korrekt ist
def checkQuestion(self,x,y):
#Überprüfen Sie zunächst, ob alle Zeilen Zeilen bis N enthalten
if self.checkQuestionRow(x) == False:
return False
#Überprüfen Sie als nächstes, ob alle Spalten Col Zahlen von 1 bis N enthalten.
if self.checkQuestionCol(y) == False:
return False
#Überprüfen Sie abschließend, ob jeder Block eine Zahl von 1 bis N enthält
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
#Suchen Sie nach einer Reihe deutscher Lösungen und nicht nach einer Suche mit Tiefenpriorität
def solve(self,question,x=0,y=0):
#Beenden Sie rekursiv, wenn Sie die nächste Spalte nach der letzten Spalte erreichen
if x == 0 and y == self.N:
return True
#Wenn bereits eine Zahl im Quadrat steht
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
#Wenn keine Zahl auf dem Quadrat steht
else:
for m in range(1,self.N+1):
self.question[y][x] = m
#Zum Debuggen
# 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
#Zum Debuggen
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
return False
#Hauptfunktion
if __name__ == '__main__':
#Problemdaten
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)