Lässt eine Do_While-Schleife C# abstürzen?
Ich bin aktuell am programmieren mit C#. Um genau zu sein arbeite ich aktuell mit der Do-While Schleife. Mein Ziel ist es ein Programm zu entwickeln welches Sudoku´s erstellt. Ist recht spartanisch aber so möchte ich es machen. Nun passiert es aber das bei manchen Testläufen das Programm sich aufhängt, aber bei manchen es perfekt durchläuft. Habe meinen Code durchforscht und keine Fehöer gefunden, daher die Frage: Kann es sein das wenn die Schleife so viele Bedingungen erfüllen muss damit sie aufhört, dass es passieren kann das so viele Durchläufe der Schleife notwendig werden können dass das Programm es als eine Endlosschleife erkennt, auch wenn es keine ist, weil sie ja theoretisch aufgelöst werden wird?
4 Antworten
Hallo.
Meines Wissens nach kann eine "Do While" Schleife C# nicht zum Absturz bringen.
Was allerdings passieren kann ist, dass du dort eine Endlosschleife gebaut hast oder das in der Schleife etwas stattfindet was das Programm zum Absturz bringt. z.B. eine Division durch 0 oder eine IndexOutOfRangeException.
Das erste ist leicht zu beheben, falls es das wäre.
Sofern die Abbruchbedingung irgendwann erfüllt wird, wird die Schleife terminiert. Ein Programm kann auch keine Endlosschleife erkennen, bzw. genauer, nicht bestimmen, ob die Schleife irgendwann terminieren wird.
Ich hatte keine Zeit mir das en Detail anzuschauen, aber alleine, daß die Zahl der Nebenbedingungen stetig wächst ist: Ach Du heilige Makkeronisch.... .
Entweder direkt eine Permutation erzeugen, oder eine zufälliges Element auswählen, aus der Menge entfernen und über den Rest (erneut) randomisieren, oder die Logik umkehren, linear über die Elemente und die Position auswürfeln, wobei belegte Positionen nicht mehr Teil der Ergebnismenge sind ...
Ach, ich laß es lieber, da kommt man vom Hundertstel ins Millionstel.
Also ohne Code-Einsicht kann Dir das niemand sagen.
Wenn die While-Bedingung nie gebrochen wird, läuft die Schleife einfach endlos weiter.
Die While Bedingung kann gebrochen werden, ich weiß nicht ob du Sudoku kennst, aber hab halt so 24 Bedingungen die erfüllt werden müssen, aber sie sind alle gleichzeitig erfüllbar. Das habe ich alles bereits gecheckt.
Ja ich kenne Sudoku sogar bestens! Allerdings erscheinen mir 24 Bedingungen auch ziemlich viel. 3 sollten reichen.
Anyway, irgendwas klappt da nicht und das musst Du mal im Einzelschritt-Debug untersuchen.
Wie gesagt, ohne Code, kein Ansatz.
Ach Du Sche***!!!
Das ist doch kein Code! Das ist eine Katastrophe!!!
Hast Du nichts von Verschachtelung gehört?
Als erstes machst Du mal aus Deinen zahl_N_N-Variablen ein 2-dimensionales Datenfeld und die Zeit-Anzeige lässt sich durch einen popeligen Timer und einen DateTime-Datentyp anzeigen. Da werden aus Deinen 85 Variablen nur 2 !!!
Und der Rest lässt sich in drei verschachtelten Bedingungen zusammen fassen:
bool duplicate = false;
int[, ] zahl = new int[9, 9];
int x, y, c;
for (x=0; x<=8; x++) {
for (y=0; y<=8; y++) {
do {
duplicate = false;
zahl[x,y] = zufall.Next(1, 10);
for (c=0;c<=x; c++) {
duplicate = (zahl[x;y] == zahl[c;y]);
if (duplicate) { break; }
}
} while duplicate
}
}
Bis auf die anderen beiden Duplikat-Suchen (Spalte und Block) ist der Code eigentlich vollständig.
Allerdings musst Du den selbst debuggen, denn ich bin kein C#-Programmierer und hab das aus dem Kopf gemacht.
PS:
4 Schleifen und für die beiden anderen Duplikat-Suchen musst Du jeweils nur den 'c'-Block modifizieren.
24 scheint mir etwas wenig. 9 Zeilen, 9 Spalten, 9 3x3-Blöcke und 2 Diagonalen, das sollten 29 Bedingungen sein.
Je Zelle natürlich 3.
(Und jetzt bin ich auf den Code gespannt, ob der einen Brute-Force-Ansatz verfolgt oder Branch-and-Bound.)
Zufallspermutationen macht man anders, als so lange Zufallszahlen zu ermitteln, bis die gerade ermittelte Zahl ungleich aller vorigen ist. Nun gut, bei 9 Zahlen geht das noch, aber bei 81 wird es dann doch etwas viel.
Keine Diagonalen! Bei Sudoku kannst Du in der Diagonalen auch alles dieselbe Ziffer haben.
Was ich allerdings in meinem Code vergessen habe – fällt mir erst jetzt ein – ist das Fallenlassen von Sudokus, die sich auf diesem Weg selbst verbaut haben.
In den meisten Fällen bei dieser Methode hier versperrt man sich die Optionen im späteren Verlauf, so dass es in einer Zelle zwangsläufig zu einem Konflikt kommen muss.
Offen gestanden habe ich mir darüber noch nie den Kopf zerbrochen. Vielleicht ist ein Ansatz aus der Mitte heraus effektiver, oder ein blockweiser Aufbau, bei dem aus der Mitte heraus kreisförmig immer in jedem Block eine weitere Ziffer zufällig und blockweise platziert wird. So könnte man schon früher die falschen Optionen ausklammern. Dann werden es tatsächlich aber mehr Schleifen. Die würde ich dann auch nicht mehr in derselben Funktion verwenden.
Na, ja, interessante Herausforderung.
Einfach helfen reicht auch, beleidigen muss man nicht direkt. Wenn du in irgendeinem Gebiet neu bist, und dir alles selbst beibringen musst, dann komm ich auch mal daher und mache mich lustig über dich.
Ich schätze, mit der radialen Methode sollten maximal 9 Zufallszahlen reichen und der Rest muss wie beim Spiel selbst durch Ausschluss-Verfahren ermittelt werden.
Aber das wäre für eine Schulaufgabe dann doch etwas zu hoch.
Sag mal, wo hab ich mich jetzt über Dich lustig gemacht??? o_O?
Einfach mal bedanken hätte auch gereicht!
Zunächst mal, wenn man ein Sudoku so generiert wie ich es dort gemacht habe, gibt es keine layouts die nicht möglich sind, als Beweis : führe es mal per Hand durch, nimm dir ein 9 x 9 Feld und einen Zufallsgenerator der dir eine Zahl von 1 bis 9 ausspuckt. Fange oben links an, eine Zahl generieren lassen, eintragen. Nächstes Feld. Hier jedoch neue Zahl generieren bis diese zweite Zahl nicht der ersten entspricht. Bei dritten so weiter, usw. usf.. Das kannst du 100.000.000 mal probieren, es wird jedes mal komplett aufgehen.
Des weiteren, danke für die Bemühungen, aber die einfache Antwort "Ja, wenn das Programm zu viele Versuche benötigt um die passende Zahl zu finden, dann hängt sich das Programm auf." Ich habe es gerade getestet und eingefügt das die Schleife ab gewisser Anzahl an Versuchen unterbrochen wird. Erst nach 100, dann nach 100.000, dann 100.000.000 usw. usf.. Ab 100.000.000 benötigt das Programm 1 Sekunde zum laden, bei noch höherer Anzahl immer wieder ein bisschen länger. Bei dem Abbruch zeigt mir das Programm dann in den jeweiligen Feldern wo die Schleife abgebrochen wurde, eine Zahl an die logischer Weise in der Zeile/Spalte/Kasten bereits vorhanden ist. An all diesen Stellen wäre eine Zahl aber möglich einzutragen, als Beispiel stand dort die "5" aber möglich gewesen wäre die "3" oder "8". Es war also eine richtige Lösung möglich, also schließt sich ein "nicht lösbares Sudoku-Layout" aus. Ich habe die Anzahl der Versuche vor dem Abbruch immer weiter erhöt, und Voila, irgendwann hat sich das Programm aufgehangen.
Und nein, an meinem Computer liegt es nicht.
Das kannst du 100.000.000 mal probieren, es wird jedes mal komplett aufgehen.
Falsch!
Denn Du berücksichtigst so nur die Reihen und mit jeder weiteren Reihe steigt das Risiko, dass Du Dich selbst Schach-Matt setzt.
Spiel mal eine Zeit lang Killer-Sudoku, dann weißt Du, was ich meine.
Die Kombinations-Möglichkeiten sind zwar enorm, aber nicht unendlich und durch die Sudoku-Regeln extrem eingeschränkt. Von ~ 1,1 * 10^50 möglichen Variationen bleiben nur ~ 5,5 -10^10 reale Sudoku Kombinationen übrig.
Falls das gerade nicht so imposant aussieht, hier mal ausführlich illustriert:
55 Milliarden →
55.000.000.000
von
110 Oktillionen →
110.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000
(musste ich auch erst nachschlagen)
Das ist jenseits von gut und böse und das ist Dein Berechnungsweg!
Ich hoffe, Dir ist nun klar, wo sich Dein Programm aufgehängt hat.
PS: Das macht eine statistische Wahrscheinlichkeit von 1: 20 Sextilliarden, dass Dein Programm ein funktionierendes Sudoku findet.
Entweder deine Schleife läuft endlos oder sie läuft einfach nur sehr lang. Ich denke aber, dass ersterer Fall zutrifft, weil in einem bestimmten Fall eine Bedingung in deinem Code nicht erfüllt werden kann.
Am schnellsten kannst du den Fehler wohl ausfindig machen, indem du dir Zwischenstände in der Konsole ausgeben lässt. Wenn du den konkreten Fall ausfindig machen konntest, der dein Programm haken lässt, kannst du diesen rekonstruieren und entweder manuell (auf Blatt Papier) oder mit einem Debugger durchlaufen.
Um das Programm nicht etliche Male neustarten zu müssen (um den Fehlerfall zu reproduzieren), kann es sinnvoll sein, im Test die Startmethode mehr als nur einmal auszuführen.
for (int i = 0; i < 10; ++i) {
generateSudoku();
}
In diesem Fall ergibt übrigens -- so weit ich durch den Gordischen Knoten auf https://pastebin.com/WJP15w6U durchsteige -- die Logik des Problems zusammen mit der Programmlogik, dass es zu einer Endlosschleife kommt, wenn nicht schon der erste Versuch zum Erfolg führt.