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.