Sudokuloeser |
| 22.11.2006, 14:08 | Auf diesen Beitrag antworten » |
| Shaihulut | Sudokuloeser Hi, bin neu hier. Hab nen Problem mit einem Programm, ich soll einen Sudokuloeser in JAVA programmieren, hab es aber nur hinbekommen, das es nur eines der vier zu loesenden Beispiele korrekt loest. Bis her macht er nur das erste Beispiel. Die anderen habe ich so geloest, um vergleichen zu können. Beispiele: ----- Beispiel 1 ---------- Ausgangssituation: 057|420|000 040|071|090 200|080|000 ---+---+--- 030|704|200 065|800|300 080|903|054 ---+---+--- 800|000|746 914|000|005 500|000|000 Ergebnis: 357|429|681 648|371|592 291|586|437 ---+---+--- 139|754|268 465|812|379 782|963|154 ---+---+--- 823|195|746 914|637|825 576|248|913 ----- Beispiel 2 ---------- Ausgangssituation: 600|200|000 002|008|400 800|090|000 ---+---+--- 080|400|320 075|000|840 031|007|090 ---+---+--- 000|050|009 003|900|700 000|001|003 Ergebnis: 654|273|918 392|168|475 817|594|632 ---+---+--- 986|415|327 275|639|841 431|827|596 ---+---+--- 748|352|169 123|986|754 569|741|283 ----- Beispiel 3 ---------- Ausgangssituation: 050|801|070 200|600|108 000|020|600 ---+---+--- 003|500|400 000|030|000 007|006|500 ---+---+--- 008|010|000 906|002|005 020|908|030 Ergebnis: 659|841|372 274|653|198 381|729|654 ---+---+--- 193|587|426 562|134|987 847|296|513 ---+---+--- 738|415|269 916|372|845 425|968|731 ----- Beispiel 4 ---------- Ausgangssituation: 300|000|050 050|000|640 000|041|007 ---+---+--- 900|028|700 000|406|000 008|970|006 ---+---+--- 805|710|000 037|000|020 090|000|008 KEINE Lösung gefunden als anhang, gebe ich euch mal meinen Quellcode (Sudokuloeser.txt) mit, vieleicht findet jemand von euch nen Fehler. Ich habe schon seit Tagen gesucht, aber nichts gefunden. Ach eh ichs vergesse, auf folgender Seite ist noch eine class-Datei, die ich mit als grundlage habe, das is die AbstraktLoeser.class in Übung 5, ohne die gibt mein Prog keinen Sinn. http://www2.informatik.uni-erlangen.de/Lehre/WS200607/Algo1/uebungen/?langu age=de Bitte Hiillffee 
.Danke. |
|
|
|
| 22.11.2006, 14:45 | Auf diesen Beitrag antworten » |
| David1979 | RE: Sudokuloeser Hallo Shaihulut, nach welcher Lösungsstrategie bzw. welchem Algorithmus gehst du denn vor? Anmerkung: Das mit dem Quellcode ist gut gemeint, aber oft kann man das Problem mit einer objektiven formalen Herangehensweise schneller finden, als Fehler im Quellcode zu lokalisieren (auch aus Gründen der Übersichtlichkeit). Zudem können dann auch NICHT-Javaianer bei der Problemsuche helfen. Und als kleine Anregung für zukünftige Programme: Besonders bei komplexeren Methoden sollte man auf eine klare Strukturierung achten. Es macht die Wartung nicht gerade einfacher, wenn der Hauptteil des Programms in einer einzigen Methode untergebracht ist, die dann mehr als 120 Zeilen umfasst und hauptsächlich aus Wiederholungen und Verzweigungen besteht. Als grobe Richtlinie kann man sich merken, dass wenn eine Methode mehr als 20 Anweisungen hat, eventuell das Klassendesign nochmal überdacht werden sollte. 
Gruß, David |
| 22.11.2006, 14:56 | Auf diesen Beitrag antworten » |
| David1979 | RE: Sudokuloeser Zu deinem Edit: Wenn du die Klasse AbstraktLoeser unbedingt benötigst, warum benutzt du die abstrakte Klasse denn nicht?
(Es reicht nicht das Interface zu implementieren! Du musst von der abstrakten Klasse ableiten!) \\EDIT: Die Methode int[] moeglicheZahlen(...) müsstest du in deinem Programm erstmal auskommentieren, da sie sonst die Implementierung aus der abstrakten Klasse überschreibt. Allerdings führt das ganze anschließend zu einer Endlosschleife, was auch nicht wirklich besser ist 
Gruß, David |
| 22.11.2006, 15:22 | Auf diesen Beitrag antworten » |
| Shaihulut | Ich hatte mir das wie follgt gedacht
,Der Löser soll sich zu ersten Stelle des Feldes gehen, dort schaut er welche möglichen Zahlen er nehmen kann, dabei schaut er zuerst im aktuellen 3X3 Block schauen ob es die Zahl schon gibt, wenn ja verwirft er die Zahl und nimmt die nächste Zahl zwischen 1 und 9. Sollte es die Zahl noch nicht im Block geben, schaut er als nächstes in der aktuellen Zeile des gesamten Sudokufeldes nach ob die Zahl schon vorhanden ist, wenn ja, wird die Zahl für diese Stelle verworfen, ansonsten schaut er in der aktuellen Spalte nach ob es diese Zahl schon gibt, wenn ja verwirft er sie, wenn nein setzt er in das Feld die Mögliche Zahl ein. Dann springt der Löser an die nächste Stelle im Sudokufeld. So im groben hab ich es mir vorgestellt, für das erste Sudokufeld haut das auch hin, aber nich für die anderen. |
| Anzeige | |
|
|
|
| 22.11.2006, 15:59 | Auf diesen Beitrag antworten » |
| David1979 | Das hört sich fast ok an. Allerdings kann es passieren, dass wenn eine Zahl richtig gesetzt wurde (z.B. die Zahl 5 ins dritte Feld) und das nächste freie Feld angesteuert wird (z.B. das 5te), dort KEINE der Zahlen von 1 bis 9 passen (das könnte die Endlos-Schleife erklären). Also musst du zurückspringen ins dritte Feld und die nächst gültige Zahl versuchen. Dannach läufst du wieder ins nächste Feld (5) und probierst wieder alle Zahlen aus. Sollte im dritten Feld allerdings auch keine Zahl mehr passen, dann musst du in das Feld davor und die nächstgültige Zahl probieren. USW. Das Verfahren wird auch Backtracking genannt und läßt sich rekursiv programmieren. (Gehört übrigens in die Klasse der NP-Vollständigen Probleme). Hier ist eine Seite mit verschiedenen Backtrackingverfahren in Java. Gruß, David |
|
|