Das Sudoku Problem

[derBenny]

Ein Sudoku sollte relativ einfach zu lösen sein. Normalerweise gibt es immer ein Feld, das eindeutig bestimmbar ist. Man erstellt ein Array von 9 boolschen Variablen, die jeweils für eine der neun möglichen Ziffern stehen. Dann überprüft man, welche Ziffern nicht möglich sind, weil sie in der horizontalen Reihe, der vertikalen Reihe oder dem 3x3-Feld des zu überprüfenden Feldes bereits auftauchen, und streicht diese. Man überprüft alle freien Felder und setzt, wenn nur noch eine Ziffer übrig bleiben sollte, diese Ziffer ein.

Es gäbe noch eine andere Strategie, bei der man sich immer gerade auf eine Ziffer beschränkt und ohne die man manchmal nicht weiterkommt. Wie man die programmiert müsste man sich nochmal überlegen, aber das sollte auch möglich sein.

Mit beiden Techniken zusammen sollte es eigentlich möglich sein, ein Lösungsprogramm zu schreiben, auch wenn es vermutlich sehr rechenintensiv wäre.

Wie man das ganze mit den Methoden der KI lösen soll, weiß ich allerdings nicht.


Backtracking halte ich bei Sudoku nicht für sinnvoll, da es wirklich viele Möglichkeiten und andere, einfachere Ansätze (s.o.) gibt.

[Mog]

Ich selber halte Backtracking nicht immer fuer ganz schlecht. Mein Sudoku-solver ist eine wunderschoene rekursive Funktion, die ganz einfach erst immer alle eindeutigen Moeglichkeiten findet und erst im Fall der Faelle per Kombinatorik einen bestimmten Versuch waehlt.

Was ausprobieren und sehen mit KI zutun haben soll weiss ich aber um ehrlich zu sein nicht ganz. schau dir am besten irgendwo die Deffinition an, dann wird dir der Unterschied wohl schnell klar.

[Teelicht]

Ein Sudoku sollte relativ einfach zu lösen sein. Normalerweise gibt es immer ein Feld, das eindeutig bestimmbar ist. Man erstellt ein Array von 9 boolschen Variablen, die jeweils für eine der neun möglichen Ziffern stehen. Dann überprüft man, welche Ziffern nicht möglich sind, weil sie in der horizontalen Reihe, der vertikalen Reihe oder dem 3x3-Feld des zu überprüfenden Feldes bereits auftauchen, und streicht diese. Man überprüft alle freien Felder und setzt, wenn nur noch eine Ziffer übrig bleiben sollte, diese Ziffer ein.

...

ja, auf den ansatz bin ich dann auch gekommen (unabhängig von dir). wozu du den booleanarray brauchst, ist mir dabei nicht ganz klar, aber jedem das seine^^ allerdings muss man den ansatz noch ausbauen, es ist nicht immer der fall, das ein feld pro gruppe eindeutig bestimmbar ist.

mh, schade, war wohl nichts mit der KI... menno

[derBenny]

wozu du den booleanarray brauchst, ist mir dabei nicht ganz klar, aber jedem das seine^^

...

Joa, da hast du Recht, das dient eigentlich nur der technischen Realisierung und hat mit dem Lösungsalgorithmus im Grunde nichts zu tun.

allerdings muss man den ansatz noch ausbauen, es ist nicht immer der fall, das ein feld pro gruppe eindeutig bestimmbar ist.

...

Wenn du ein Sudoku komplett betrachtest, das gesamte 9x9-Feld, dann wirst du immer ein Feld finden, das eindeutig lösbar ist. Raten muss man soweit ich weiß nie, das würde irgendwie am Sinn der Sache vorbeigehen. Aber wie gesagt, wenn man das ganze Feld einmal durchgegangen ist und mit dem ersten Ansatz kein eindeutiges Feld gefunden hat, muss man den anderen Ansatz durchlaufen lassen, der sich immer nur auf eine Ziffer beschränkt:

Man nimmt sich drei 3x3-Felder, die in einer Zeile liegen und wählt eine Ziffer n, die in zwei der 9x1-Zeilen vorkommt dadurch fallen für die dritte Ziffer n, die gesucht wird, schonmal zwei 3x3-Felder und zwei Zeilen im 3. 3x3-Feld weg, so dass für n genau drei Felder übrigbleiben. Wenn man Glück hat, sind einige davon schon belegt. Die restlichen schließt man aus, indem man die jeweilige Gesamtspalte (1x9) auf n überprüft. Damit findet man die einzige Stelle im 3. 3x3-Feld, auf der n liegen kann.
(Dasselbe gilt für Spalten. Einfach die Begriffe Zeile und Spalte vertauschen.)

Ein Beispiel:


Im markierten Feld könnte auch problemlos eine 8 oder eine 9 (zum Beispiel) stehen, es ist nicht eindeutig, aber dann könnte in dem dazugehörigen 3x3 Feld keine 7 mehr stehen, weil alle anderen Felder ausgeschlossen sind.

[Teelicht]

Joa, da hast du Recht, das dient eigentlich nur der technischen Realisierung und hat mit dem Lösungsalgorithmus im Grunde nichts zu tun.

...

Mh, mal sehen, vielleicht komm ich bei der Umsetzung ja noch auf ein Boolean Array, bisher hab ich mehr so eine IF Abfrage im Kopf... naja, aber egal, das wichtigere kommt jetzt erst:

Wenn du ein Sudoku komplett betrachtest, das gesamte 9x9-Feld, dann wirst du immer ein Feld finden, das eindeutig lösbar ist.

...

Ja, korrekt. Unsere Ansätze unterscheiden sich doch etwas^^

Ich gehe nämlich 3x3-Gruppenweise vor: Ich prüfe in der ersten 3x3 Gruppe alle Möglichkeiten aller freien Felder und vergleiche diese dann, sodass ich auf die Lösung komme. Das Problem, welches aufgetreten ist, war nun folgendes: Es kann passieren, das 2 Felder mit den selben beiden Möglichkeiten übrigbleiben. Na gut, die muss ich eben erst offen lassen, um dann abzuwarten, bis sie eindeutig bestimmbar sind. Bei deinem Ansatz dürfte so etwas nicht passieren, denn dein Ansatz sucht gleich am Anfang das ganze 9x9 Feld ab und findet dort selbstverständlich ein lösbares Feld. Gar nicht so dumm ^^

Das Beispiel von mir:

In den freien Feldern des oberen, mittleren 3x3 Feldes passen die Zahlen 2 und 3 rein, und zwar in beide Felder. Erst wenn man weitermacht und bei dem unteren, mittleren Feld angekommen ist, kommt heraus, dass es die Reihenfolder 3, 2 sein muss.

[Moyaccercchi]

Du könntest das ganze doch auch gleich rekursiv anlegen, sodass dein Programm immer die einzelnen 3x3-Felder überprüft, nicht bestimmbare frei lässt, und wenn es mit allen fertig ist, eine if-Abfrage kommt.
Sind schon alle Zahlen bestimmt -> fertig, wenn nicht - von vorne beginnen, und alle vorher ausgerechneten Zahlen sozusagen als gegeben betrachten. ^^