Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Sudoku in Python (Backtracking)
Autor
Kein bestimmter Bereich Sudoku in Python (Backtracking)
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Themenstart: 2021-03-14

Hallo zusammen, ich brauche mal ein bisschen Hilfe beim Implementieren einer Funktion, die Sudokus löst. Ich würde das gerne per Backtracking machen und habe dabei ein paar konkrete Probleme. Zuerst überprüfe ich jedes freie Feld, ob es eine eindeutige Ziffer gibt, die in das Feld eingetragen werden kann. Das mache ich solange, bis sich das ganze Spielfeld nicht mehr verändert. Bei einfachen Sudokus hat man dann oft schon die Lösung. Wenn hier die Lösung noch nicht erreicht ist, gilt für jedes freie Feld, dass es mindestens zwei "vorab" zulässige Möglichkeiten gibt, Ziffern einzutragen. Mit "vorab" zulässig meine ich, dass aktuell noch kein Widerspruch erkennbar ist. Beim Backtracking fängt jetzt sozusagen das Raten an: Man nimmt sich für das erste freie Feld die erste widerspruchsfreie Ziffer und guckt, wie weit man damit kommt. Mit Glück ist kommt man damit zur Lösung. Oft ist es aber so, dass man wieder an einen Punkt kommt, wo eine Entscheidung getroffen werden muss, welche Ziffer für ein weiteres freies Feld gewählt werden soll. Wenn man nun nicht zufällig immer richtig rät, läuft man irgendwann in eine Sackgasse und muss zurück und eine andere mögliche Ziffer raten. Genau hier fängt mein Problem an. Eigentlich muss ich ja bis zur letzten Verzweigung zurück und da alle Möglichkeiten durchprobieren um zu gucken, wie weit ich komme. Rein praktisch ist mir aber nicht klar, wie ich diese Verzweigungen ohne großen Aufwand erkennen kann. Ich müsste diese ja immer in einer globalen Variable speichern und die beim rekursiven Aufruf mitgeben. Die fertigen Lösungen, die ich im Netz gefunden habe, machen das aber nicht. Habe ich hier einen Denkfehler oder sehe ich den Wald vor lauter Bäumen nicht? Vg Daniel


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.1, eingetragen 2021-03-14

\quoteon(2021-03-14 11:18 - mrdjv2 im Themenstart) Rein praktisch ist mir aber nicht klar, wie ich diese Verzweigungen ohne großen Aufwand erkennen kann. \quoteoff Ich verstehe nicht, was du da erkennen möchtest. "Vorab"-Entscheidungen, die sich als falsch herausgestellt haben, zurückzunehmen, ist doch gerade das, was das Backtracking leisten soll. --zippy


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.2, vom Themenstarter, eingetragen 2021-03-14

\quoteon(2021-03-14 11:37 - zippy in


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.3, eingetragen 2021-03-14

Schau dir nochmal an, wie Backtracking funktioniert. Z.B hier.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.4, eingetragen 2021-03-14

Du musst sicherstellen, dass du jeden Schritt beim Backtracking wieder rückgängig machst, sodass der vorige Zustand wieder erreicht wird. Bei einfachen Problemen steht der Zustand im Übergabeparameter der rekursiven Funktion. Wird dieser selbst nicht modifiziert, sondern bei weiteren Aufrufen immer nur eine modifizierte Kopie übergeben, so gibt es hier nichts zu tun. Bei schwierigeren Problemen und iterativer Implementierung kann man für jeden Schritt ein "make"/"undo"-Paar implementieren. [Die Antwort wurde nach Beitrag No.2 begonnen.]


   Profil
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen
  Beitrag No.5, eingetragen 2021-03-14

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\) mrdjv2 Du mußt ja nicht nur bis zur letzten Verzweigung zurück, sondern auch alle gesetzten Steine zurücknehmen. Und die eleganteste Methode, diese „Buchführung“ zu bewerkstelligen, ist Rekursion! Die kennst du bis jetzt vielleicht nur von der Berechnung der Fakultät: $f(n+1)=(n+1)!=n! \cdot (n+1)=f(n) \cdot (n+1)$, mit $f(0)=1$. Tip: Probier erst mal, das 8-Damen-Problem (8 Damen so auf einem Schachbrett zu plazieren, daß keine Dame eine andere bedroht) zu lösen. Natürlich rekursiv. Aber ohne dir die in dem Link aufgezeigten Lösungsmöglichkeiten anzusehen (was du vermutlich jetzt erst recht tun wirst – versuche, dich zu beherrschen und erst mal selber nachzudenken).\(\endgroup\)


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.6, vom Themenstarter, eingetragen 2021-03-14

