Sudoku Solver - Verständnisfrage

  • C

Es gibt 33 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Ich betrachte noch meinen Code.
    Müsste bei Return 0 nicht noch sowas wie x-1 stehen?

    nein - die Return-Werte sind nicht als Zahlen gemeint, sondern als booleans: 0 bedeutet: fail, 1: success.

    vmtl. ist das C und kennt daher kein Boolean - Datentyp.

    Aber wie gesagt: Die Rekursion-Logik ist krude, und die Ergebnis-Ausgabe ist auch an schrulliger Stelle untergebracht.
    Sowas macht Code auch schwer verständlich.

    Was auch nervig ist, sind sinnlose Leerzeilen und sinnlose Kommentare - guck:

    C#-Quellcode

    1. int solveField(int x, int y) {
    2. if (x == G) {
    3. y++;
    4. x = 0;
    5. if (y == G) return 1; //-> Solved
    6. }
    7. if (feld[y][x] > 0) return solveField(x + 1, y); //Wenn besetzt Nächstes Feld rekursiv
    8. int z;
    9. for (z = 1; z < 10; z++) {
    10. if (checkSudoku(z, x, y) == 0) {
    11. feld[y][x] = z;
    12. if (solveField(x, y) == 1) {
    13. //Fertig -> Print
    14. printField();
    15. }
    16. }
    17. }
    18. //keine Lösung gefunden für x,y -> feld resetten + return fail
    19. feld[y][x] = 0;
    20. return 0;
    21. }
    unveränderte Logik, aber kompakt und ohne Gelaber

    Unlogisch ist, dass das PrintField nicht da steht, wo "solved" kommentiert ist.
    Und #12 ist wohl ein versehen, und soll heißen: if (solveField(x+1, y) == 1) {
    Und da der Algo alle Lösungen finden soll ist Datentyp int unangemessen als Rückgabewert - es muss eiglich garnix zurückgegeben werden.

    Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „ErfinderDesRades“ ()

    In #12 das ist ein versehen, stimmt, dennoch funktioniert es aber ohne das +1?

    Habe meinen Code auch mal aufgeräumt. Verstehe ihn jetzt bis auf die Tatsache, dass sich die Funktion bei einem Widerspruch erneut aufruft und "rückwärts" läuft.
    Mal angenommen die Schleife hat alle 10 Zahlen probiert und bei keiner wird checkSudoku(z,x,y) == 0, dann ist ja die solve Funktion durch, das aktuelle Feld wird einfach 0 gesetzt
    und die Funktion wäre gestoppt?

    C-Quellcode

    1. //Sukoku Lösen
    2. int solveField(int x, int y)
    3. {
    4. if(x == G)
    5. {
    6. y++;
    7. x = 0;
    8. }
    9. if(y == G)
    10. {
    11. //Solved
    12. system("cls");
    13. printField();
    14. }
    15. if(feld[y][x] > 0)
    16. {
    17. return solveField(x+1, y);
    18. }
    19. int z;
    20. for(z = 1; z < 10; z++)
    21. {
    22. if(checkSudoku(z,x,y) == 0)
    23. {
    24. feld[y][x] = z;
    25. solveField(x+1, y);
    26. }
    27. }
    28. feld[y][x] = 0;
    29. }

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „MB-Tech“ ()

    Und nach dem Return ist aber die Funktion beednet und ruft sich nicht selbst wieder auf?
    Also je mehr ich über diese Funktion nachdenke, desto weniger verstehe ich...

    MB-Tech schrieb:

    diese Funktion
    Beschreib mal ohne Code zu verwenden, was diese Funktion machen soll.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    MB-Tech schrieb:

    Und nach dem Return ist aber die Funktion beednet und ruft sich nicht selbst wieder auf?
    nein, da ruft sie sich nicht mehr auf.
    Und das ist gut so, denn sonst hättest du eine Endlos-Rekursion.
    Dieses Beenden ohne sich nochmal aufzurufen ist genau der Rücksprung.
    Also wenn sie sich selber aufruft, verschachtelt sich der Vorgang um eine Ebene tiefer, und wenn sie returnt kommt sie eine Ebene näher zur Oberfläche.

    so ist das mitte Rekursion.

    Dann Beschreib ich mal:

    Die Funktion soll alle einzelnen Feldern (Koordinaten der 9x9 Matrix) durchgehen und pro Feld die Zahlen 1-9 testen. Sobald eine Zahl stimmt und keine Unstimmigkeiten mit den Regeln des Sudoku´s auftreten wird in das nächste (freie) Feld gesprungen. Sobald ein Widerspruch herauskommt (z.B. eine Reihe stimmt komplett und im letzten Feld gibt es einen Widerspruch, weil z.B. im selben 3x3 Päckhen die Zahl schon vorhanden ist) wird stufenweise alles rückgängig gemacht und wieder von vorne angefangen, bis es dann klappt usw...

    Rekursion heißt, dass sich eine Funktion selbst aufruft. Das macht sie aber nur, wenn sie eine Zahl gefunden hat, die passt. Sobald aber ein Widerspruch entsteht und daher KEINE Zahl passt wird das Feld einfach auf 0 gesetzt und die Funktion ist beendet. Ich sehe nirgens, dass sie in DIESEM Fall nochmal aufgerufen wird. Ich hoffe, dass mir endlich meinen Denkfehler so erklären kann, dass ich keinen Denkfehler mehr habe :)

    du unterscheidest nicht zw. einem aufruf und verschachtelten Aufrufen.


    Also Solve wird mit 0/0 aufgerufen, testet die Zelle 0/0 - findet keinen Widerspruch, ruft sich selbst mit 0/1 auf, testet erfolgreich, ruft sich selbst mit 0/3 auf - findet Widerspruch 8|
    Also wir befinden uns in Sub Solve, die innerhalb von Sub Solve die innerhalb von Sub Solve aufgerugen ist.
    Teste das mit einem Haltepunkt - sieh dir den Aufrufe-Stack an!
    Nun - Widerspruch - also Return - wo kommt er raus beim Returnen?
    Na da, wo er aufgerufen wurde - und wo ist das? Na in Sub Solve - die hat sich ja selbst aufgerufen.

    Also wenner tief in einer Verschachtelung ist und returnt, dann verlässt er nicht die Solve-Methode als ganzes, sondern nur die aktuelle Schachtel-Tiefe.
    Also mehr kann ich nicht erklären - kapiers oder lasses.

    Kennst du das Aufrufe-Fenstet? Haltepunkt etc?
    Schon mal gedoppelklickst auf eine tiefer im Stack liegende Methode?

    Also geht ein bischen in Richtung VisualStudio richtig nutzen (Google ist nicht deine Mami) , nur das AufrufeFenster musste halt noch bisserl suchen.

    ErfinderDesRades schrieb:

    Also wenner tief in einer Verschachtelung ist und returnt, dann verlässt er nicht die Solve-Methode als ganzes, sondern nur die aktuelle Schachtel-Tiefe.
    Also mehr kann ich nicht erklären - kapiers oder lasses.


    Aha. Das war der entscheidene Tipp! Danke. Ich dachte immer wenn die Funktion unten zu Ende ist, ist sie komplett zu Ende. Wobei in meinem Code jetzt unten garkein Return steht und es fuktioniert trotzdem. Schreibt der Compiler das automatisch rein?

    Jain. Wenn Funktion zu Ende, dann zu Ende. Da aber eine Funktion irgendeinen Wert haben muss, wird er wohl bei dem } default(TResult) oder sowas nehmen.
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    MB-Tech schrieb:

    Schreibt der Compiler das automatisch rein?
    Zunächst bringt der Compiler eine Warnung, die hast Du ignoriert:
    warning C4715: "solveField": Nicht alle Steuerelementpfade geben einen Wert zurück.
    Der Rückgabeweret ist dann ein zufälliger Speicherinhalt.
    Du solltest Dein Programm mal Zeile für Zeile debuggen :!:
    Bilder

    • Sudoku.jpg

      27,6 kB, 306×557, 54 mal angesehen
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    In DevC++ ist alles i.O. und der Compiler mault nicht. Daher sind mir auch so einige Sachen nicht aufgefallen.

    MB-Tech schrieb:

    der Compiler mault nicht.
    Wenn Du kannst, lass den Code mal von einem anderen Compiler kompilieren.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook
Telefonspende