C# Rekursives Programm entwickelt Eigenleben - mögliche Ursache?

[Smagjus]

Hallo zusammen!

Ich habe ein extrem merkwürdiges Problem. Mein Programm soll eigentlich via Backtracking welches ich rekursiv realisiert habe, zusammen mit der Klasse Random zufällige Sudokus erstellen. Jetzt kommt das aber: Es funktioniert nur, wenn ich eine Debugausgabe einbaue und das kann ich mir mit gesundem Menschenverstand nicht erklären.

Der Code ist nicht schön, deswegen versuche ich das Prinzip erst einmal zu erklären:

1. Ich habe ein eindimensionales Array, welches mein Feld darstellt. Index 0 ist oben links, Index 8 ist oben rechts und Index 80 ist unten rechts auf meinem quadratischen Sudoku Feld.
2. Die Methode FillValues bekommt den Startindex 0 und einen Zufallswert zwischen 1 und 9. Dieser wird ins Array eingetragen.
3. Danach prüfe ich mit der Methode IsLegal, ob der Teil des Array, der bereits befüllt ist, den Sudoku Regeln entspricht. Ist das nicht der Fall, werden für den aktuellen Index nacheinander alle anderen möglichen Werte zwischen 1 und 9 probiert.
4. Funktioniert das nicht, gehe eine Ebene weiter nach oben(=Index - 1) und probiere wieder alle Werte.
5. Bin ich erfolgreich, gehe ich eine Ebene weiter nach unten(=Index + 1) und mache mit verändertem Index bei Schritt 2 weiter.
6. Abbruchbedingung ist ein Index von 81.

Das Problem ist, dass dies nur funktioniert, wenn ich Debug Ausgabe über die Konsole einbaue. Ohne diese Ausgaben, scheint sich das Feld bis zur Ebene 70 recht fehlerfrei aufzubauen, fängt dann aber an sukzessive bis zurück auf Ebene 16 zu kollabieren. Baue ich die Debugausgabe ein, dauert das Erstellen wesentlich länger, dafür ist es aber erfolgreich und benötigt weniger Iterationen als der fehlerhafte Aufbau. Genau das kann doch eigentlich gar nicht sein oder? Das einzige Element in meinem Programm, das meines Wissens mit der Zeit in Relation steht, ist Random, womit ich die zufälligen Werte erstelle. Aber theoretisch gesehen, müsste das Programm auch mit einem schlechten Randomseed terminieren oder etwa nicht?

Spoiler: FillValues Methode

private Boolean FillValues(int index, int value)        {
            if (index >= 81)
                return true;


            Solution[index] = (byte)value; TestValue++;


            if (IsLegal(Solution, index) && FillValues(index + 1, new Random().Next(1, 10)))
                return true;
            else
            {


                Boolean isLegalOption = false;
                int i = 0;
                int newValue =((value % 9) + 1);
                do
                {
                    Solution[index] = newValue; TestValue++;
                    isLegalOption = IsLegal(Solution, index);
                    i++;
                    newValue = ((value + i) % 9) + 1;
                }
                while (newValue != value && !isLegalOption);


                if (isLegalOption)
                    return FillValues(index + 1, new Random().Next(1, 10));
                else
                    return false;
            }
        }

Spoiler: IsLegal Methode

public Boolean IsLegal(int[] solution, int upperIndexLimit)        {
            Boolean[] values;
            int temp = -1;


            for (int i = 0; i < 9; i++)
            {


                values = new Boolean[10];
                for (int j = 0; j < 9; j++) //hoizontal
                {
                    temp = solution[i * 9 + j];
                    if (temp != 0 && (i * 9 + j) <= upperIndexLimit)
                    {
                        if (values[temp])
                        {
                            Print(solution, upperIndexLimit);    //DEBUGAUSGABE, fällt sie weg, funktioniert das Programm nicht mehr
                            return false;
                        }
                        else
                            values[temp] = true;
                    }
                }


                //---------------------------------------------------------------------------------
                values = new Boolean[10];
                for (int k = 0; k < 9; k++) //vertical
                {
                    temp = solution[k * 9 + i];
                    if (temp != 0 && (k * 9 + i) <= upperIndexLimit)
                    {
                        if (values[temp])
                        {
                            Print(solution,upperIndexLimit);    //DEBUGAUSGABE, fällt sie weg, funktioniert das Programm nicht mehr
                            return false;
                        }
                        else
                            values[temp] = true;
                    }
                }


                //---------------------------------------------------------------------------------
                values = new Boolean[10];
                for (int l = 0; l < 9; l++) //blockwise
                {
                    temp = solution[i * 3 + (i / 3) * 18 + (l / 3) * 9 + (l % 3)];
                    if (temp != 0 && (i * 3 + (i / 3) * 18 + (l / 3) * 9 + (l % 3)) <= upperIndexLimit)
                    {
                        if (values[temp])
                        {
                            Print(solution, upperIndexLimit);    //DEBUGAUSGABE, fällt sie weg, funktioniert das Programm nicht mehr
                            return false;
                        }
                        else
                            values[temp] = true;
                    }
                }
            }
            return true;
        }

