Mathematiker lösen minimales Sudoku-Problem

Sudoku 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.

Es gibt noch eine weitere ungeschriebene Regel: Das Rätsel darf nur eine Lösung haben. Gitter können also nicht nur wenige Starthinweise enthalten.

Es ist leicht zu erkennen, warum. Ein Raster mit 7 Hinweisen kann keine eindeutige Antwort haben, da die beiden fehlenden Ziffern in jeder Lösung immer vertauscht werden können. Ein ähnliches Argument erklärt, warum Gitter mit weniger Hinweisen auch mehrere Lösungen haben müssen.

Aber es ist nicht so einfach zu verstehen, warum ein Raster mit 8 Hinweisen keine eindeutige Lösung haben kann, oder sogar eines mit 9 oder mehr Hinweisen.

Das wirft für Mathematiker eine interessante Frage auf: Wie viele Sudoku-Hinweise ergeben mindestens eine eindeutige Antwort?

Diese Frage beschäftigt die Sudoku-Community nicht zuletzt, weil sie glaubt, die Antwort zu kennen. Sudoku-Fanatiker haben zahlreiche Beispiele für Gitter mit 17 Hinweisen gefunden, die eine einzigartige Lösung haben, aber sie haben noch nie eines mit 16 Hinweisen gefunden.

Das deutet darauf hin, dass die Mindestzahl 17 ist, aber niemand konnte beweisen, dass es keine 16-Hinweis-Lösung gibt, die irgendwo im Rätselraum lauert.

Betreten Sie Gary McGuire und seine Freunde vom University College Dublin. Diese Jungs haben das Problem mit der bewährten mathematischen Technik der reinen Brute-Force gelöst.

Im Wesentlichen haben diese Jungs jede potenzielle 16-Hinweis-Lösung für jedes mögliche Sudoku-Gitter untersucht. Unsere Suche ergab keine richtigen 16-Hinweis-Rätsel, aber wenn es eines gegeben hätte, hätten wir es gefunden, heißt es.

Das ist eine beeindruckende Leistung. Es gibt genau 6, 670, 903, 752, 021, 072, 936, 960 mögliche Lösungen für Sudoku (ca. 10^21) . Das ist weit mehr, als in angemessener Zeit überprüft werden kann.

Aber wie es der Zufall so will, ist es nicht notwendig, sie alle zu überprüfen. Verschiedene Symmetrieargumente beweisen, dass viele dieser Gitter äquivalent sind. Dadurch reduziert sich die Anzahl der zu überprüfenden Stellen auf nur noch 5 472 730 538.

Also schrieben McGuire und Co. ein Programm namens Checker, um jedes dieser Raster auf eine 16-Hinweis-Lösung zu überprüfen.

Aber der Prozess der Überprüfung eines einzelnen Rasters ist selbst knifflig. Eine Möglichkeit, dies zu tun, besteht darin, jede mögliche Teilmenge von 16 Hinweisen zu untersuchen, um zu sehen, ob einer von ihnen zu einer eindeutigen Lösung führt. Das Problem ist, dass es für jedes Gitter etwa 10^16 Teilmengen gibt.

Wieder einmal ist ein wenig Mathematik nützlich. McGuire und Co haben einige kluge Argumente verwendet, um zu zeigen, dass bestimmte Teilmengen vielen anderen gleichwertig sind, und dies reduziert die Anzahl der zu überprüfenden Teilmengen dramatisch.

Trotzdem ist die daraus resultierende Berechnung immer noch ein Monster. Das Dubliner Team sagt, dass es 7,1 Millionen Kernstunden Verarbeitungszeit auf einer Maschine mit 640 Intel Xeon Hex-Core-Prozessoren benötigt hat. Sie begannen im Januar 2011 und endeten im Dezember.

Die ganze Übung mag nach mathematischem Spaß klingen, aber diese Art der Problemlösung hat viele wichtige Anwendungen. McGuire und Co. sagen, dass das Problem der Sudoku-Grid-Prüfung formal äquivalent zu Problemen bei der Genexpressionsanalyse und beim Testen von Computernetzwerken und Software ist.

Die Methoden des Dubliner Teams zur Beschleunigung der Berechnung werden sich also auch in diesen Bereichen direkt auswirken.

Aber während das Ergebnis eindeutig beeindruckend ist, ist das Minimum-Sudoku-Problem nicht ganz beigelegt.

Dieses Problem schreit nach einem eleganten Beweis, der uns erlaubt zu erkennen, warum die Mindestzahl 17 sein muss; eher wie der Beweis, dass es für 7 oder weniger Hinweise keine eindeutigen Lösungen geben kann.

Eine große Bitte, ich weiß, aber sicherlich eine, die es wert ist, angestrebt zu werden.

Ref: arxiv.org/abs/1201.0749 : Es gibt kein 16-Hinweis-Sudoku: Lösen des Sudoku-Problems mit der Mindestanzahl von Hinweisen

Korrektur: Dieser Beitrag wurde am 6. Januar bearbeitet, um das Argument widerzuspiegeln, dass, wenn ein n-Hinweis-Gitter eindeutig lösbar ist, das Hinzufügen einer Ziffer zu einem n+1-Hinweis-Gitter auch eindeutig lösbar sein muss. Wenn es also keine eindeutig lösbaren 16-Hinweis-Gitter gibt, kann es auch keine Gitter mit weniger eindeutig lösbaren Hinweisen geben. Danke an RealMurph und abooij.

verbergen