Sudoku mit Backtracking lösen

[WilliWacker]

Hallo,

ich habe ein Programm zum lösen von Sudokus geschrieben. Das logische lösen des Sudoku klappt. Meine Vorgehensweise ist die Folgende, ich habe ein 2d Array mit 9*9 Objekte der Klasse SudokuZelle. Die Klasse hat die Fähigkeit für jede Zelle ungültige Werte auszuschließen, eindeutige Werte und alle noch möglichen Werte der einzelnen Zelle zu liefern.

Durch das Ausschließen der Werte erhalte ich eine Kandidatenliste für jede Zelle.
Jetzt möchte ich auch Sudokus lösen, bei dennen es keinen eindeutigen Werte für jede Zelle gibt.

Hier ein Bsp. als 2*2 Spielfeld

1 0 | 0 0
0 0 | 0 0
-----------
0 0 | 0 0
0 0 | 0 0

Eine Methode zur Überpüfung, ob das Sudoku wiederspruchsfrei gelöst ist habe ich, das systematische durchprobieren der Kandidatenliste bereitet mir allerdings Kopfzerbrechen.

Danke schonmal für eure Hilfe.

 

[Elmu]

Warum schreibst du die Werte einer Zelle nicht in ein neues 2 dimensolaes Array und lässt dann diese Werte über eine Schleife Addieren.

Einmal horizental(Zeile für Zeile) und vertikal(Spalte für Spalte). Bei Sudoku müssen die dann doch alle einen ( den gleichen Wert haben?) , oder nicht.

Trifft der check für alle Zeilen und Spalten zu, dann ist es gelöst.


Hinzufügen kannst du auch noch, dass zusätzlich überprüft wird, ob in dem neuen Array in einer Spalte oder Zeile eine Zahl doppelt vorhanden ist.


Ich hoffe, dass ich dir helfen konnte, ansonsten hab ich die Frage nicht richtig verstanden.

 

[Elmu]

Ah, okay. Das Ende der Frage nicht gelesen gehabt, vergiss meine Antwort.

 

[HonniCilest]

Warum schreibst du die Werte einer Zelle nicht in ein neues 2 dimensolaes Array und lässt dann diese Werte über eine Schleife Addieren.

Einmal horizental(Zeile für Zeile) und vertikal(Spalte für Spalte). Bei Sudoku müssen die dann doch alle einen ( den gleichen Wert haben?) , oder nicht.

Trifft der check für alle Zeilen und Spalten zu, dann ist es gelöst.

@Elmu: Juhu

999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999

Sudoku gelöst....



@ WilliWacker: Ich persönlich verstehe nur nicht, was das obige Thema mit Backtracking zu tun hat. Möchtest du eventuell wissen, wie du Backtracking auf deinen Code anwenden kannst? Ohne Code kann man dir dann leider schlecht weiterhelfen, aber hier mal allgemeines:
Wichtige Punkte beim Backtracking sind:
Die Schritte Vorwärts und Rückwärts
Iterativ oder Rekursiv?
Wodurch ist eine Mögliche Lösung gekennzeichnet?
Soll nach einer Lösung beendet werden?
...

 

[Elmu]

Wenn du mich zitierst und darauf antwortest, dann bitte richtig. In meinen Post steht schon drin, dass jede Zahl nur 1mal pro Zeile oder Spalte zufinden sein darf.

System gibt es bei der Sache nicht, du lösst es einfach zufällig befüllen, dann lässt du einen Check durchlaufen, ob alles passt ( wird es garantiert nicht beim ersten mal) und dann kannst du dein weiteres vorgehen überlegen.

Entweder einfach immer wieder zufällig befüllen oder du gehst Zeile für Zeile und Spalte für Spalte durch und behebst immer Fehler, welche gegen die Spielregeln stoßen. Am Ende wieder einmal überprüfen und sonst wieder entweder Zeile für Zeile oder Spalte für Spalte wieder durchgehen.

bzw. 3x3 Feld oder was weiß ich - ich kenn das Spiel nur vom sehen.


// Beim 8Dame-Problem ist es ja nichts anderes, da wird solange nacheinander von hinten und von vorne geschoben, bis es passt.

 

[HonniCilest]

Wenn du mich zitierst und darauf antwortest, dann bitte richtig. In meinen Post steht schon drin, dass jede Zahl nur 1mal pro Zeile oder Spalte zufinden sein darf.

Warum überprüfst du dann noch die Summe?