Anmerkung zur Auswahl des Forums: Ich habe mich für das AnfängerForum entschieden, da die Fragen zu Rekursiv und Pointern die eines Anfängers sind ... dass Sudoku nicht zwingend für den blutigen Anfänger gedacht ist, ist mir durchaus klar, jedoch wollte ich jetzt nicht gleich zwei Topics aufmachen. Ich hoffe, dass ist so okay. Ansonsten entschuldige ich mich dafür und bitte dies einfach zu verschieben.
Wer keine Lust auf den Text hat: Die Fragen stehen gaaanz unten
Hallo,
Ich programmiere mir derzeit einen Algorithmus, der ein eingegebenes Sudoku lösen soll bzw. bei unlösbarkeit des Selbigen genau diesen Umstand zurückgeben soll. Hierzu habe ich (bisher) einen zwei-Klassen-Ansatz gewählt.
Die 1. Klasse heißt Sudoku. Der Konstruktor besteht aus zwei boolean, von denen einer angibt, ob das Sudoku bereits gelöst ist und der andere, ob es im aktuellen Status (!) noch lösbar ist.
Weiterhin findet sich im Konstruktor ein 9X9 Array aus Feldern (siehe zweite Klasse), das auch sogleich durch eine simple doppel for-schleife vorbelegt wird.
Die 2. Klasse heißt Feld. Jedes Feld repräsentiert eines der 81 Felder, die ein Standardsudoku hat. Dementsprechend "weiß" jedes Objekt Feld:
- seine Koordinaten (X,Y)
- seinen Sektor (damit meine ich diese 3x3-Quadrate, für die ebenfalls die Regel gilt, dass eine Zahl nur einmal vorkommen darf)
- ob es sich beim eingetragenen Wert um einen Fix-Wert handelt (bereits eingetragene Zahl) (boolean)
- welche Zahlen noch eingetragen werden können (Int-Array, das zu Beginn die Länge 9 hat).
Beide Klassen habe ich mit den nötigen Methoden versehen, um Änderungen an Variablen und Arrays vorzunehmen, Überprüfungen der Stati vorzunehmen. Intern gibt es in einigen Methoden Exceptions, die eine Verletzung bestimmter Bedingung verhindern soll (z.B. darf der fix-Boolean eines Felds nicht auf true gesetzt werden, wenn die Lösungsmenge noch größer als 1 ist) ... ja, hätte ich auch über eine einfache IF-Abfrage machen können, aber das macht's mir bei tests einfacher rauszufinden, wo der Fehler auftritt.
Der Algorithmus selbst soll wie folgt arbeiten:
1. User ein Sudoku eingeben lassen
2. Sudokugültigkeit prüfen (kommen schon im Ursprung zwei Zahlen in gleiche zeile/spalte/sektor vor?)
3. prüfen, ob Sudoki bereits gelöst (wenn ja, dann abbruch und Ausgabe)
4. Lösungsmenge der Felder korrigieren
5. prüfen, ob Sudoku in diesem Status noch lösbar (keines Feldes Lösungsmenge darf kleiner 1 werden)
6. prüfen, ob es Felder gibt, deren Lösungsmenge == 1 ist
7. Auswahl der Methode zur weiteren Lösung
8. Rücksprung zu Schritt 3.
Meine Probleme bestehen jetzt im Punkt 7
Ich unterscheide hierbei zwischen zwei wesentlichen Ansätzen:
1. Dem simplen Ansatz
2. Dem backtracking-Ansatz
Der 1. Fall ist nur möglich, wenn es in der Prüfung (Schritt 6) mindestens 1 Feld gibt, dessen Lösungsmenge == 1.
Hierbei werden einfach alle Felder, deren Lösungsmenge = 1 ist mit dem entsprechenden fix-Wert belegt.
Der simple Ansatz ist (meiner Meinung und Programmierung nach) zu bevorzugen und wird wann immer möglich ausgeführt. Begründung hier ist: Der Ansatz ist NICHT rekursiv
Der 2. Fall tritt genau dann ein, wenn der simple Ansatz unmöglich ist, da die Lösungsmengen durchgehend nicht eindeutig sind (Länge der Lösungsmenge größer 1). Hierbei soll der Algorithmus das Feld mit der kleinsten Lösungsmenge raussuchen. Werden mehrere mit gleicher Lösungsmenge gefunden, so wird das erste gefundene Feld ausgewählt.
Nacheinander sollen hier alle für dieses Feld möglichen Lösungen ausprobiert werden.
(Beispiel: noch mögliche Zahlen für Feld A sind 1,3,5 -> das Programm setzt zunächst 1 als FixWert und prüft, ob eine Lösung rauskommt, wenn nein, dann das gleiche mit drei, wenn wieder nein, dann mit 5 und wenn wieder nicht, ist das Sudoku nicht lösbar ... führt eine der Möglichkeiten zu einer Lösung, wird sofort die Ausgabe erzeugt und das Programm endet.)
In beiden Fällen wird das ursprüngliche Sudoku verändert und wieder durch den Lösungsalgorithmus gejagt (Ansatz hierfür ist interativ: eine while-schleife prüft, ob Sudoku gelöst oder unlösbar und beendet sich, wenn diese Bedingung erfüllt)
So viel zu meinem bisherigen Ansatz. Nun zu meinen Fragen, die hierzu aufgetreten sind:
1. Wie schaut es beim Kopieren von Objekt (hier das Objekt Sudoku) mit Pointern aus?
Sagt man bei einem Array einfach, es sei = anderes Array, kopiert man ja nicht das Array, sondern nur den Pointer.
Ist das bei Objekten bzw. Objekten die Arrays mitführen ebenfalls so?
(da müsste ich entsprechend eine tiefergehende kopiermethode schreiben, ähnlich der für Arrays)
2. Wie schaut es mit der Machbarkeit des Backtrackings aus speichertechnischer Sicht aus?
Als WorstCase habe ich den Fall identifiziert, in welchem der User eine vollständig leeres Sudoku eingibt.
Alleine für die komplette erste Zeile gäbe es 9! Möglichkeiten.
Da ich aber davon ausgehe, dass Java die Schritte NACHEINANDER ausführen wird (sprich jeweils nur eine Möglichkeit zur Zeit prüft und dann entweder die Ausgabe erreicht oder einen Schritt zurückgeht), habe ich berechnet, dass die Rekursion eine Tiefe von 60 erreichen wird.
(9X9 Felder = 81 ... davon ausgehend, dass das jeweils letzte Feld eines Sektor wieder nur eine Lösung besitzt, wird hier der simple Ansatz gewählt. Es gibt 9 Sektoren, also 81 - 9 = 72
Weiterhin gilt auch für das letzte Feld einer Zeile wieder Lösungsmenge = 1. Dies gilt für 6 Zeilen => 72 - 6 = 66.
Hinzu kommt, dass für die komplette letzte Zeile wieder die Lösungsmenge = 1 ist. Dies gilt wieder für 6 Felder (nicht für 9, da ich die letzten Felder eines Sektors bereits zu anfang ausgerechnet habe
66 -6 = 60)
Sprich: Der Algorithmus wird im WorstCase 60 Sudokus erzeugen und das letzte als Lösung ausgeben.
Wird das mit hoher Wahrscheinlichkeit zu einem Stack-Overflow führen oder sollte das per se keine Probleme geben
(ich bin mir kein Rekursionen nie sicher, weshalb ich die auch nicht mag ... interativ habe ich hier aber keinen Ansatz gefunden)
3. Keine Frage, aber ich würde mich über Verbesserungsvorschläge für den von mir entwickelten Algorithmus freuen.
Ich habe einen Ansatz, den ich ursprünglich für eine imperative Sprache entwickelte (Ada95) hier für die Objektorientierung umgewandelt und Teile des Ansatzes behalten. Java macht's mir an vielen Stellen leichter als Ada95, daher auch größere Abwandlungen. Behalten habe ich im prinzip den Ken mit der Auswahl der Methode und eben die beiden Methoden.
Was ich jedoch nicht möchte ist ein bereits fertiger Ansatz oder eine fertige Lösung. Ich habe aus Spaß am Programmieren vor zwei Tagen damit begonnen, diesen Algorithmus zu schreiben und möchte am Ende das Gefühl haben, selbst etwas geleistet zu haben und nicht einfach eines anderen Lösung angepasst zu haben ... möchte auch als Student und Offizieranwärter einfach mal stolz drauf sein dürfen :-D
Liebe Grüße
Moch
Wer keine Lust auf den Text hat: Die Fragen stehen gaaanz unten
Hallo,
Ich programmiere mir derzeit einen Algorithmus, der ein eingegebenes Sudoku lösen soll bzw. bei unlösbarkeit des Selbigen genau diesen Umstand zurückgeben soll. Hierzu habe ich (bisher) einen zwei-Klassen-Ansatz gewählt.
Die 1. Klasse heißt Sudoku. Der Konstruktor besteht aus zwei boolean, von denen einer angibt, ob das Sudoku bereits gelöst ist und der andere, ob es im aktuellen Status (!) noch lösbar ist.
Weiterhin findet sich im Konstruktor ein 9X9 Array aus Feldern (siehe zweite Klasse), das auch sogleich durch eine simple doppel for-schleife vorbelegt wird.
Die 2. Klasse heißt Feld. Jedes Feld repräsentiert eines der 81 Felder, die ein Standardsudoku hat. Dementsprechend "weiß" jedes Objekt Feld:
- seine Koordinaten (X,Y)
- seinen Sektor (damit meine ich diese 3x3-Quadrate, für die ebenfalls die Regel gilt, dass eine Zahl nur einmal vorkommen darf)
- ob es sich beim eingetragenen Wert um einen Fix-Wert handelt (bereits eingetragene Zahl) (boolean)
- welche Zahlen noch eingetragen werden können (Int-Array, das zu Beginn die Länge 9 hat).
Beide Klassen habe ich mit den nötigen Methoden versehen, um Änderungen an Variablen und Arrays vorzunehmen, Überprüfungen der Stati vorzunehmen. Intern gibt es in einigen Methoden Exceptions, die eine Verletzung bestimmter Bedingung verhindern soll (z.B. darf der fix-Boolean eines Felds nicht auf true gesetzt werden, wenn die Lösungsmenge noch größer als 1 ist) ... ja, hätte ich auch über eine einfache IF-Abfrage machen können, aber das macht's mir bei tests einfacher rauszufinden, wo der Fehler auftritt.
Der Algorithmus selbst soll wie folgt arbeiten:
1. User ein Sudoku eingeben lassen
2. Sudokugültigkeit prüfen (kommen schon im Ursprung zwei Zahlen in gleiche zeile/spalte/sektor vor?)
3. prüfen, ob Sudoki bereits gelöst (wenn ja, dann abbruch und Ausgabe)
4. Lösungsmenge der Felder korrigieren
5. prüfen, ob Sudoku in diesem Status noch lösbar (keines Feldes Lösungsmenge darf kleiner 1 werden)
6. prüfen, ob es Felder gibt, deren Lösungsmenge == 1 ist
7. Auswahl der Methode zur weiteren Lösung
8. Rücksprung zu Schritt 3.
Meine Probleme bestehen jetzt im Punkt 7
Ich unterscheide hierbei zwischen zwei wesentlichen Ansätzen:
1. Dem simplen Ansatz
2. Dem backtracking-Ansatz
Der 1. Fall ist nur möglich, wenn es in der Prüfung (Schritt 6) mindestens 1 Feld gibt, dessen Lösungsmenge == 1.
Hierbei werden einfach alle Felder, deren Lösungsmenge = 1 ist mit dem entsprechenden fix-Wert belegt.
Der simple Ansatz ist (meiner Meinung und Programmierung nach) zu bevorzugen und wird wann immer möglich ausgeführt. Begründung hier ist: Der Ansatz ist NICHT rekursiv
Der 2. Fall tritt genau dann ein, wenn der simple Ansatz unmöglich ist, da die Lösungsmengen durchgehend nicht eindeutig sind (Länge der Lösungsmenge größer 1). Hierbei soll der Algorithmus das Feld mit der kleinsten Lösungsmenge raussuchen. Werden mehrere mit gleicher Lösungsmenge gefunden, so wird das erste gefundene Feld ausgewählt.
Nacheinander sollen hier alle für dieses Feld möglichen Lösungen ausprobiert werden.
(Beispiel: noch mögliche Zahlen für Feld A sind 1,3,5 -> das Programm setzt zunächst 1 als FixWert und prüft, ob eine Lösung rauskommt, wenn nein, dann das gleiche mit drei, wenn wieder nein, dann mit 5 und wenn wieder nicht, ist das Sudoku nicht lösbar ... führt eine der Möglichkeiten zu einer Lösung, wird sofort die Ausgabe erzeugt und das Programm endet.)
In beiden Fällen wird das ursprüngliche Sudoku verändert und wieder durch den Lösungsalgorithmus gejagt (Ansatz hierfür ist interativ: eine while-schleife prüft, ob Sudoku gelöst oder unlösbar und beendet sich, wenn diese Bedingung erfüllt)
So viel zu meinem bisherigen Ansatz. Nun zu meinen Fragen, die hierzu aufgetreten sind:
1. Wie schaut es beim Kopieren von Objekt (hier das Objekt Sudoku) mit Pointern aus?
Sagt man bei einem Array einfach, es sei = anderes Array, kopiert man ja nicht das Array, sondern nur den Pointer.
Ist das bei Objekten bzw. Objekten die Arrays mitführen ebenfalls so?
(da müsste ich entsprechend eine tiefergehende kopiermethode schreiben, ähnlich der für Arrays)
2. Wie schaut es mit der Machbarkeit des Backtrackings aus speichertechnischer Sicht aus?
Als WorstCase habe ich den Fall identifiziert, in welchem der User eine vollständig leeres Sudoku eingibt.
Alleine für die komplette erste Zeile gäbe es 9! Möglichkeiten.
Da ich aber davon ausgehe, dass Java die Schritte NACHEINANDER ausführen wird (sprich jeweils nur eine Möglichkeit zur Zeit prüft und dann entweder die Ausgabe erreicht oder einen Schritt zurückgeht), habe ich berechnet, dass die Rekursion eine Tiefe von 60 erreichen wird.
(9X9 Felder = 81 ... davon ausgehend, dass das jeweils letzte Feld eines Sektor wieder nur eine Lösung besitzt, wird hier der simple Ansatz gewählt. Es gibt 9 Sektoren, also 81 - 9 = 72
Weiterhin gilt auch für das letzte Feld einer Zeile wieder Lösungsmenge = 1. Dies gilt für 6 Zeilen => 72 - 6 = 66.
Hinzu kommt, dass für die komplette letzte Zeile wieder die Lösungsmenge = 1 ist. Dies gilt wieder für 6 Felder (nicht für 9, da ich die letzten Felder eines Sektors bereits zu anfang ausgerechnet habe
66 -6 = 60)
Sprich: Der Algorithmus wird im WorstCase 60 Sudokus erzeugen und das letzte als Lösung ausgeben.
Wird das mit hoher Wahrscheinlichkeit zu einem Stack-Overflow führen oder sollte das per se keine Probleme geben
(ich bin mir kein Rekursionen nie sicher, weshalb ich die auch nicht mag ... interativ habe ich hier aber keinen Ansatz gefunden)
3. Keine Frage, aber ich würde mich über Verbesserungsvorschläge für den von mir entwickelten Algorithmus freuen.
Ich habe einen Ansatz, den ich ursprünglich für eine imperative Sprache entwickelte (Ada95) hier für die Objektorientierung umgewandelt und Teile des Ansatzes behalten. Java macht's mir an vielen Stellen leichter als Ada95, daher auch größere Abwandlungen. Behalten habe ich im prinzip den Ken mit der Auswahl der Methode und eben die beiden Methoden.
Was ich jedoch nicht möchte ist ein bereits fertiger Ansatz oder eine fertige Lösung. Ich habe aus Spaß am Programmieren vor zwei Tagen damit begonnen, diesen Algorithmus zu schreiben und möchte am Ende das Gefühl haben, selbst etwas geleistet zu haben und nicht einfach eines anderen Lösung angepasst zu haben ... möchte auch als Student und Offizieranwärter einfach mal stolz drauf sein dürfen :-D
Liebe Grüße
Moch
Zuletzt bearbeitet:
