 Sudokuloeser |
Shaihulut 
Grünschnabel
Dabei seit: 22.11.2006
Beiträge: 6
 |
|
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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shaihulut: 22.11.2006 14:18.
|
|
22.11.2006 14:08 |
|
|
David1979
Mitglied
Dabei seit: 26.09.2006
Beiträge: 27
|
|
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:45 |
|
|
Shaihulut
Grünschnabel
Dabei seit: 22.11.2006
Beiträge: 6
|
|
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.
|
|
|
22.11.2006 15:22 |
|
|
David1979
Mitglied
Dabei seit: 26.09.2006
Beiträge: 27
|
|
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
|
|
|
22.11.2006 15:59 |
|
|
|
