Sudoku zur Kompression verwenden
-
Wie genau sieht denn eigentlich ein größeres Sudoku aus?
-
Jester schrieb:
Wie genau sieht denn eigentlich ein größeres Sudoku aus?
Na nen 15*15 Sudoku im Hexadezimalsystem z.B.
-
Man kann die Lösung auch schon vorher errechnen und dann in die komprimierte Datei mit einfügen. Dann geht das extrahieren natürlich sehr viel schneller, da die Berechnung nicht mehr gemacht werden müssen.
-
dragon90# schrieb:
Jester schrieb:
Wie genau sieht denn eigentlich ein größeres Sudoku aus?
Na nen 15*15 Sudoku im Hexadezimalsystem z.B.
Sudokus müssen nicht mit Ziffern realisiert werden. Man kann ohne Weiteres auch ein 100x100 Sudoku mit den entsprechenden Zahlen machen. Wer sagt denn, dass pro Feld immer nur eine Ziffer notiert sein darf? Genau genommen kann man Sudokus sogar mit absolut beliebigen Zeichen machen.
Dass die beiden hier vorgestellten "Löser" mit solchen Sudokus nicht umgehen können, ist eine andere Geschichte.
-
Was genau ist für Dich der Unterschied zwischen Zahlen und beliebigen Zeichen? Wir nummerieren einfach die Zeichen durch und fertig. Ich wollte nur wissen, wie man es sinnvoll verallgemeinert.
Damit können die beiden Löser damit schon umgehen (vielleicht müßte man noch die Schleifengrenze hochsetzen).
-
Worauf man aber achten sollte: Nehmt keine Primzahlen als Kantenlaenge. Sonst wirds langweilig.
-
hehejo schrieb:
Nun, das mag für kleine Sudokus gelten.
Aber wenn du in einem Sudoku eine große Datei reinschreiben willst, dann muss das Sudoku ja entsprechend groß werden...Wenn es um Kompression geht kann man eine Datei auch als folge mehrerer kleiner Sudokus ansehen.
Allerdings sollte es mich wundern wenn der Algorithmus für grössere Sudokus öfters Backtracken müsste. Denn der Fall wo dies nötig ist, ist ein ganz spezieller wo sich alle Kolonnen, Lininen und Kisten in den Schwanz beißen. Bei 9x9 muss man schon gut suchen um solche Sudokus zu finden und bei grösseren sollte es noch schwieriger sein da noch mehr Bedinungen gleichzeitig erfüllt sein müssen. Es kann also durchaus sein, dass die Laufzeit bei grösseren Sudokus besser wird. :p
Desweiteren muss der Algo ja gar nicht alle Sudokus lösen können. Er muss legentlich die lösen können welche der Kompressionsalgo ausgespuckt hat. Man muss also nur den so trimmen, dass der Backtrackfall nicht eintritt.
-
Lösung schrieb:
Man kann die Lösung auch schon vorher errechnen und dann in die komprimierte Datei mit einfügen. Dann geht das extrahieren natürlich sehr viel schneller, da die Berechnung nicht mehr gemacht werden müssen.
Naja, die Lösung ist doch grad die Komprimierung..
Wenn du die wieder mit reinsteckst, dann kannste die Datei auch gleich so nehmen.
-
Jester schrieb:
Was genau ist für Dich der Unterschied zwischen Zahlen und beliebigen Zeichen? Wir nummerieren einfach die Zeichen durch und fertig.
Ich rede von Bäumchen, Häuschen, Vierecken, irgendwelchen lustigen Zeichen halt. Das diese auf Zahlen abbildbar sind und es bei konkreten Implementierungen mit Rechnern zwangsläufig darauf hinausläuft, liegt schlicht in der Natur der Sache und dürfte kaum erwähnenswert sein.
Bei einem "Real-World-Sudoku" gibt es aber keinen Grund und keine Notwendigkeit irgendwas auf Zahlen oder Ziffern zurückzuführen. Dort ist es schlicht Konvention, dass man Ziffern verwendet. dragon90#s Beitrag lässt aber vermuten, dass er dem Irrtum aufsaß, dass in jedem Feld nur eine Ziffer stehen könne. Dem ist eben nicht so. Und genau darum ging's mir.
-
hehejo schrieb:
Es gibt keine atm noch keine besserer Lösung als einfach auszuprobieren.
Naja. Das ist die Lösung, die man mit dem wenigsten Nachdenken realisieren kann. Ich kann mir durchaus vorstellen, dass es bessere Verfahren zum Lösen eines Sudokus gibt. Vielleicht könnte man das Lösen eines Sudokus irgendwie auf das Lösen eines Gleichungssystems reduzieren?
Wenn man die Sudokus nicht eh alle so schnell lösen könnte, würde es sich direkt mal lohnen, solchen Ideen nachzugehen.
-
Und am Ende arbeitest du damit am Problem P=NP.
Wenn du etwas schnellers findest als nur ausprobieren -- dann bist du reich.Und eines noch @Threadstarter:
DU bist Schuld.
Eigentlich dachte ich, dass ich mich dem Sudokuhype entziehen kann.
Aber jetzt hab ich ein paar teilsweise gemacht und bin "begeistert".Vielen Dank. :-þ
-
hehejo schrieb:
Und am Ende arbeitest du damit am Problem P=NP.
Wenn du etwas schnellers findest als nur ausprobieren -- dann bist du reich.Das wäre wohl ne andere Aufgabe. Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.
-
Sudoku zur Kompression verwenden, klingt interessant. Könnte man dabei (falls möglich) nicht auch mehrfach komprimieren?
Ich hatte mir auch mal zum Spaß überlegt, ob man Hashes zur Komprimierung verwenden könnte. So ein MD5-Hash ist in Byteform ja 16 Bytes lang. Angenommen, also wirklich nur rein fiktiv, man hätte eine Tabelle die alle möglichen Hashs von 20 Byte Strings enthält, dann würde man pro Hash 4 Bytes sparen. So eine ganze Datei durch und man hätte einige Bytes gespart. Aber jetzt könnte man ja diese Hashs wieder Hashen usw. usw... Zum Schluss hätte man eine gigabytegroße Datei zu 16 Bytes "komprimiert" und könnte diese dann wieder entkomprimieren.
Reines GedankenspielGruß
yogle
-
Die Zuordnung Wert -> Hash(Wert) ist aber leider nicht bijektiv. Wie soll sie auch? Die Menge der unterschiedlichen Hashes ist kleiner als die Menge der unterschiedlichen Werte (es sei denn, du nimmst Hashes, die genauso groß sind wie die Werte, das ist dann aber auch keine Kompression).
-
yogle schrieb:
Sudoku zur Kompression verwenden, klingt interessant. Könnte man dabei (falls möglich) nicht auch mehrfach komprimieren?
Ich hatte mir auch mal zum Spaß überlegt, ob man Hashes zur Komprimierung verwenden könnte. So ein MD5-Hash ist in Byteform ja 16 Bytes lang. Angenommen, also wirklich nur rein fiktiv, man hätte eine Tabelle die alle möglichen Hashs von 20 Byte Strings enthält, dann würde man pro Hash 4 Bytes sparen. So eine ganze Datei durch und man hätte einige Bytes gespart. Aber jetzt könnte man ja diese Hashs wieder Hashen usw. usw... Zum Schluss hätte man eine gigabytegroße Datei zu 16 Bytes "komprimiert" und könnte diese dann wieder entkomprimieren.
Reines GedankenspielAlso ehrlich geasgt halte ich die Idee, Sudokus zur Kompression zu verwenden, für Unfug. Genauso wie die Idee mit den Hashes.
Hashes sind nicht eindeutig: Das heißt, dass Du sehr viele unterschiedliche Daten hast, die auf den gleichen Hashwert abgebildet werden. Entsprechend kannst Du aus den Hashwerten alleine nicht bestimmen, zu welchen Daten sie gehören. ...bzw. sie gehören einfach nicht zu bestimmten Daten.
Auch bei den Sudokus ist es so, dass Du den Informationsgehalt, der in den Daten steckt nicht einfach so auf Daten reduzieren kannst, die diesen Informationsgehalt nicht hergeben. Wenn deine Daten grundsätzlich schon so eine Art Sudoku-Struktur haben, wird das sicherlich gehen, das haben Daten im Allgemeinen aber nicht. Das heißt, dass Du Daten darüber abspeichern musst, wie Du deine zu komprimierenden Daten, auf diese Struktur bringst. ...und diese Daten werden dann wieder entsprechend groß sein: Vermutlich wird der Effekt deine zu speichernde Datenmenge sogar enorm vergrößern und nicht komprimieren. Übliche - verlustfreie - Kompressionsalgorithmen nutzen meistens Redundanzen und ähnliche Dinge in den ursprünglichen Daten aus, die dann irgendwie bei der Kompression entfernt werden. Mit anderen Worten: Da wird ausgenutzt, dass in den ursprünglichen Daten weniger Information enthalten ist, als man in dem genutzten Speicherplatz unterbringen könnte. Ich sehe keine Möglichkeit, wie man die grundsätzliche Tatsache, dass Informationen einen gewissen Speicherlatz benötigen, einfach so durch irgendein tolles Verfahren außer Kraft setzen kann.
Wenn man Gedankenspiele machen kann, bei denen rauskommt, dass man durch sein Verfahren alle Daten auf wenige Bytes reduzieren kann, dann ist das ein sicherer Hinweis darauf, dass das Verfahren einfach Mist ist. Es wird nicht funktionieren.
-
Was mir gerade ausffaellt: Sind die Spielfelder eigentlich immer symmetrisch voreingefuellt?
-
Klar, dass mit den Hashes ist ja auch nur ein Gedankenspiel.
Aber ich weiß nicht wie viele Kollisionen es unter 20 Bytesstrings gibt. Sicher es gibt einen Haufen Kollisionen bei denen die eine Datei 10 Bytes und die andere 4129458 Bytes groß ist, aber wenn beide genau 20 Bytes groß sind? Auch egal, umsetzen kanns eh keinerBei Sudoku kenn ich mich nicht so aus. Bin den Hype noch nicht erlegen
Gruß
yogle
-
yogle schrieb:
Klar, dass mit den Hashes ist ja auch nur ein Gedankenspiel.
Das machts nicht richtiger.
Aber ich weiß nicht wie viele Kollisionen es unter 20 Bytesstrings gibt. Sicher es gibt einen Haufen Kollisionen bei denen die eine Datei 10 Bytes und die andere 4129458 Bytes groß ist, aber wenn beide genau 20 Bytes groß sind? Auch egal, umsetzen kanns eh keiner
Häh? Ich kann dir so viel sagen: Es gibt immer so viele Kollisionen, dass du auf die selbe durchschnittliche Größe bei der Ausgabe kommst wie bei der Eingabe. Es kann nunmal kein Verfahren geben, dass alle Dateien verkleinert.
-
Gregor schrieb:
Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.
Es ist wohl tatsächlich NP-vollständig. Daß es in NP steckt war hoffentlich vorher schon klar. Ein fertig ausgefülltes Feld zu prüfen geht schließlich sogar in Linearzeit.
Ich finde es auch nicht weiter erstaunlich, daß es NP vollständig sein soll, angesichts der Tatsache, daß schon deutlich "einfachere" Dinge, wie zum Beispiel Minesweeper NP vollständig sind.
-
Jester schrieb:
Gregor schrieb:
Die Frage ist doch, ob die Problemstellung, die man bei Sudoku hat, überhaupt in NP steckt. Es ist ja nicht so, dass kein Problem, das man irgendwie durch Suche oder ähnliches lösen kann, besser gelöst werden könnte.
Es ist wohl tatsächlich NP-vollständig. Daß es in NP steckt war hoffentlich vorher schon klar. Ein fertig ausgefülltes Feld zu prüfen geht schließlich sogar in Linearzeit.
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. Ok, aber man hat ja noch zu viele Freiheitsgrade. Ich weiß nicht, ob man da vielleicht noch die Ungleichungen reinbringen kann, die für jede Zeile, Spalte und jedes kleine Quadrat gelten? Keine Ahnung, ob man damit gut arbeiten kann. Zumindest bin ich mir alles andere als sicher, dass man dieses Problem nicht auf eine Art und Weise formulieren kann, wo es offensichtlich nicht in NP fällt.
Naja, vielleicht fehlt mir da aber auch einfach noch entsprechender theoretischer Hintergrund. Kannst Du mir erklären, warum Du denkst, dass dieses Problem NP ist?
PS: Ok, fällt natürlich in NP.
...die Frage ist aber eher: Gibt es auch eine "bessere" Komplexitätsklasse, in die dieses Problem auch fällt?