Sudoku Blank Grid wird in der Symmetrie von Sudoku verwendet,Es umfasst Zeilen und Spalten von 4 × 4,16 × 16 und mehr mit kleinen und varianten Gittern.

Sudoku-Rätsel können mathematisch studiert werden, um Fragen wie zu beantworten “Wie viele volle Sudoku-Gitter?”, “Was ist die Mindestanzahl an Hinweisen in einem echten Puzzle??” und “Wie können Sudoku-Gitter symmetrisch sein??” durch kombinatorische und Gruppentheorien.

Die Hauptergebnisse sind die für klassisches Sudoku, Die Anzahl der abgeschlossenen Gitter beträgt 6,670,903,752,021,072,936,960 (6.67× 1021), welche, unter Beibehaltung der Gültigkeit der Transformation reduziert sich auf 5,472,730,538 signifikant unterschiedliche Gruppen.

Es gibt 26 Arten von Symmetrie, aber sie können nur in ungefähr gefunden werden 0.005% aller gefüllten Gitter.

Ein Puzzle mit einer einzigartigen Lösung muss mindestens haben 17 Lösungen, und für jedes gelöste Gitter gibt es nicht mehr als 21 Lösungen. Das größte Minimum gefundenes Puzzle hat 40 Hinweise.

Ähnliche Ergebnisse sind für Varianten und kleinere Gitter bekannt. Genaue Ergebnisse sind für Sudokus nicht mehr bekannt als für das klassische 9 × 9-Raster, obwohl es Schätzungen gibt, die als ziemlich genau angesehen werden.

Berechnungslösungen für Sudoku

Eine interessante Frage ist, Wie viele Möglichkeiten kann ein 9 durch 9 Das Sudoku-Gitter muss gefüllt werden, um die Einzelregel zu erfüllen?

Mit anderen Worten, Wie viele verschiedene Sudoku-Lösungen gibt es?? Wir beschreiben die Methode von Bertram Felgenhauer und Fraser Jarvis früh 2006 um diese Zahl zu berechnen.

Den Standard unserer Sprache beibehalten, Wir nennen drei Reihen von Blockstreifen eines Gitters und drei Spalten von Blockstapeln. Eine Zelle in dieser Zeile und in der j-Spalte befindet sich in (ich,j).

Wir nennen die Anzahl der einzelnen Gitter Sudoku N.. Zuerst, Wir nennen die Gitterblöcke wie folgt:

Wie viele Möglichkeiten gibt es, um B1 auf gültige Weise zu füllen?? Weil dort sind 9 Zeichen, die B1 füllen können, eine in jeder Zelle, das ist 9 Optionen für die erste Zelle.

Für jeden von diesen 9 Optionen, es gibt 8 Optionen für die zweite Zelle. Für jeden von diesen 8 Optionen, es gibt 7 links für die dritte Zelle.

Grundsätzlich gilt, Wir berechnen die Anzahl der Permutationen von 9 Figuren: wie viele Möglichkeiten können wir platzieren 9 Zeichen in 9 setzt, oder wie viele Möglichkeiten wir bestellen können 9 Dinge.

Es gibt 9 Möglichkeiten zum Ausfüllen von B1. Beginnend mit einem gültigen B1-Block, Wir können jeden anderen gültigen B1-Block erhalten, indem wir die Nummern neu markieren oder neu anordnen.

So, Die erste vereinfachende Annahme, die wir machen können, ist, dass B1 mit Zahlen gefüllt ist 1, 2, 3, …, 9 in Ordnung, Wie nachfolgend dargestellt.

Jetzt können wir berechnen, wie viele tatsächliche Gitterenden diese bestimmte B1 hat: Nennen wir es N1. Die Gesamtzahl der tatsächlichen Sudoku-Gitter beträgt N1 × 9!, also N1 = N / 9!…

Betrachten wir die Möglichkeiten, die ersten Zeilen in B2 und B3 zu füllen. Schon seit 1, 2 und 3 treten in der ersten Zeile in B1 auf, Diese Zahlen können in den anderen Zeilen nicht vorkommen.

