@Moritz: danke für die Seite, die Möglichkeit das Problem auf eine große dünnbesetzte Inzidenzmatrix zurückzuführen ist sehr symmetrisch und damit sehr elegant, das erfreut das Mathematikerherz... 8 )

Ich weiß aber nicht ob ich die Seite so schnell verstanden hätte wenn ich nicht mein halbes Studium mit solchen Strukturen verbracht hätte, du könntest aber vielleicht auch noch erwähnen, dass im Allgemeinen "Exact Cover"-Probleme NP-vollständig sind(was aber nicht für diesen Sonderfall "Sudoku" gelten muss)

Und da es immer noch Backtracking erfordert, lässt es m.E. auch viel Raum für Heuristiken, die die Wahl des erfolgversprechensten nächsten Zuges bestimmen, deswegen ist es von der Lösungsgeschwindigkeit IMHO nicht zwingend einem anderem Ansatz überlegen, es ist aber zumindest sehr elegant und einfach zu implementieren.

Um die Sache abzurunden: Anbei noch Bilder der beteiligten Wissenschaftler: Professor Knuth Professor Knox ; )