Ich arbeite an meinem ersten kleinen Projekt, einen Sudokulöser der möglichst schnell arbeiten soll.
Ich wollte euch bitten, mir Ratschläge zu geben, wie ich mein Programmierstil verbessern kann.
(So beim schnellen drüberfliegen)
Es dürfen natürlich auch Ratschläge gemacht werden, wie der Algorithmus Optimiert werden kann,
oder mit welche Datenstrukturen sich besser für ein Problem eignen, aber ich denke, dass
es etwas zu viel zu unübersichtlicher Code ist, als das ich euch das zumuten könnte
Code: Alles auswählen
def sudokuloeser3(S):
def kandidatenListe_init(S, BZS):
"""
erstellt eine 9x9 kandidatenListe zu einem Sudoku S
mit allen möglichen Einträgen für jede Position.
"""
kandidatenListe = [];
for i in range(9):
kandidatenListe.append([]);
for j in range(9):
if S[i][j]:
# Wenn die i.Zeile und j.Spalte besetzt ist
# kann nichts mehr eingetragen werden.
kandidatenListe[i].append(set())
else:
# Ansonsten ist eine Zahl genau dann Kandidat,
# wenn sie noch nicht in dem Block, der Zeile
# und der Spalte eingetragen werden kann.
kandidatenListe[i].append(BZS[0][i//3*3+j//3] & BZS[1][i] & BZS[2][j])
return kandidatenListe
def BZS_Z_init(S):
"""
erstellt 2 Hilfs-Listen BZS und Z zu einem Sudoku S
BZS ist eine 3x9 Liste, wobei bei der 1. Dimension
BZS[0]=Blöcke
BZS[1]=Zeilen
BZS[2]=Spalten entspricht
und in der 2. Dimension durchnummeriert wird.
Bei den Blöcken ist die Reinfolge: [1 2 3]
[4 5 6]
[7 8 9]
Als Einträge hat BZS die noch fehlenden Zahlen
in dem Block/ der Zeile/ der Spalte
Z ist das genaue Gegenstück,
es ist ein Array der Länge 10, wobei Index 0
nichts speichert.
Beim Rest ist der Eintrag eine Menge die jeden
Tupel (Zeile/Spalte , nr) beinhaltet, in der die
jeweilige zum Index gehörende Zahl noch fehlt.
(Für das Speichern der Blöcke in Z hat sich kein
Sinnvolle Verwendung gefunden)
"""
BZS = [[set(range(1, 10)) for nr in range(9) ] for art in range(3)];
Z = ["DUMMY"];
for k in range(9):
Z.append(set(it.product(range(1, 3), range(9))))
for i in range(9):
for j in range(9):
if S[i][j]:
BZS[0][i//3*3+j//3].remove( S[i][j] )
BZS[1][i].remove( S[i][j] )
BZS[2][j].remove( S[i][j] )
Z[S[i][j]].remove( (1, i) )
Z[S[i][j]].remove( (2, j) )
return BZS, Z
def zuBearbeiten_init(BZS):
"""
erstellt zuBearbeiten
zuBearbeiten ist die Menge aller zahlen und
Blöcke/Zeilen/Spalten, bei denen es sein könnte,
dass man die Zahl in den/r Block/Zeile/Spalte
eintragen kann.
Am Anfang ist das jede Zahl in jede(r) Block/Zeile/Spalte
in der die Zahl noch fehlt.
Später müssen nur die betrachtet werden, für die sich
was seit der letzten Betrachtung verändert hat.
"""
return { (zahl, art, nr) for art in range(3) for nr in range(9) for zahl in BZS[art][nr]}
def Spaltenloeser(kandidatenListe, j, kandidat):
"""
prüft ob der Kandidat in der j. Spalte eingetragen
werden kann und gibt ggf die Position zurück
"""
eintragen_pos=False
for i in range(9):
if kandidat in kandidatenListe[i][j]:
# wenn die Zahl an dieser Stelle (i,j) in der
# Spalte eingetragen werden kann und an keiner
# anderen Stelle, so muss sie hier richtig sein
if not eintragen_pos:
eintragen_pos = (i, j)
else:
# leider kann sie an mind 2 Stellen Eingetragen werden,
# also abbrechen
return False;
return eintragen_pos
def Zeilenloeser(kandidatenListe, i, kandidat):
"""
prüft ob der Kandidat in der i. Zeile eingetragen
werden kann und gibt ggf die Position zurück
"""
eintragen_pos = False
for j in range(9):
if kandidat in kandidatenListe[i][j]:
# wenn die Zahl an dieser Stelle (i,j) in der
# Zeile eingetragen werden kann und an keiner
# anderen Stelle, so muss sie hier richtig sein
if not eintragen_pos:
eintragen_pos = (i, j)
else:
# leider kann sie an mind 2 Stellen Eingetragen werden,
# also abbrechen
return False;
return eintragen_pos
def Blockloeser(kandidatenListe, nr, kandidat):
"""
prüft ob der Kandidat in dem Block "nr" eingetragen
werden kann und gibt ggf die Position zurück
"""
a, b = nr//3*3, nr%3*3
eintragen_pos = False
for i in range(a, a+3):
for j in range(b, b+3):
if kandidat in kandidatenListe[i][j]:
# wenn die Zahl an dieser Stelle (i,j) in dem
# Block eingetragen werden kann und an keiner
# anderen Stelle, so muss sie hier richtig sein
if not eintragen_pos:
eintragen_pos = (i, j)
else:
# leider kann sie an mind 2 Stellen Eingetragen werden,
# also abbrechen
return False;
return eintragen_pos
def copy_2dim(liste):
"""
tiefes Kopieren einer 2-dimensionalen Liste,
viel schneller als copy.deepcopy
"""
return [[ eintrag.copy() for eintrag in zeile] for nr,zeile in enumerate(liste)]
def update(zuBearbeiten,BZS,Z,zeile,spalte,zahl):
"""
aktualisiert die Mengen zuBearbeiten, BZS und Z
nachdem die Zahl "zahl" an der Stelle "pos" eingetragen wurde
"""
# Bestimmt Block in der die Zahl eingetragen wurde
block=zeile//3*3+spalte//3
# entfehrnt die eingetragene Zahl von der Menge
# der Zahlen die in B/Z/S noch fehlen
BZS[0][block].remove(zahl)
BZS[1][zeile].remove(zahl)
BZS[2][spalte].remove(zahl)
# entfehrnt B/Z/S von der Menge der Blöcke/Zeilen/Spallten
# in der die eingetragene Zahl noch fehlt
Z[zahl].difference_update({(1,zeile),(2,spalte)})
# entfehrnt die eingetragene Zahl aus
# den zu bearbeitenden Möglichkeiten
zuBearbeiten.difference_update({(zahl,0,block),(zahl,1,zeile),(zahl,2,spalte)})
# fügt alle Zahlen die noch in B/Z/S eingetragen werden müssen
# in die Menge der zu überprüfenden Möglichkeiten ein.
for zahl_BZS in BZS[0][block]:
zuBearbeiten.add((zahl_BZS,0,block))
for zahl_BZS in BZS[1][zeile]:
zuBearbeiten.add((zahl_BZS,1,zeile))
for zahl_BZS in BZS[2][spalte]:
zuBearbeiten.add((zahl_BZS,2,spalte))
def entfehrne_Zahl_aus_kandidatenListe(kandidatenListe,zuBearbeiten,sofortloesen,Z,zeile,spalte,zahl):
"""
Diese Fkt geht Zeile/Spalte/Block von der "pos" der gerade eingetragenen
"zahl" durch, um diese aus der "kandidatenListe" zu streichen.
Ist dies an einer Stelle geschehen, wird geschaut, ob die Zahl
nun in der Zeile/Spalte/Block dieser Stelle eintragen werden kann,
indem sie der Menge zuBearbeiten hinzugefügt wird.
"""
# Blockposition (die Position des oberen linken Feldes des Blockes)
bl_z=zeile//3*3
bl_s=spalte//3*3
# Es müssen lediglich die Stellen überprüft werden,
# in denen die Zahl in der Zeilen/Spalten fehlt
# ansonsten war die Zahl schon vorher nicht in
# der kandidatenListe
for (art,nr) in Z[zahl]:
if art==1:
# Die Eigentliche Arbeit übernimmt entfernen,
# sie gibt dann zurück, ob die Zahl vorher an
# der Position eingetragen werden konnte
if(entfernen(kandidatenListe,sofortloesen,nr,spalte,zahl)):
# wenn dem so war, dann sollte die Zeile in der
# eingetragen wurde überprüft werden, ob die Zahl
# jetzt auch in diese eingetragen werden kann.
zuBearbeiten|={(zahl,art,nr)}
if nr//3!=zeile//3 :
# und wenn das auch noch in einem anderen Block war,
# als die eingetragene Zahl, dann sollte der Block auch
# nochmal überprüft werden.
zuBearbeiten|={(zahl,0,nr//3*3+spalte//3)}
else:
if(entfernen(kandidatenListe,sofortloesen,zeile,nr,zahl)):
# wenn dem so war, dann sollte die Spalte in der
# eingetragen wurde überprüft werden, ob die Zahl
# jetzt auch in diese eingetragen werden kann.
zuBearbeiten|={(zahl,art,nr)}
if nr//3!=spalte//3 :
# und wenn das auch noch in einem anderen Block war,
# als die eingetragene Zahl, dann sollte der Block auch
# nochmal überprüft werden.
zuBearbeiten|={(zahl,0,bl_z+nr//3)}
# In der Zeile und Spalte der eingetragenen Zahl wurde diese
# schon aus der kandidatenListe entfehrnt. Es gibt aber noch vier
# restliche Kästchen in dem Block in dem sie eingetragen wurde:
for x in range(bl_z,bl_z+3):
for y in range(bl_s,bl_s+3):
if(x!=zeile and y!=spalte):
if(entfernen(kandidatenListe,sofortloesen,x,y,zahl)):
zuBearbeiten|={(zahl,1,x),(zahl,2,y)}
def entfernen(kandidatenListe, sofortloesen, zeile, spalte, zahl):
"""
nimmt >zahl< aus der >kandidatenListe< vom Soduku S
an der Stelle pos=(i,j) falls zahl enthalten ist.
Wenn es danach nur noch eine Möglichkeit gibt,
wird diese in sofortlösen eingetragen
"""
if zahl in kandidatenListe[zeile][spalte]:
kandidatenListe[zeile][spalte].remove(zahl)
if(len(kandidatenListe[zeile][spalte])==1):
sofortloesen.add((zeile, spalte));
return False
return True;
def eintragen(S, kandidatenListe, zuBearbeiten, sofortloesen, BZS, Z, zeile, spalte, zahl):
S[zeile][spalte]=zahl;
kandidatenListe[zeile][spalte]=set();
update(zuBearbeiten, BZS, Z, zeile, spalte, zahl);
entfehrne_Zahl_aus_kandidatenListe(kandidatenListe, zuBearbeiten, sofortloesen, Z, zeile, spalte, zahl);
def raten(S, kandidatenListe, BZS, Z, zeile, spalte):
for zahl in kandidatenListe[zeile][spalte]:
# Kopieren, falls man falsch rät
S_c = [S[i].copy() for i in range(9)]
kandidatenListe_c = copy_2dim(kandidatenListe)
BZS_c = copy_2dim(BZS)
Z_c = ["DUMMY"];
Z_c.extend([Z[i].copy() for i in range(1,10)])
# zuBearbeiten und sofortloesen waren leer, ansonsten
# hätte man nicht raten müssen, desswegen mussten sie
# nicht kopiert werden
zuBearbeiten=set()
sofortloesen=set()
eintragen(S_copy,
kandidatenListe_copy,
zuBearbeiten,
sofortloesen,
BZS_copy,
Z_copy,
zeile, spalte,
zahl);
ergebnis=loesen(S_copy,
kandidatenListe_copy,
zuBearbeiten,
sofortloesen,
BZS_copy,
Z_copy);
if not ergebnis is None:
return ergebnis
return
def loesen(S,kandidatenListe,zuBearbeiten,sofortloesen,BZS,Z):
while(True):
if len(sofortloesen):
pos = sofortloesen.pop()
if len(kandidatenListe[pos[0]][pos[1]]):
# Wenn
#
zahl=kandidatenListe[pos[0]][pos[1]].pop()
else :
# wiederspruch zur Lösbarkeit.
# Da die Position in sofortloesen war,
# gab es nur eine Zahl die eingetragen werden konnte,
# inzwischen kann man keine Zahl mehr eintragen,
# und da "sofortloesen" priorität über die anderen
# Lösungsstrategien hat, kann die Zahl auch nicht
# schon eingetragen worden sein.
# Ergo: Hier ist ein freies Feld ohne
# anscheinend falsch geraten
# abbrechen!
#TODO überprüfen ob tatsächlich alle Möglichkeiten in denen man Falsch geraten hat, an dieser Stelle anspringen
return;
elif len(zuBearbeiten):
# Hier wird überprüft, ob man durch "scannen"
# eine Zahl eintragen kann
(zahl,art,ort)=zuBearbeiten.pop()
if(art==0):
pos = Blockloeser(kandidatenListe,ort,zahl)
elif(art==1):
pos = Zeilenloeser(kandidatenListe,ort,zahl)
elif(art==2):
pos = Spaltenloeser(kandidatenListe,ort,zahl)
else:
# Es kann nichts mehr mit Sicherheit gefunden werden
# es muss geraten werden;
break;
# Wenn eine Position "pos" gefunden wurde,
# wird die Zahl dort eingetragen
if pos:
eintragen(S, kandidatenListe, zuBearbeiten, sofortloesen, BZS, Z, pos[0], pos[1], zahl);
# Ok, der Algorithmus hat alles Eingetragen,
# was er finden konnte
# Entweder er ist fertig, oder wir raten.
# Um effizient zu raten, wird die Stelle mit den wenigsten
# Möglichkeiten gesucht.
for mindest in range(2,9):
for i in range(9):
for j in range(9):
if(len(kandidatenListe[i][j])==mindest):
return raten(S,kandidatenListe,BZS,Z,i,j);
return S
# Ab hier geht es los..
# Alle Hilfslisten initiieren und loslegen ٩(^ᴗ^)۶
BZS,Z=BZS_Z_init(S)
kandidatenListe=kandidatenListe_init(S,BZS)
zuBearbeiten=zuBearbeiten_init(BZS)
sofortloesen=set();
return loesen(S,kandidatenListe,zuBearbeiten,sofortloesen,BZS,Z);
(damit ihr ungefähr meine Vorkenntnisse einschätzen könnt)
Ich Programmiere übrigens über Jupyter, falls das ein Unterschied macht.
ps:
Die Regeln die ich mir durchlesen soll, bevor ich etwas poste, sind irgendwie nicht existenz:
This page does not exist yet. You can create a new empty page, or use one of the page templates.
ich denke aber, ich kann mir ungefähr denken, was drinsteht.
.