Deshalb, nur die Zahlen 4, 5, 6, 7, 8 und 9 aus der zweiten und dritten Reihe von B1 können sich in der ersten Reihe in B2 und B3 treffen.

Listen Sie alle möglichen Möglichkeiten auf, um die ersten Zeilen in B2 und B3 zu füllen, bis zur Neuanordnung der Nummern in jedem Block. Trinkgeld: Es gibt zehn Möglichkeiten, dies zu tun, so dass der Austausch von B2 und B3 diese zehn Möglichkeiten Ihnen zehn weitere Möglichkeiten gab, insgesamt zwanzig.

Wir nennen zwei dieser Möglichkeiten reine Toplines: wenn Zahlen {4,5,6}, wie in der zweiten Reihe von B1, werden zusammen in B2 gespeichert, und Zahlen {7,8,9}, wie in der dritten Reihe von B1, werden zusammen in B3 gespeichert, und eine geänderte Version davon.

Die anderen Möglichkeiten sind gemischte Toplines, wie sie die Sets mischen {4,5,6} und {7,8,9} wenn verwendet, um die ersten Zeilen von B2 und B3 zu füllen.

Angesichts dieser zwanzig Möglichkeiten für die erste Zeile des Gitters (bis zur Neuanordnung der Nummern in jedem Block), Wir können herausfinden, wie die erste Zeile gefüllt wird.

Überlegen Sie, wie Sie die erste Band ab der reinen oberen Reihe abschließen können 1,2,3;{4,5,6};{7,8,9}.

(Hinweis: Wir schreiben a,b,c, um ein geordnetes Dreifach von Zahlen zu bezeichnen und {ein,b,c} sie in beliebiger Reihenfolge zu bezeichnen.)

Wie viele Möglichkeiten gibt es insgesamt?, Zählen unterschiedlicher Nummernreihenfolgen innerhalb jeder Zeile in B2 und B3? Ist diese Nummer dieselbe wie für die andere reine obere Reihe?, 1,2,3;{7,8,9};{4,5,6}?

Merken, Wir möchten B1 beibehalten, da wir bereits die Anzahl der Gitter berücksichtigt haben, die durch erneutes Beschriften der neun Ziffern erhalten werden können.

Es stellt sich heraus, dass es gibt (3!)⁶ Möglichkeiten, das erste Band mit der reinen oberen Reihe zu vervollständigen 1,2,3;{4,5,6};{7,8,9}.

Das liegt daran, dass wir gezwungen sind zu setzen {7,8,9};{1,2,3} in der zweiten Reihe in B2 und B3 und {1,2,3};{4,5,6} in der dritten Reihe, und dann können wir die drei Ziffern in jeder der sechs Zeilen von B2 und B3 neu anordnen, um alle Konfigurationen zu erhalten.

Die Antwort ist die gleiche für die andere reine obere Reihe, da wir in diesem Fall nur B2 gegen B3 getauscht haben.

Die Fälle der gemischten oberen Reihen sind komplizierter. Betrachten wir die oberste Reihe 1,2,3;{4,6,8};{5,7,9}. Dies kann bis zum ersten Band wie im folgenden Bild abgeschlossen werden, wo ein, b, und c sind die Zahlen 1, 2, 3 In irgendeiner Reihenfolge.

Nach Auswahl von a, b und c sind die beiden verbleibenden Zahlen in beliebiger Reihenfolge, wie sie in der gleichen Reihe sind.

Da gibt es drei Möglichkeiten für a, und drei Ziffern in jedem der sechs Sätze in B2 und B3 können übersprungen werden, um verschiedene gültige Titelseiten zu erhalten, Die Gesamtzahl der Konfigurationen beträgt in diesem Fall 3 ×(3!)6.

Sie können in ähnlicher Weise jeden der verbleibenden siebzehn Fälle in der ersten Reihe durcharbeiten, um dieselbe Nummer zu erhalten.

