211service.com
Mathematik des Sudoku führt zu einer 'Richter-Skala' der Rätselhärte
Die weltweite Faszination für Sudoku hat zu einem plötzlichen Interesse an den mathematischen Eigenschaften des Puzzles geführt. In den letzten Monaten haben wir uns in diesem Blog angesehen, wie Mathematiker das Minimum-Sudoku-Problem gelöst haben und sogar wie sie die Mathematik von Sudoku zum Verschlüsseln von Bildern verwendet haben .
Heute bekommen wir dank der Arbeit von Maria Ercsey-Ravasz an der Babes-Bolyai-Universität in Rumänien und Zoltan Toroczkai an der Universität Notre Dame in Indiana eine andere Sichtweise auf Sudoku.
Diese Jungs haben eine Methode entwickelt, um die Schwierigkeit eines bestimmten Sudoku-Rätsels zu messen und sagen, dass ihre Richter-Skala der Rätsel-Schwierigkeit auf eine Vielzahl anderer Spiele angewendet werden könnte.
Zuerst ein kleiner Hintergrund über Sudoku. Dies ist ein Zahlenrätsel, das aus einem 9 x 9-Raster besteht, in dem einige Zellen Hinweise in Form von Ziffern von 1 bis 9 enthalten das Raster enthält alle neun Ziffern. Außerdem kann jedes Gitter nur eine Lösung haben.
Sudoku-Rätsel werden im Allgemeinen als leicht, mittel oder schwer klassifiziert, wobei Rätsel im Allgemeinen mehr Starthinweise haben, aber nicht immer einfacher zu lösen sind. Aber die Schwierigkeit mathematisch zu quantifizieren ist schwierig.
Jetzt sagen Ercsey-Ravasz und Toroczkai, dass sie mithilfe der algorithmischen Komplexitätstheorie einen Weg gefunden haben, dies zu tun. Sie weisen darauf hin, dass es einfach ist, einen Algorithmus zu entwickeln, der Sudoku löst, indem jede Ziffernkombination getestet wird, um die richtige zu finden. Diese Art von Brute-Force-Lösung garantiert Ihnen eine Antwort, aber nicht sehr schnell.
Stattdessen suchen Algorithmus-Designer nach klügeren Wegen, um Lösungen zu finden, die die Struktur und die Einschränkungen des Problems ausnutzen. Diese Algorithmen und ihr Verhalten sind komplexer, aber sie erhalten schneller eine Antwort.
Der zentrale Punkt der Argumentation von Ercsey-Ravasz und Toroczkai ist, dass, weil ein Algorithmus die Struktur des Problems widerspiegelt, sein Verhalten – die Drehungen und Wendungen, denen er durch den Zustandsraum folgt – ein gutes Maß für die Schwierigkeit des Problems ist.
Um dies zu demonstrieren, greifen sie das Beispiel Sudoku auf. Anstelle der Brute-Force-Lösung entwerfen sie einen viel eleganteren Algorithmus, der die verschiedenen Einschränkungen des Puzzles ausnutzt, wie zum Beispiel die Tatsache, dass jede Zeilenspalte und jedes Unterraster alle Ziffern von 1 bis 9 enthalten muss.
Auf diese Weise transformieren sie das Problem in einen Typ, der Komplexitätstheoretikern als k-sat-Problem bekannt ist.
Sie beginnen damit, eine zufällige Menge von Zahlen in das Raster einzufügen und folgen der Flugbahn des Algorithmus durch den Zustandsraum, während er nach einer Lösung sucht. Für ein einfaches Problem ist diese Flugbahn einfach, wie in der oberen der beiden Abbildungen oben in diesem Beitrag gezeigt.
Aber all das ändert sich für ein schwieriges Problem. Ercsey-Ravasz und Toroczkai testen ihren Algorithmus gegen ein Sudoku-Raster so hart, dass es einen eigenen Namen hat: Platinblond. Das Ergebnis ist in der unteren Hälfte der Abbildung dargestellt. Es ist wesentlich komplexer und dauert zehnmal so lange, bis es gelöst ist.
Ercsey-Ravasz und Toroczkai sagen, dass bei schwierigen Problemen der Weg chaotisch wird, bevor man sich auf eine Lösung einlässt. Tatsächlich ist die Zeit, die es braucht, um diesem chaotischen Zustand zu entkommen, ein einfaches Maß für die Schwierigkeit.
Auf dieser Grundlage erstellen sie eine „Richter-Skala“ der Rätselschwierigkeit basierend auf der Fluchtrate. Die Skala reicht von 1 bis 4, wobei 1 die einfachste und 4 ultrahart ist.
Sie sagen, dass diese Skala überraschend gut mit den subjektiven menschlichen Bewertungen korreliert, wobei 1 für leichte Rätsel, 2 für mittlere Rätsel und 3 für schwere Rätsel steht. Das Platinblond hat einen Schwierigkeitsgrad von 3,5789.
Eine interessante Folgerung ist, dass kein Sudoku-Rätsel mit einem Schwierigkeitsgrad von 4 bekannt ist. Und auch die Anzahl der Hinweise ist nicht immer ein gutes Maß für den Schwierigkeitsgrad. Ercsey-Ravasz und Toroczkai sagen, dass sie viele Rätsel getestet haben, darunter mehrere mit den 17 Hinweisen, der Mindestanzahl und einige mit 18 Hinweisen.
Diese waren alle leichter zu lösen als das Platinblond, das 21 Hinweise hat. Denn die Härte des Puzzles hängt nicht nur von der Anzahl der Hinweise ab, sondern auch von deren Position.
Eine interessante Frage ist nun, ob es tatsächlich ein ultrahartes Puzzle mit Schwierigkeitsgrad 4 gibt und wie es gefunden werden kann.
Bedeutsamer ist, dass die Methode von Ercsey-Ravasz und Toroczkai auf alle k-sat-Probleme derselben Klasse wie Sudoku verallgemeinert. Die Schwierigkeit dieser Probleme kann also alle durch ähnliche Richter-Skalen klassifiziert werden.
Bleibt nur eine Frage – wie sollte die Skala der Rätselschwierigkeit genannt werden? Die offensichtliche Antwort ist die Ercsey-Ravasz- und Toroczkai-Skala oder ERT-Skala. Alle anderen Vorschläge im Kommentarbereich unten.
Ref: arxiv.org/abs/1208.0370 : Das Chaos im Sudoku