Hallo zusammen, ja, Rekursion war mir schon ein Begriff und kam mir bisher in der praktischen Programmierung tatsächlich eher nur bei der Fakultät unter. Ich habe jetzt etwas gebastelt (nicht ganz ohne Hilfe), was mir zwar das richtige Ergebnis in meinem Testfall liefert, aber womit ich noch nicht zufrieden bin: \sourceon Python def solve(grid): grid2 = fill_unique(grid) solveSudokuHelper(0,0,grid2) return def solveSudokuHelper(i,j,grid): if j>8 and i<9: solveSudokuHelper(i+1,0,grid) return if i>8: print(grid) return quit() if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: solveSudokuHelper(i,j+1,grid) return grid \sourceoff Ich rufe die Funktion solve auf und übergebe das unvollständige Sudoku. Dann ergänze ich die Felder, die eindeutig befüllbar sind und nenne das ganze dann grid2. Das schicke ich dann in die Funktion solveSudokuHelper und fange an der Stelle (0,0) an. Damit hangele ich mich dann von Feld zu Feld durch und komme irgendwann in den Zweig "if i>8". An der Stelle wird mir die Lösung dann auf den Bildschirm gegeben. Was ich jetzt noch nicht verstehe, ist, warum trotz quit() und return python hier nicht aufhört. Das Programm rechnet noch ein paar Sekunden weiter. Ich verstehe nicht, was er hier macht. Und als Schönheitskorrektur würde mich noch interessieren, wie ich das gelöste Sudoku jetzt als Rückgabewert der Funktion solve bekomme. Indem ich "return grid" verwendet habe, hat er trotzdem nichts zurückgegeben. Muss ich hier noch etwas beachten? VG Daniel


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.7, eingetragen 2021-03-14

\quoteon(2021-03-14 20:26 - mrdjv2 in Beitrag No. 6) Indem ich "return grid" verwendet habe, hat er trotzdem nichts zurückgegeben. \quoteoff Deine Funktion hat drei Ausgänge, und du gibst das Gitter nur bei einem davon zurück (also nicht bei allen, auf die es ankommt).


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.8, vom Themenstarter, eingetragen 2021-03-14

Ich verstehe es trotzdem noch nicht. Ich hatte ursprünglich im "if i>8:"-Zweig ein "return grid" eingefügt. Hier ist für mich nämlich letztendlich der finale Ausgang der Berechnung. Das musste jetzt aber durch die "solve"-Funktion durchgeschleift werden und dann ausgegeben werden. Das ist mir noch ein Rätsel, wie ich das praktisch umsetze. Ich verstehe auch noch nicht, warum das Programm nach dem richtigen Ausgeben per Print und dann dem Abbrechen der Hilfsfunktion noch weiterarbeitet.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.9, eingetragen 2021-03-14

\quoteon(2021-03-14 22:32 - mrdjv2 in Beitrag No. 8) Ich verstehe auch noch nicht, warum das Programm nach dem richtigen Ausgeben per Print und dann dem Abbrechen der Hilfsfunktion noch weiterarbeitet. \quoteoff Die Funktion solveSudokuHelper hat sich doch zu dem Zeitpunkt, an dem das return im "if i>8"-Zweig aktiv wird, mehrmals selbst aufgerufen. Dieses return kehrt daher nicht zu solve zurück, sondern nur zum nächst höheren rekursiven Aufruf von solveSudokuHelper.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.10, eingetragen 2021-03-15

Ein rekursiver Solver sollte immer ein Ergebnis zurückgeben. Dieses kann man dann außerhalb zur weiteren Logik nutzen. \sourceon Python def solve(state): if isSolved(state): return state if isDeadEnd(state): return None for newState in calculateNewStates(state): solution = solve(newState) if solution: return solution return None \sourceoff


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.11, vom Themenstarter, eingetragen 2021-03-15

\quoteon(2021-03-15 08:00 - DerEinfaeltige in Beitrag No. 10) Ein rekursiver Solver sollte immer ein Ergebnis zurückgeben. Dieses kann man dann außerhalb zur weiteren Logik nutzen. \quoteoff Eigentlich hatte ich das vor. Daher habe ich in den "i>8"-Zweig eine quit()-Anweisung geschrieben. Eigentlich wollte ich das, was dann in der Variable "grid" steht, zurück an "solve" geben und die "solveSudokuHelper"-Funktion beenden. Mit einem einfachen Return funktioniert das aber nicht, wie zippy sagt. Um das Zurücklaufen durch die ganze Rekursion zu vermeiden, wollte ich eben die Funktion einfach abbrechen.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.12, eingetragen 2021-03-15

\quoteon(2021-03-15 15:51 - mrdjv2 in Beitrag No. 11) Um das Zurücklaufen durch die ganze Rekursion zu vermeiden, wollte ich eben die Funktion einfach abbrechen. \quoteoff Das "quit()" wird aber nie ausgeführt, da du die Funktion ja schon vorher mit "return" verlassen hast.


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.13, vom Themenstarter, eingetragen 2021-03-15

Aber kann ich denn nicht an einer bestimmten Stelle, die ich definiere, sagen: Gehe hier aus der Funktion raus, gehe wieder in Solve und nimm den Wert, der jetzt in "grid" steht mit?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.14, eingetragen 2021-03-15

\quoteon(2021-03-15 17:21 - mrdjv2 in Beitrag No. 13) Aber kann ich denn nicht an einer bestimmten Stelle, die ich definiere, sagen: Gehe hier aus der Funktion raus, gehe wieder in Solve und nimm den Wert, der jetzt in "grid" steht mit? \quoteoff Das kann man erreichen, aber der aus Python-Sicht saubere Weg ist der, den DerEinfaeltige in Beitrag Nr. 10 beschrieben hat.


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.15, vom Themenstarter, eingetragen 2021-03-15