Jetzt haben wir die Anzahl der möglichen Titelseiten, die durch B1 definiert sind: das ist 2 ×(3!)6+18× 3 ×(3!)6= 2612736, Dabei ist der erste Teil der Summe die Anzahl der ersten Seitenabschlüsse aus den oberen Nettozeilen und der zweite die Anzahl der ersten Seitenabschlüsse aus den gemischten oberen Zeilen.

Anstatt zu berechnen, wie viele Titelseiten jeweils fertiggestellt wurden 2612736 Eigenschaften, Felgenhauer und Jarvis haben aus dem oberen Feld ermittelt, welche Titelseiten die gleiche Anzahl von Erstseitenvervollständigungen aufweisen.

Diese Analyse reduziert die Anzahl der Titelseiten, die bei der Berechnung berücksichtigt werden müssen.

Hier sind einige Operationen, bei denen die Anzahl der Endungen des ersten Bereichsgitters unverändert bleibt: Bemerkung der Zahlen, Hören Sie sich einen der Blöcke im ersten Bereich an, Hören Sie sich die Spalten in einem beliebigen Block an und hören Sie sich die drei Zeilen des Bereichs an. Bei jeder dieser B1-Änderungen, Wir können die Zahlen neu markieren, um ihre Standardform wiederherzustellen.

B1 arrangieren, B2 und B3 behalten die Anzahl der Gitterenden bei, denn wenn wir mit einem tatsächlichen Sudoku-Gitter beginnen, Die einzige Möglichkeit, es real zu halten, besteht darin, B4 zu markieren, B5, B6 und B7, B8, B9 jeweils so, dass die Stapel gleich bleiben.

Mit anderen Worten, Jede tatsächliche Beendigung des Titelseitenrasters ergibt genau eine tatsächliche Beendigung des Titelseitenrasters, d.h.. beliebiges B1, B2, B3-Permutation.
Stellen Sie sicher, dass, wenn Sie B2 in B3 im nächsten Sudoko-Raster ändern, Die einzige Möglichkeit, das Raster gültig zu halten, besteht darin, B5 in B6 und B7 in B8 zu ändern. Dadurch bleiben die Stapel gleich, obwohl sich ihr Standort geändert hat.

Wenn Sie ein gültiges Sudoku-Raster haben und Spalten in einem der B1 überspringen, B2 und B3, Was müssten Sie mit den Spalten des restlichen Sudoku-Gitters tun, um es gültig zu halten?? Beispielsweise, wenn Sie Spalten geändert haben 1 und 2 von B2 im obigen Raster, Wie würden Sie das resultierende Raster so reparieren, dass es der Einen Regel entspricht??

Die letzte Übung zeigt uns, dass jede Füllung des Rasters der ersten Reihe eine eindeutige Füllung des Rasters der ersten Reihe mit Spalten ergibt, die innerhalb der Blöcke übersprungen werden.

Solche Überlegungen ermöglichen es uns, die Anzahl bestimmter Titelseiten zu reduzieren, die beim Zählen berücksichtigt werden müssen.

Nach Felgenhauer und Jarvis, Wir scrollen durch die Spalten B2 und B3, sodass die obersten Zeileneinträge jeder Spalte in aufsteigender Reihenfolge angezeigt werden, und tauschen Sie dann gegebenenfalls B2 und B3 aus, sodass der erste B2-Eintrag kleiner als der B3-Eintrag ist.

Dies wird als lexikografische Abkürzung bezeichnet.

Da hat jeder der beiden Blöcke 6 Neuanordnungen von Säulen und zwei Möglichkeiten zum Umordnen von Blöcken, Die lexikografische Kurzschrift sagt uns das, gegeben die erste Seite, Es gibt 62 × 2 = 72 andere Titelseiten mit der gleichen Anzahl von Rasterenden.

Jetzt müssen wir nur noch 2612736/72 = 36288 Titelseiten berücksichtigen.

Schauen wir uns für jede dieser Möglichkeiten die Umlagerungen aller drei oberen Blöcke an: es gibt 6. Für jeden von ihnen gibt es 63 Neuanordnungen von Spalten innerhalb jedes Blocks.