Spoiler: Print Methode

​private void Print(int[] solution, int upperIndex)        {
            for (int i = 0; i < 81; i++)
            {
                if (i % 9 == 0)
                    Console.WriteLine();
                Console.Write(solution[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine("UpperIndex = {0}",upperIndex);
        }

 

[DjNDB]

Benutzt du Threads in dem Programm?

 

[Smagjus]

Nein, das wäre in der Tat eine mögliche Lösung, aber das Füllen meines Array muss eigentlich absolut linear ablaufen. Es sei denn VS2012 kommt von selbst auf die Idee Rekursionen auf mehrere Threads zu verteilen, aber das ist mir nicht bekannt.

Edit: Weitere Tests zeigen. Lasse ich die Ausgabe weg, füge stattdessen ein

System.Threading.Thread.Sleep(10);

ein, läuft mein Programm auch fehlerfrei. Es hat also wirklich mit dem Timing zu tun.

 

[cx01]

Du rufst immer new Random() auf, wodurch jedesmal ein neuer Zufallsgenerator erstellt wird. Seed ist vermutlich die Systemzeit und die ändert sich nicht schnell genug, sodass alle deine Randomwerte überall gleich sein dürften.

 

[yetisports]

Folgendes Problem mMn: Du rufst in FillValues an 2 Stellen die Funktion selbst wieder auf, was ja in Ordnung ist, da es eine Rekursion ist. Aber du fügst ja unterschiedliche Zahlen ein durch dein Random.

Heißt: Zeilen 9-14 sowie 33 sind überflüssig. Da würde das auch insgesamt anders machen:

private Boolean FillValues(int index, int value)        {
            if (index >= 81)
                return true;

            if (value==10)
               return false;
 
 
            Solution[index] = (byte)value; TestValue++;
 
 
            if (IsLegal(Solution, index))
                return FillValues(index + 1, 0);
            else return FillValues(index, ++value);
            
        }

Oder was ich zumindest machen würde (da meine kurzgedachte Implementierung wohl das Backtracking nicht beinhaltet, was ja benötigt wird):
Du musst "FillValues(index + 1, new Random().Next(1, 10))" in einer boolschen Variable zwischenspeichern und dann an den Stellen des Aufrufs einfügen. Sonst hast du ja zwei unterschiedliche Ergebnisse im gleichen Aufrufschritt.

EDIT: Ok, bin ja auch doof. Da würde ja immer das gleiche Sudoku herauskommen. ^^

 

[Smagjus]

cx01, vielen Dank für den Hinweis. Ich hatte sowas im Sinn, habe aber nicht daran geglaubt. Die neue Implementierung der FillValues, die deinen Tipp beherzigt, funktioniert! Trotzdem merkwürdig, weil die Methode eigentlich auch ohne Zufallswerte klarkommen müsste. Ich gehe dem mal nach.

@yetisports
Ich überprüfe gerade deine Aussage, dauert noch ein wenig.

Edit:
Ja deine Aussage stimmt. Allerdings müsste ich die do-while dann in eine while Schleife umwandeln.

Was mir aber dabei aufgefallen ist:
Die Zeilen 29-30 enthalten den Fehler. Sollte hier tatsächlich ein false zurückgegeben werden, müsste ich theoretisch durch weitere Möglichkeiten für meine aktuelle Ebene iterieren. Das tue ich aber nicht, sondern werfe stattdessen komplett das Handtuch, indem ich das false direkt zurückgebe. Deswegen terminiert das Programm unter bestimmten Bedingungen nicht richtig.

Edit2:Falls von Interesse, hier der fehlerfreie Code. Dieser funktioniert jetzt unabhängig von der Qualität des Randomseeds. Zeile 22 ist neu.

private Boolean FillValues(int index, int value, Random ran)        {
            if (index >= 81)
                return true;


            Solution[index] = (byte)value; TestValue++;


            if (IsLegal(Solution, index) && FillValues(index + 1, ran.Next(1, 10), ran))
                return true;
            else
            {


                Boolean isLegalOption = false;
                int i = 0;
                int newValue = ((value % 9) + 1);
                do
                {
                    Solution[index] = newValue; TestValue++;
                    isLegalOption = IsLegal(Solution, index);
 isLegalOption = isLegalOption && FillValues(index + 1, ran.Next(1, 10), ran);
                    i++;
                    newValue = ((value + i) % 9) + 1;
                }
                while (newValue != value && !isLegalOption);


                return isLegalOption;
            }

        }

Beweis:
Das Sudoku mit 1 anstelle von Random.NextInt().