Also vielleicht bin ich ja nicht in der Lage, Rekursion zu verstehen, aber mir will nicht in den Kopf, warum folgender Code nicht funktioniert: \sourceon Python def solve(grid): grid2 = fill_unique(grid) return solveSudokuHelper(0,0,grid2) def solveSudokuHelper(i,j,grid): if isSolved(grid): print(grid) return grid else: if j>8 and i<9: solveSudokuHelper(i+1,0,grid) return if i>8: return grid if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: solveSudokuHelper(i,j+1,grid) return \sourceoff Bei jedem Aufruf der Hilfsfunktion teste ich, ob das Sudoku gelöst ist. Irgendwann ist das der Fall (ich sehe es durch das Ausführen von print(). Dann gebe ich einfach diesen Wert zurück. Für jede rekursiv aufgerufene Version von der Hilfsfunktion sollte die Bedingung dann doch auch erfüllt sein und letztendlich sollte der Rückgabewert doch das gelöste Rätsel sein. Was ist denn jetzt konkret noch falsch? Die Rückgabe ist nämlich nichts. Kein None oder [], sondern einfach nichts.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.16, eingetragen 2021-03-16

\quoteon(2021-03-15 21:35 - mrdjv2 in Beitrag No. 15) Also vielleicht bin ich ja nicht in der Lage, Rekursion zu verstehen \quoteoff Ja, da liegt das Problem. \quoteon(2021-03-15 21:35 - mrdjv2 in Beitrag No. 15) Bei jedem Aufruf der Hilfsfunktion teste ich, ob das Sudoku gelöst ist. Irgendwann ist das der Fall (ich sehe es durch das Ausführen von print(). Dann gebe ich einfach diesen Wert zurück. \quoteoff Soweit ist alles in Ordnung. Aber wie geht es mit diesem Wert dann weiter? Die Ausführung der Funktion solveSudokuHelper, die mit "print(grid)" und "return grid" endet, wurde ja nicht unmittelbar aus solve heraus aufgerufen, sondern aus einer übergeordneten Ausführung von solveSudokuHelper. Nehmen wir mal an, dass das aus diesem Fragment heraus erfolgt ist: \sourceon python if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: solveSudokuHelper(i,j+1,grid) return \sourceoff Für beide Aufrufe von solveSudokuHelper in diesem Fragment wird zunächst deren Rückgabewert ignoriert und dann ein "return" ohne Rückgabewert durchgeführt. Auf diese Weise geht der zuvor von "return grid" gelieferte Wert wieder verloren. Betrachten wir mal ein ganz einfaches Beispiel einer rekursiven Funktion. Die folgende Funktion f gibt die nächste durch 5 teilbare Zahl aus, die $\ge n$ ist: \sourceon python def f(n): if n % 5 == 0: return n else: return f(n+1) \sourceoff Deiner Version von solveSudokuHelper entspricht die folgende nicht funktionierende Version von f: \sourceon python def f(n): if n % 5 == 0: return n else: f(n+1) return \sourceoff


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1819
  Beitrag No.17, eingetragen 2021-03-16

Hallo, ich weiß nicht, ob es hilfreich ist, aber mein Backtracking Algorithmus für Sudoku in Fortran sieht so aus (siehe auch mein Matheplanet Artikel): https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1882 \showon \sourceonFORTRAN program sudoku c ************************************** c Sudoku-Solver Version 1.0 Backtracking c von Delastelle (c) Dezember 2006 c ************************************** c Compileroption für dieses Programm: c ftn95 -optimise -link sudoku sudoku.for c Ausgabe der Ergebnisse in Datei mittels: c sudoku.exe > ausgabe.txt c Zeiten 1.Loesung / 2.Loesung oder fertig c 1: 0.046875 / 0.0625 c 2: 0.078125 / 0.140625 c 3: 0.21875 / 1.51563 c 4: 0.046875 / 0.9375 c 5: 0.046875 / 0.046875 c 6: 1.51563 / 2.54688 c 7: 0.78125 / 0.78125 implicit none integer i,j,beispiel,m(9,9),s(9),az real t0,t1 parameter(beispiel = 6) call cpu_time(t0) az = 0 if (beispiel.eq.1) then c Testsudoku von http://www.mathworks.com/matlabcentral/files/8083/sodoku.m c zeit = 0.1 Sekunden auf 3200+ s(1) = 0 0 1 9 0 0 0 0 8 s(2) = 6 0 0 0 8 5 0 3 0 s(3) = 0 0 7 0 6 0 1 0 0 s(4) = 0 3 4 0 9 0 0 0 0 s(5) = 0 0 0 5 0 4 0 0 0 s(6) = 0 0 0 0 1 0 4 2 0 s(7) = 0 0 5 0 7 0 9 0 0 s(8) = 0 1 0 8 4 0 0 0 7 s(9) = 7 0 0 0 0 9 2 0 0 endif if (beispiel.eq.2) then c Testsudoku von http://www.sudokusolver.co.uk/grids_nologic.html c das schwerste; Difficulty score: 19499 (19x Raten für das angegebene Prg) c zeit = 0.1 Sekunden auf 3200+ s(1) = 0 7 0 0 0 0 0 0 9 s(2) = 0 0 0 7 0 0 5 0 0 s(3) = 0 3 2 0 5 0 0 8 0 s(4) = 0 0 7 6 3 0 0 5 4 s(5) = 0 0 0 0 8 0 0 0 0 s(6) = 3 6 0 0 9 5 2 0 0 s(7) = 0 2 0 0 1 0 7 3 0 s(8) = 0 0 4 3 0 0 0 0 0 s(9) = 1 0 0 0 0 0 0 9 0 endif if (beispiel.eq.3) then c Testsudoku von http://www.frayn.net/sudoku/ c das schwerste Rating nighmare 334 Points c zeit = 0.2 Sekunden auf 3200+ s(1) = 0 2 0 0 0 0 0 0 0 s(2) = 0 0 0 6 0 0 0 0 3 s(3) = 0 7 4 0 8 0 0 0 0 s(4) = 0 0 0 0 0 3 0 0 2 s(5) = 0 8 0 0 4 0 0 1 0 s(6) = 6 0 0 5 0 0 0 0 0 s(7) = 0 0 0 0 1 0 7 8 0 s(8) = 5 0 0 0 0 9 0 0 0 s(9) = 0 0 0 0 0 0 0 4 0 endif if (beispiel.eq.4) then c Testsuduku aus Tagesspiegel 9.12 "schwer" c zeit = 0.1 Sekunden auf 3200+ s(1) = 0 0 0 0 0 0 0 3 0 s(2) = 0 0 0 3 1 4 6 0 0 s(3) = 0 5 0 0 9 0 0 2 0 s(4) = 0 8 0 0 0 7 0 0 0 s(5) = 1 0 6 0 3 5 0 0 0 s(6) = 5 7 2 0 0 0 0 0 0 s(7) = 0 0 1 2 0 9 0 7 0 s(8) = 0 0 0 0 0 6 0 4 0 s(9) = 0 0 7 8 4 0 0 0 2 endif if (beispiel.eq.5) then c Testsudoku von mir c zeit = 0.1 Sekunden auf 3200+ s(1) = 1 0 0 0 0 0 0 0 0 s(2) = 0 2 0 0 0 0 0 0 0 s(3) = 0 0 3 0 0 0 0 0 0 s(4) = 0 0 0 4 0 0 0 0 0 s(5) = 0 0 0 0 5 0 0 0 0 s(6) = 0 0 0 0 0 6 0 0 0 s(7) = 0 0 0 0 0 0 7 0 0 s(8) = 0 0 0 0 0 0 0 8 0 s(9) = 0 0 0 0 0 0 0 0 9 endif c Sudoku mit nur 17 Zahlen - Nr 1 von 100 c http://moritz.faui2k3.org/files/100sudoku1.pdf c zeit = 1.4 Sekunden auf 3200+ if (beispiel.eq.6) then s(1) = 7 0 0 1 0 8 0 0 0 s(2) = 0 9 0 0 0 0 0 3 2 s(3) = 0 0 0 0 0 5 0 0 0 s(4) = 0 0 0 0 0 0 1 0 0 s(5) = 9 6 0 0 2 0 0 0 0 s(6) = 0 0 0 0 0 0 8 0 0 s(7) = 0 0 0 0 0 0 0 0 0 s(8) = 0 0 5 0 0 1 0 0 0 s(9) = 3 2 0 0 0 0 0 0 6 endif if (beispiel.eq.7) then c wie Nr.6 aber mit m(1,1) = 0 c zeit = 0.7 Sekunden s(1) = 0 0 0 1 0 8 0 0 0 s(2) = 0 9 0 0 0 0 0 3 2 s(3) = 0 0 0 0 0 5 0 0 0 s(4) = 0 0 0 0 0 0 1 0 0 s(5) = 9 6 0 0 2 0 0 0 0 s(6) = 0 0 0 0 0 0 8 0 0 s(7) = 0 0 0 0 0 0 0 0 0 s(8) = 0 0 5 0 0 1 0 0 0 s(9) = 3 2 0 0 0 0 0 0 6 endif c extrahiere Sudoku do 100 i = 1,9 do 200 j = 1,9 m(i,j) = s(i)/10**(9-j) s(i) = s(i) - m(i,j)*10**(9-j) 200 continue 100 continue call solver(m,az) call cpu_time(t1) print *,'Zeit ',t1 end c **************************************** c Backtracking-Algortihmus für Sudoku(9,9) c **************************************** recursive subroutine solver(m,az) implicit none integer i,j,ii,jj,m(9,9),leer,k,kollision, * x,y,gefunden,az real t1 c sind in M noch 0en => noch nicht fertig gelöst leer = 1 do 1000 i = 1,9 do 1100 j = 1,9 if (m(i,j).eq.0) then leer = 0 endif 1100 continue 1000 continue if (leer.eq.1) then call ausgabe(m) call cpu_time(t1) print *,'Zeit ',t1 print *,' ' az = az + 1 if (az.eq.2) then stop else return endif else c Rechne Brute Force c finde erste Stelle mit einer Null gefunden = 0 do 1300 i = 1,9 do 1400 j = 1,9 if (gefunden.eq.0.and.m(i,j).eq.0) then gefunden = 1 x = i y = j endif 1400 continue 1300 continue c probiere dort alles durch do 1500 k = 1,9 ii = ((x-1)/3)*3+1; jj = ((y-1)/3)*3+1; kollision = 0 c Spalten- & Zeilenbedingung verletzt? do 1550 i = 1,9 if (k.eq.m(x,i).or.k.eq.m(i,y)) then kollision = 1 endif 1550 continue c Zellenbedingung verletzt? if (kollision.eq.0) then do 1600 i = 0,2 do 1700 j = 0,2 if (k.eq.m(ii+i,jj+j)) then kollision = 1 endif 1700 continue 1600 continue endif if (kollision.eq.0) then c Hurra ein neuer Wert wird eingetragen! m(x,y) = k call solver(m,az) endif 1500 continue endif m(x,y) = 0 return end c ************************* c Ausgabe eines 9x9-Sudokus c ************************* subroutine ausgabe(m) implicit none integer i,m(9,9) do 2100 i = 1,9 print 13, m(i,1:9) 13 format(i4,i4,i4,i4,i4,i4,i4,i4,i4) 2100 continue print *,' ' return end \sourceoff \showoff Viele Grüße Ronald


   Profil
JoeM
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.10.2015
Mitteilungen: 827
Wohnort: Oberpfalz
  Beitrag No.18, eingetragen 2021-03-16

Hallo mrdjv2, ich habe vor ca. 15 Jahren ein Sudoku- Programm geschrieben, das mit Sicherheit jedes 9 * 9 - Sudoku löst ( auch getestet mit den schwierigsten Sudokus weltweit; z.B. mit Sudokus von Arto Inkala ). Meine Vorgehensweise war so : - im 1. Schritt habe ich ein leeres 9 * 9 - Feld nach den Sudoku- Regeln mit Zufallszahlen ausfüllt ( das geht in sec.- Bruchteilen ). - damit ist gewährleistet, dass man jedes beliebige gültige Sudoku lösen kann. - somit kann man auch Sudukus erzeugen, indem man überflüssige Zahlen entfernt. - Das Programm erzeugt durch Zufallszahlen z.B. 1000 gültige Sudokus i.m. in 2,30 min ( dabei sind bei jedem Sudoku überflüssige Zahlen entfernt ). Die Anzahl der Vorgabezahlen liegt i.d.R. zwischen 22 und 26. - weiterer Vorteil: Man kann jedes gegebene Sudoku von >leicht< auf >schwer< reduzieren, indem man überfüssige Zahlen entfernen kann. viele Grüße JoeM


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.19, vom Themenstarter, eingetragen 2021-03-16

\quoteon(2021-03-16 00:37 - zippy in Beitrag No. 16) \quoteon(2021-03-15 21:35 - mrdjv2 in Beitrag No. 15) Also vielleicht bin ich ja nicht in der Lage, Rekursion zu verstehen \quoteoff Ja, da liegt das Problem. \quoteon(2021-03-15 21:35 - mrdjv2 in Beitrag No. 15) Bei jedem Aufruf der Hilfsfunktion teste ich, ob das Sudoku gelöst ist. Irgendwann ist das der Fall (ich sehe es durch das Ausführen von print(). Dann gebe ich einfach diesen Wert zurück. \quoteoff Soweit ist alles in Ordnung. Aber wie geht es mit diesem Wert dann weiter? Die Ausführung der Funktion solveSudokuHelper, die mit "print(grid)" und "return grid" endet, wurde ja nicht unmittelbar aus solve heraus aufgerufen, sondern aus einer übergeordneten Ausführung von solveSudokuHelper. Nehmen wir mal an, dass das aus diesem Fragment heraus erfolgt ist: \sourceon python if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: solveSudokuHelper(i,j+1,grid) return \sourceoff Für beide Aufrufe von solveSudokuHelper in diesem Fragment wird zunächst deren Rückgabewert ignoriert und dann ein "return" ohne Rückgabewert durchgeführt. Auf diese Weise geht der zuvor von "return grid" gelieferte Wert wieder verloren. Betrachten wir mal ein ganz einfaches Beispiel einer rekursiven Funktion. Die folgende Funktion f gibt die nächste durch 5 teilbare Zahl aus, die $\ge n$ ist: \sourceon python def f(n): if n % 5 == 0: return n else: return f(n+1) \sourceoff Deiner Version von solveSudokuHelper entspricht die folgende nicht funktionierende Version von f: \sourceon python def f(n): if n % 5 == 0: return n else: f(n+1) return \sourceoff \quoteoff Ok, ich glaube, ich verstehe langsam...Betonung liegt auf "langsam". Ich habe jetzt Folgendes gemacht: \sourceon Python def solve(grid): grid2 = fill_unique(grid) return solveSudokuHelper(0,0,grid2) def solveSudokuHelper(i,j,grid): if isSolved(grid): print(grid) return grid else: if j>8 and i<9: return solveSudokuHelper(i+1,0,grid) if i in range(0,9) and j in range(0,9): if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: return solveSudokuHelper(i,j+1,grid) \sourceoff Hier habe ich kein return ohne Wert. Die Lösung wird auch gefunden (wie oben schon). Diese Lösung gebe ich über "return grid" zurück. Jetzt hätte ich erwartet, dass die übergeordnete Instanz diesen Rückgabewert einliest und durch die Abfrage ganz oben den dann an die nächsthöhere Instanz weitergibt usw. Damit hätte ich dann erwartet, dass das auch der Rückgabewert für solveSudokuHelper(0,0,grid2) aus dem Programm "solve" ist. Das stimmt aber offenbar immer noch nicht.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  Beitrag No.20, eingetragen 2021-03-16

\quoteon(2021-03-16 14:00 - mrdjv2 in Beitrag No. 19) Hier habe ich kein return ohne Wert. \quoteoff Doch, das hast du, und zwar am Ende deiner Funktion Wenn hier die Bedingung "grid[i][j] == 0" erfüllt ist, rufst du solveSudokuHelper auf, ignorierst den Rückgabewert, und das Ende der Funktion sorgt dann für ein implizites "return": \sourceon python if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) grid[i][j]=0 else: return solveSudokuHelper(i,j+1,grid) \sourceoff


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.21, vom Themenstarter, eingetragen 2021-03-16

Halleluja! Es hat geklappt. Vielen Dank für die Hilfe! \sourceon Python def solve(grid): grid2 = fill_unique(grid) return solveSudokuHelper(0,0,grid2) def solveSudokuHelper(i,j,grid): """This function solves the grid recursively by testing out all possible numbers for each cell""" if isSolved(grid): return grid #solveSudokuHelper(i+1,j+1,grid) else: if j>8 and i<9: return solveSudokuHelper(i+1,0,grid) if i in range(0,9) and j in range(0,9): if grid[i][j]==0: for x in range(1,10): if x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) if isSolved(grid): return grid grid[i][j]=0 else: return solveSudokuHelper(i,j+1,grid) \sourceoff Jetzt versuche ich noch, das alles in eine Funktion zu packen. Dann bin ich fertig...


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.22, vom Themenstarter, eingetragen 2021-03-31

Hallo zusammen, ich muss den thread hier nochmal aufwärmen. Im Prinzip funktioniert mein Programm jetzt und das auch meistens relativ schnell (zumindest schnell genug). In einzelnen Fällen ist es aber sehr langsam. Jetzt würde ich es gerne optimieren. Erstmal der Code: \sourceon Python def solve(grid): temp=[] #grid=fill_unique(grid, temp) Erklärung dazu unten return solveSudokuHelper(0,0,grid) def solveSudokuHelper(i,j,grid): temp=[] #print(grid) #grid = fill_unique(grid, temp) #print(grid) """This function solves the grid recursively by testing out all possible numbers for each cell""" if isSolved(grid): return grid #solveSudokuHelper(i+1,j+1,grid) else: if j>8 and i<9: return solveSudokuHelper(i+1,0,grid) if i in range(0,9) and j in range(0,9): if grid[i][j]==0: for x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) if isSolved(grid): return grid grid[i][j]=0 else: return solveSudokuHelper(i,j+1,grid) \sourceoff Der Aufruf erfolgt dann mit "solve(grid)", wobei grid vorgegeben wird. Konkret brauche ich bei dem grid [[0, 0, 0, 6, 0, 0, 4, 0, 0], [7, 0, 0, 0, 0, 3, 6, 0, 0], [0, 0, 0, 0, 9, 1, 0, 8, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 5, 0, 1, 8, 0, 0, 0, 3], [0, 0, 0, 3, 0, 6, 0, 4, 5], [0, 4, 0, 2, 0, 0, 0, 6, 0], [9, 0, 3, 0, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 1, 0, 0]] sehr lange. Meine Idee das zu verbessern hat nicht funktioniert (obwohl es in der Theorie klappen müsste). Erklärung zur Funktion "fill_unique": Je nach Situation ist für offene Felder nur noch ein Wert zulässig. Der wird dann eingetragen. Dadurch ergeben sich ggf. bei anderen Feldern nur noch eindeutige Werte, die dann eingetragen werden. Das Programm läuft solange bis keine Änderung mehr passiert und gibt dann dieses neue Spielfeld aus. Sollte jetzt für ein Feld gar keine mögliche Ziffer mehr möglich sein, wird wieder das ursprünglich übergebene Feld zurückgegeben. Darum habe ich die Variable temp eingeführt: \sourceon Python def fill_unique(grid, temp): if temp==[]: temp=grid if temp!=[]: return temp temp1=grid for i in range(0,9): for j in range(0,9): if len(possible_values(i,j)) == 0 and grid[i][j]==0: return temp for i in range(0,9): for j in range(0,9): if grid[i][j]==0: if len(possible_values(i,j)) == 1: grid[i][j]=list(possible_values(i,j))[0] temp2=grid if temp1 != temp2: for i in range(0,9): for j in range(0,9): if grid[i][j]==0: fill_unique(grid, temp) return grid \sourceoff Grundsätzlich funktioniert das auch, aber es verbessert die Performance nicht. Hat jemand eine Idee, wie ich die weiter verbessern kann? Das o.g. Feld braucht bei mir rund 2 Minuten um gelöst zu werden und zum Beispiel bei https://www.surfpoeten.de/apps/sudoku/solver/ nichtmal eine Sekunde... Irgendwo verschwende ich zuviel Rechenleistung...aber wo? VG Daniel


   Profil
OlgaBarati
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.11.2018
Mitteilungen: 190
  Beitrag No.23, eingetragen 2021-03-31

Ich würde mit drei identischen Klassen arbeiten.


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.24, vom Themenstarter, eingetragen 2021-03-31

\quoteon(2021-03-31 23:53 - OlgaBarati in Beitrag No. 23) Ich würde mit drei identischen Klassen arbeiten. \quoteoff Das verstehe ich nicht mal im Ansatz...


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.25, eingetragen 2021-04-01

\quoteon(2021-03-31 23:10 - mrdjv2 in Beitrag No. 22) Grundsätzlich funktioniert das auch, aber es verbessert die Performance nicht. Hat jemand eine Idee, wie ich die weiter verbessern kann? Das o.g. Feld braucht bei mir rund 2 Minuten um gelöst zu werden und zum Beispiel bei https://www.surfpoeten.de/apps/sudoku/solver/ nichtmal eine Sekunde... Irgendwo verschwende ich zuviel Rechenleistung...aber wo? \quoteoff Also mein Solver löst das ebenfalls quasi "sofort". Ich verwende eine eigene Variante des "Dancing Links" Algorithmus und mein SudokuSolver selbst besteht im Grunde nur aus einem Konvertierer von Sudoku zu Exact Cover. Ohne zu wissen, wie effizient oder ineffizient das sudokuHelper-Modul ist, kann man schlecht beurteilen, wo der Falschenhals sitzt. Dort geschehen schließlich 90% der Arbeit. Du zeigst hier ja nur die recht uninteressanten 10% des Algorithmus.


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.26, vom Themenstarter, eingetragen 2021-04-01

Mein Programm ist wie folgt: \sourceon Python def numbers_from_row(row): """This function returns a set of valid numbers for a given row""" row_numbers=set(grid[row]) start={1,2,3,4,5,6,7,8,9} for i in range (1, 10): if i in row_numbers: start.remove(i) return start def numbers_from_column(column): """This function returns a set of valid numbers for a given column""" temp=[[grid[j][i] for j in range(len(grid))] for i in range(len(grid[0]))] column_numbers=set(temp[column]) start={1,2,3,4,5,6,7,8,9} for i in range (1, 10): if i in column_numbers: start.remove(i) return start def numbers_from_box(row, column): """This function returns a set of valid numbers for a given box""" if row in range(0,3): row_range=range(0,3) if row in range(3,6): row_range=range(3,6) if row in range(6,9): row_range=range(6,9) if column in range(0,3): column_range=range(0,3) if column in range(3,6): column_range=range(3,6) if column in range(6,9): column_range=range(6,9) number_set = [] for i in column_range: for j in row_range: number_set.append(grid[j][i]) start={1,2,3,4,5,6,7,8,9} for i in range (1, 10): if i in number_set: start.remove(i) return start def possible_values(row, column): """This function returns a set of valid numbers for a cell in the grid""" row_numbers=numbers_from_row(row) column_numbers=numbers_from_column(column) box_numbers=numbers_from_box(row, column) poss_val = row_numbers.intersection(column_numbers.intersection(box_numbers)) return poss_val def isSolved(grid): columns = "not OK" boxes = "not OK" rows = "not OK" box1=[] box2=[] box3=[] box4=[] box5=[] box6=[] box7=[] box8=[] box9=[] for i in range(0,9): if sorted(grid[i])==[1,2,3,4,5,6,7,8,9]: columns = "OK" temp=[[grid[j][i] for j in range(len(grid))] for i in range(len(grid[0]))] if sorted(temp[i])==[1,2,3,4,5,6,7,8,9]: rows = "OK" for i in range(0,3): for j in range(0,3): box1.append(grid[i][j]) for i in range(0,3): for j in range(3,6): box2.append(grid[i][j]) for i in range(0,3): for j in range(6,9): box3.append(grid[i][j]) for i in range(3,6): for j in range(0,3): box4.append(grid[i][j]) for i in range(3,6): for j in range(3,6): box5.append(grid[i][j]) for i in range(3,6): for j in range(6,9): box6.append(grid[i][j]) for i in range(6,9): for j in range(0,3): box7.append(grid[i][j]) for i in range(6,9): for j in range(3,6): box8.append(grid[i][j]) for i in range(6,9): for j in range(6,9): box9.append(grid[i][j]) if sorted(box1)==[1,2,3,4,5,6,7,8,9] and sorted(box1) == sorted(box2) and sorted(box2) == sorted(box3) and sorted(box3) == sorted(box4) and sorted(box4) == sorted(box5) and sorted(box5) == sorted(box6) and sorted(box6) == sorted(box7) and sorted(box7) == sorted(box8) and sorted(box8) == sorted(box9): boxes = "OK" if boxes == "OK" and columns == "OK" and rows == "OK": return True else: return False def fill_unique(grid, temp): if temp==[]: temp=grid if temp!=[]: return temp temp1=grid for i in range(0,9): for j in range(0,9): if len(possible_values(i,j)) == 0 and grid[i][j]==0: #return("Problem") #solve(temp3, 1) return temp for i in range(0,9): for j in range(0,9): if grid[i][j]==0: if len(possible_values(i,j)) == 1: grid[i][j]=list(possible_values(i,j))[0] temp2=grid if temp1 != temp2: for i in range(0,9): for j in range(0,9): if grid[i][j]==0: fill_unique(grid, temp) return grid def solve(grid): temp=[] grid=fill_unique(grid, temp) return solveSudokuHelper(0,0,grid) def solveSudokuHelper(i,j,grid): #print(grid) temp=[] grid = fill_unique(grid, temp) #print(grid) """This function solves the grid recursively by testing out all possible numbers for each cell""" if isSolved(grid): return grid #solveSudokuHelper(i+1,j+1,grid) else: if j>8 and i<9: return solveSudokuHelper(i+1,0,grid) if i in range(0,9) and j in range(0,9): if grid[i][j]==0: for x in possible_values(i, j): grid[i][j]=x solveSudokuHelper(i,j+1,grid) if isSolved(grid): return grid grid[i][j]=0 else: return solveSudokuHelper(i,j+1,grid) \sourceoff


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.27, vom Themenstarter, eingetragen 2021-04-04

*push*


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.28, eingetragen 2021-04-04

Die Methoden "numbers_from_..." und "isSolved" sind sehr ineffizient. Dort wird der Flaschenhals vermutlich sitzen. Das kann man durch andere Datenstrukturen besser lösen.


   Profil
mrdjv2
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 05.07.2003
Mitteilungen: 1010
Wohnort: Aachen
  Beitrag No.29, vom Themenstarter, eingetragen 2021-04-04

Was könnte man denn besser nehmen? Die Idee, wie es funktioniert (aktuell), ist klar, denke ich. Woran kann ich denn erkennen, ob etwas schneller geht oder nicht? Allein die Schleifen sind doch nicht das Problem, oder?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.30, eingetragen 2021-04-04

Ich werde mal schaun, dass ich meinen Algorithmus bei Gelegenheit in Python übertrage. Dann kann man direkt vergleichen.


   Profil
emmi82
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.05.2013
Mitteilungen: 443
  Beitrag No.31, eingetragen 2021-04-05

\quoteon(2021-04-04 15:01 - mrdjv2 in Beitrag No. 29) Was könnte man denn besser nehmen? Die Idee, wie es funktioniert (aktuell), ist klar, denke ich. Woran kann ich denn erkennen, ob etwas schneller geht oder nicht? Allein die Schleifen sind doch nicht das Problem, oder? \quoteoff Hi, Eine Struktur mit 2 ineinandergeschachtelten Forschleifen, \sourceon nameDerSprache for i in range(1,7): for j in range(1,4): #task 1 for i in range(1,7):### for j in range(4,8): #task 2 \sourceoff lässt sich kürzer schreiben, indem du die Zeile mit '###' streichst. Solch ein Muster, wo du die gleiche äußere Schleifenbedingung mehrfach verwendest, sehe ich da mehrmals. Das könnte schon etwas bringen, aber nicht unbedingt weltbewegend. Sollte isSolved mehrfach aufgerufen werden im gesamten Durchlauf des Programms (da bin ich selbst nicht auf die Schnelle durchgestiegen, sorry), dann ist für die Performance vorteilhaft, die grids in einer Klasse abzulegen und darauf schreibend zuzugreifen, wenn es pro Iteration von isSolved nur kleinere Änderungen am grid gibt. Gegenwärtig baust du die Boxen jeweils neu auf, um sie zu prüfen. Hier nur als Skizze, um zu zeigen, wie es im Prinzip geht: \sourceon Python-Skizze class grid: Attribut grid #(2dim. Array) Methode update(self, i,j,val): grid[i][j]=val Methode checkbox(self,vertpos,horizpos): return true/false Methode checkline(self,num): return true/false \sourceoff emmi


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1819
  Beitrag No.32, eingetragen 2021-04-06

Hallo, mein Algorithmus aus Beitrag Nr.17 braucht nur 1 Sekunde um ein Sudoku zu lösen. Noch schneller war eine mindeg-Heuristik beim Backtracking. Dabei wurde zuerst geschaut in welcher Zeile/Spalte man wenige verschiedene Ziffern eintragen konnte und diese Zeile/Spalte zuerst befüllt. Dies brachte noch mal eine Zeitersparnis von 50-66 Prozent. Viele Grüße Ronald


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3040
  Beitrag No.33, eingetragen 2021-04-06

Meine Java-Implementierung benötigt rund 60ms für obiges Sudoku. Ich habe versucht, den Algorithmus nach Python zu portieren, die Implementierung ist aktuell jedoch ungleich langsamer. (Faktor 100) Vermutlich weil ich nicht gewohnt bin, objektorientierten Pythoncode zu schreiben und ein paar Flaschenhälse übersehe.


   Profil
mrdjv2 hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]