Nach dem Ausführen dieser Operationen, Wir markieren erneut, um B1 in seine Standardform zurückzubringen.

Ähnlich, Wir können die obersten drei Zeilen der Gruppe überschreiben und neu markieren, um B1 zu einem Standardformular zurückzukehren. Diese Vorgänge speichern die Anzahl der Rasterabschlüsse in der ersten Reihe.

Felgenhauer und Jarvis verwendeten ein Computerprogramm, um festzustellen, dass diese Vorgänge die Anzahl der zu berücksichtigenden Titelseiten verringern 36288 nur zu 416.

Betrachten wir diese erste Gruppe.

Führen Sie verschiedene Vorgänge aus, um die Anzahl der Rasterenden zu speichern. Sie können mit folgendem beginnen: Tauschen Sie die erste und zweite Zeile aus. Markieren Sie es erneut, sodass B1 in seiner Standardform vorliegt. Reduzieren Sie dieses Raster lexikografisch.

Die Hauptsache ist, dass die Gruppe, mit der Sie begonnen haben, und die andere Gruppe, mit der Sie fertig waren, die gleiche Anzahl von Abschlüssen bis zum vollständigen Sudoku-Raster haben.

Somit, anstatt die Anzahl der Enden des Gitters für jede dieser Gruppen zu berechnen, wir können es nur für einen von ihnen berechnen.

Es gibt weitere Schritte, mit denen die Anzahl der zu berücksichtigenden Raster verringert wird. Wenn wir zwei Ziffern haben {ein,b} in einer Spalte mit a in einer i-ten Reihe und b in einer j-ten Reihe, und das gleiche Paar in einer anderen Spalte mit b in einer i-ten Reihe und a in einer j-ten Reihe, Jedes Paar hat ein Band mit der gleichen Anzahl von Gitterenden wie das Original.

Dies liegt daran, dass jedes Paar in derselben Spalte liegt, und wenn beide gleichzeitig geändert werden, eine einzelne Regel wird gespeichert, was auch die beteiligten Zeilen erfüllt.

Als Beispiel, schau dir Zahlen an 8 und 9 in der sechsten und neunten Spalte des obigen Beispiels. Betrachten Sie alle möglichen Fälle dieser linken Felgenhauer und Jarvis mit 174 des ersten 416 Gruppen, mit denen Sie fortfahren können.

Sie haben auch andere Konfigurationen desselben Satzes von Zahlen in Betracht gezogen, die in zwei verschiedenen Spalten oder Zeilen liegen, die in ihren Spalten oder Zeilen weggelassen werden können, Die Anzahl der Gitterenden bleibt unverändert.

Dies reduzierte die Anzahl der Titelseiten auf 71, und die Suche nach jedem von diesen 71 Fälle machten ihnen klar, dass es tatsächlich nur gibt 44 Titelseiten, deren Anzahl der Rastervervollständigungen gefunden werden kann.

Jedes von diesen 44 Bands hat die gleiche Anzahl von Endungen zum vollen Gitter.

C bezeichne eine davon 44 Streifen. Anschließend können Sie die Anzahl der Möglichkeiten berechnen, die C zum vollständigen Sudoku-Raster ausführen kann: nenne es nc.

Wir benötigen auch die Anzahl der mC-Titelseiten, die diese Anzahl der nC-Endungen des Rasters gemeinsam nutzen. Dann, Die Gesamtzahl der Sudoku-Gitter beträgt nur N = ΣCmCnC, oder die Summe von mCnC für alle 44 Streifen.

Felgenhauer und Jarvis haben ein Computerprogramm geschrieben, um die endgültigen Berechnungen durchzuführen.

Sie berechneten die Anzahl der N1 gültigen Abschlüsse mit B1 in einer Standardform, beginnen mit 44 Fahrspuren. Dann multiplizierten sie diese Zahl mit 9! um eine Antwort zu bekommen.

Sie fanden heraus, dass die Anzahl der möglichen 9 durch 9 Sudoku-Raster ist N=6670903752021072936960, das ist ungefähr 6,671 × 1021.

Artikel- und Bildnachweis:

http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html