Das Sudoku Problem

[Teelicht]

Hallo Leute,

ich sitze gerade im Informatikunterricht und muss mir Gedanken über das Sudoku Problem machen. Keine Angst, ich programmier es selbst, aber ich hatte gerade eine kleine Diskussion mit meinem Infolehrer, ob das nicht schon eine einfache Form der KI ist!? Mein Lehrer meinte, zur KI gehöre dann schon mehr, aber wenn ich mal an Schachcomputer denke, habe ich einen Computer im Kopf, der verschiedene Zugmöglichkeiten hat und dann durch in-Gedanken-durchprobieren ausprobiert, was wohl der intelligenteste Weg ist. Das wäre bei Sudoku doch ähnlich? Nach der Backtracking Methode probiert man aus, setzt erst mal eine Zahl ein und wenn es keine Lösung gibt, setzt man eine andere ein - erinnert insgesamt sehr an Heuristik, wäre das dann keine - zugegebenermaßen wohl relativ einfache(?) - Anwendung der KI?

Gruß, Micha

[drunken monkey]

Ich bin mir ziemlich sicher, dass man soetwas in keinster Weise als KI bezeichnen kann. Eine KI muss auf unterschiedliche Probleme sinnvoll reagieren können und auch lernfähig sein, auf ein Programm, dass einfach durch begrenzte Enumeration, oder was auch immer, ein Sudoku löst, trifft nichts davon zu. Das ist ein einfacher Algorithmus und nichts, was man imo als "intelligent" bezeichnen kann.

[Teelicht]

mh, komisch - und was ist an einem wegfindeprogramm so phänomenal intelligenter? so wirklich kapier ich nicht, was bei diesem klassischen anfängerproblm für KI begeisterte anders sein soll... man probiert auch einfach alle möglichkeiten durch und sucht damit die kürzeste, oder nicht?

[MagicMagor]

Wer behauptet das ein einfacher Wegfinde-Algorithmus intelligent ist?

Generell ist es schwierig zu sagen was genau eine KI ist, da streng genommen eine Intelligenz mit Computern nicht realisierbar, allerhöchstens simulierbar ist.
Ich würde sagen, eine KI muss in einer gegebenen Situation eine Entscheidung treffen zwischen mehreren möglichen Optionen und dabei versuchen aufgrund diverser Kriterien die "beste" oder sinnvollste Option zu wählen.
Wenn du ein Sudoku mittels reinem Ausprobieren löst, handelt sich um keine wirkliche Intelligenz, da nur willkürlich ausprobiert wird, bis das einzig mögliche Ergebniss eintrifft.

Beim Schach-Computer ist das anders. Hier rechnet der Computer zwar auch mehrere Zugmöglichkeiten aus, aber es ist nicht so, daß er dann die eine einzig richtige Zugabfolge findet. Stattdessen rechnet er einige Züge tief und bewertet anschließend die Brettstellung. Dann vergleicht er mehrere dieser Brettstellung und wählt die aus, die ihm für ihn am vorteilhaftesten vorkommt und zieht entsprechend.
Durch das bewerten kommt hier etwas hinzu, was ein wichtiger Bestandteil einer Intelligenz ist, nämlich die Bewertung einer vorher unbekannten Situation um daraus Schlüsse für die beste Wahl zu ziehen. Bei deinem Sudoku-Beispiel fehlt das, da wird einfach sturr durchgerechnet. Oder würdest du ein Bruteforce-Programm, daß auf ein passwort angesetzt wird als intelligent im knacken von Passwörtern bezeichnen?

[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:
http://img115.imageshack.us/img115/2300/sudokustrategie2mi9.png

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:
http://schattentier.sc.ohost.de/sudoku.PNG
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. ^^