Sudoku zur Kompression verwenden
-
Ok, ich seh es ein.
...vielleicht sollte ich mich mal ein bischen mit Komplexitätstheorie befassen.
-
Vielleicht mal ne Anmerkung am Rande:
Spektrum der Wissenschaft, März 2006 - Seite 100, "Sudoku oder die einsamen Zahlen"
Da werden auch Lösungsstrategien diskutiert.
-
Gregor schrieb:
Ist mir immer noch nicht klar, dass das in NP sein soll. Man hat da 81 Variablen. Ein Drittel davon ist meistens so in etwa vorgegeben. Für ein weiteres Drittel könnte ich aus dem Stand heraus entsprechende Gleichungen aufschreiben. Nämlich jeweils die Zeilensumme, die Spaltensumme und die Summe in jedem kleinen Quadrat. ...Das Lösen von Gleichungssystemen fällt AFAIK nicht in NP.
Ich glaub nicht, dass die Summe eine ausreichende Bedingung ist. In dem Fall könnte man das gesamte Sudoku nähmlich als System linearer Gleichungen schreiben mit 81 Variablen.
Um ein System mit 81 Variablen eindeutig lösen zu können braucht man mindestens 81 Gleichungen. Wir haben 9 Reihen, Spalten und Kisten. Das macht 27 Gleichungen. Wir brauchen also mindestens noch 54 weitere welche nur in Form von gegebenen Kästchen exsistiren können. Also ist 54 die Mindestanzahl von gegebenen Kästchen um ein eindeutig lösbares Sudoku zu haben. Laut Wikipedia gibt es aber auch eindeutig lösbare mit 17 gegeben Feldern.