Mathematik des Sudoku - Mathematics of Sudoku

Ein automorphes Sudoku mit 24 Hinweisen und Translationssymmetrie

Sudoku- Rätsel können mathematisch studiert werden , um Fragen wie "Wie viele gefüllte Sudoku-Gitter gibt es?" zu beantworten. , " Was ist die minimale Anzahl von Hinweisen in einem gültigen Puzzle? " und "Inwiefern können Sudoku-Gitter symmetrisch sein?" durch den Einsatz von Kombinatorik und Gruppentheorie .

Die wichtigsten Ergebnisse sind, dass für das klassische Sudoku die Anzahl der gefüllten Gitter 6.670.903.752.021.072.936.960 (6,67 × 10 ²¹ ), was sich auf 5.472.730.538 im Wesentlichen unterschiedliche Gruppen unter den gültigkeitserhaltenden Transformationen reduziert . Es gibt 26 Symmetrietypen, die jedoch nur in etwa 0,005% aller gefüllten Raster zu finden sind. Ein Rätsel mit einer eindeutigen Lösung muss mindestens 17 Hinweise enthalten, und für jedes gelöste Raster gibt es ein lösbares Rätsel mit höchstens 21 Hinweisen. Das größte bisher gefundene minimale Puzzle hat 40 Hinweise.

Ähnliche Ergebnisse sind für Varianten und kleinere Raster bekannt. Für Sudokus, die größer als das klassische 9×9-Raster sind, sind keine genauen Ergebnisse bekannt, obwohl es Schätzungen gibt, von denen angenommen wird, dass sie ziemlich genau sind.

Überblick

Die Analyse von Sudoku gliedert sich in zwei Hauptbereiche:

Analyse der Eigenschaften fertiger Gitter
Analysieren der Eigenschaften abgeschlossener Puzzles.

Die anfängliche Analyse konzentrierte sich hauptsächlich auf die Aufzählung von Lösungen, wobei die Ergebnisse erstmals im Jahr 2004 erschienen.

Es gibt viele Sudoku-Varianten , die teilweise durch die Größe ( N ) und die Form ihrer Regionen gekennzeichnet sind . Sofern nicht anders angegeben, geht die Diskussion in diesem Artikel vom klassischen Sudoku aus, dh N = 9 (ein 9×9-Gitter und 3×3-Regionen). Ein rechteckiges Sudoku verwendet rechteckige Bereiche der Reihen-Spalten-Dimension R × C . Andere Varianten sind solche mit unregelmäßig geformten Regionen oder mit zusätzlichen Beschränkungen ( Hypercube ) oder anderen Beschränkungstypen ( Samunamupure ).

Regionen werden auch Blöcke oder Boxen genannt . Ein Band ist ein Teil des Rasters, das 3 Zeilen und 3 Kästchen umschließt, und ein Stapel ist ein Teil des Rasters, das 3 Spalten und 3 Kästchen umschließt. Ein Puzzle ist ein teilweise ausgefülltes Raster , und die Anfangswerte sind Angaben oder Hinweise . Ein richtiges Puzzle hat eine einzigartige Lösung. Ein minimales Puzzle ist ein richtiges Puzzle, aus dem kein Hinweis entfernt werden kann, ohne zusätzliche Lösungen einzuführen. Weitere Terminologie finden Sie im Glossar von Sudoku .

Das Lösen von Sudokus aus der Sicht eines Spielers wurde in Denis Berthiers Buch "The Hidden Logic of Sudoku" (2007) untersucht, das Strategien wie "versteckte xy-Ketten" betrachtet.

Mathematischer Kontext

Das allgemeine Problem des Lösens von Sudoku-Rätseln auf n ² × n ² Gittern von n × n Blöcken ist als NP-vollständig bekannt . Für n = 3 (klassisches Sudoku) ist dieses Ergebnis jedoch von geringer praktischer Relevanz: Algorithmen können aufgrund der geringen Größe des Problems Rätsel in Bruchteilen einer Sekunde lösen.

Ein Puzzle kann als ein Diagrammfarbproblem ausgedrückt werden . Ziel ist es, eine 9-Färbung eines bestimmten Graphen zu konstruieren, wenn eine partielle 9-Färbung gegeben ist. Der Sudoku-Graph hat 81 Scheitelpunkte, einen Scheitelpunkt für jede Zelle. Die Scheitelpunkte sind mit geordneten Paaren ( x , y ) gekennzeichnet, wobei x und y ganze Zahlen zwischen 1 und 9 sind. In diesem Fall werden zwei verschiedene Scheitelpunkte, die mit ( x , y ) und ( x ′, y ′) gekennzeichnet sind, durch an . verbunden Kante genau dann, wenn :

x = x ′ (gleiche Spalte) oder,
y = y ′ (gleiche Reihe) oder,
⌈ x /3 ⌉ = ⌈ x ′/3 ⌉ und ⌈ y /3 ⌉ = ⌈ y ′/3 ⌉ (gleiche 3×3-Zelle)

Das Puzzle wird dann vervollständigt, indem jedem Scheitelpunkt eine ganze Zahl zwischen 1 und 9 zugewiesen wird, sodass Scheitelpunkten, die durch eine Kante verbunden sind, nicht dieselbe ganze Zahl zugewiesen ist.

Ein Sudoku-Lösungsraster ist auch ein lateinisches Quadrat . Es gibt deutlich weniger Sudoku-Gitter als lateinische Quadrate, da Sudoku die zusätzliche regionale Einschränkung auferlegt.

Sudokus von Gruppentischen

Wie bei den lateinischen Quadraten können die (Additions- oder) Multiplikationstafeln ( Cayleytafeln ) endlicher Gruppen verwendet werden, um Sudokus und verwandte Zahlentafeln zu konstruieren. Es sind nämlich Untergruppen und Quotientengruppen zu berücksichtigen:

Nehmen Sie zum Beispiel die Gruppe von Paaren, wobei jede Komponente separat modulo some hinzugefügt wird . Durch Weglassen einer der Komponenten befinden wir uns plötzlich in (und diese Abbildung ist offensichtlich mit den jeweiligen Ergänzungen kompatibel, dh es handelt sich um einen Gruppenhomomorphismus ). Man sagt auch, dass die letztere eine Quotientengruppe der ersteren ist, weil einige einst verschiedene Elemente in der neuen Gruppe gleich werden. Es ist jedoch auch eine Untergruppe, da wir die fehlende Komponente einfach mit füllen können , um zurück zu . $\mathbb{Z}_{n}\oplus\mathbb{Z}_{n}$ $n$ $\mathbb{Z} _{n}$ $0$ $\mathbb{Z}_{n}\oplus\mathbb{Z}_{n}$

Unter dieser Ansicht schreiben wir das Beispiel Grid 1 für auf . $n=3$

Jede Sudoku-Region sieht auf der zweiten Komponente (nämlich wie die Untergruppe ) gleich aus, da diese unabhängig von der ersten hinzugefügt werden. Andererseits sind die ersten Komponenten in jedem Block gleich, und wenn wir uns jeden Block als eine Zelle vorstellen, zeigen diese ersten Komponenten das gleiche Muster (nämlich die Quotientengruppe ). Wie im Artikel der lateinischen Quadrate beschrieben, ist dies ein lateinisches Ordnungsquadrat . $\mathbb{Z}_{3}$ $\mathbb{Z}_{3}$ $9$

Um nun ein Sudoku zu erhalten, permutieren wir die Zeilen (oder äquivalent die Spalten) so, dass jeder Block genau einmal in jeden Block umverteilt wird – zum Beispiel ordnen . Dadurch bleibt natürlich das lateinische Quadrat erhalten. Darüber hinaus haben die Zeilen in jedem Block konstruktionsbedingt eine unterschiedliche erste Komponente und jede Zeile in einem Block hat unterschiedliche Eingänge über die zweite Komponente, da die zweiten Komponenten der Blöcke ursprünglich ein lateinisches Ordnungsquadrat (aus der Untergruppe ) bildeten. So kommen wir zu einem Sudoku (benennen Sie die Paare auf Wunsch in Zahlen 1...9 um). Mit dem obigen Beispiel und der Zeilenpermutation gelangen wir zu Grid 2 . $1,4,7,2,5,8,3,6,9$ $3$ $\mathbb{Z}_{3}$

Raster 1 – Die Additionstabelle in

\mathbb{Z}_{3}\oplus\mathbb{Z}_{3}

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(2,0)	(2,1)	(2,2)
(2,1)	(2,2)	(2,0)
(2,2)	(2,0)	(2,1)

(0,0)	(0,1)	(0,2)
(0,1)	(0,2)	(0,0)
(0,2)	(0,0)	(0,1)

(1,0)	(1,1)	(1,2)
(1,1)	(1,2)	(1,0)
(1,2)	(1,0)	(1,1)

Raster 2 – Generieren eines Sudoku

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)
(0,0)	(0,1)	(0,2)

(2,0)	(2,1)	(2,2)
(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)

(0,1)	(0,2)	(0,0)
(1,1)	(1,2)	(1,0)
(2,1)	(2,2)	(2,0)

(1,1)	(1,2)	(1,0)
(2,1)	(2,2)	(2,0)
(0,1)	(0,2)	(0,0)

(2,1)	(2,2)	(2,0)
(0,1)	(0,2)	(0,0)
(1,1)	(1,2)	(1,0)

(0,2)	(0,0)	(0,1)
(1,2)	(1,0)	(1,1)
(2,2)	(2,0)	(2,1)

(1,2)	(1,0)	(1,1)
(2,2)	(2,0)	(2,1)
(0,2)	(0,0)	(0,1)

(2,2)	(2,0)	(2,1)
(0,2)	(0,0)	(0,1)
(1,2)	(1,0)	(1,1)

Damit diese Methode funktioniert, braucht man in der Regel kein Produkt aus zwei gleich großen Gruppen. Eine sogenannte kurze exakte Folge endlicher Gruppen entsprechender Größe erledigt bereits die Arbeit. Versuchen Sie zum Beispiel die Gruppe mit Quotienten- und Untergruppe . Es scheint klar (schon aus Aufzählungsargumenten), dass nicht alle Sudokus auf diese Weise erzeugt werden können. $\mathbb{Z}_{4}$ $\mathbb {Z} _{2}$

Varianten

Ein Sudoku kann als Kacheln (oder Abdeckung ) eines lateinischen Quadrats mit Polyominos (den Regionen des Sudoku) interpretiert werden . Das klassische 9×9-Sudoku besteht aus quadratischen Nonominoes . Es ist möglich, die Sudoku-Regeln auf Puzzles anderer Größen anzuwenden, obwohl nur N ² × N ² Sudoku-Puzzles mit quadratischen Polyominos gekachelt werden können.

Eine erweiterte Liste der Varianten finden Sie im Glossar von Sudoku .

Rechteckige Bereiche

Eine beliebte Variante sind rechteckige Bereiche ( Blöcke oder Kästen ) – zum Beispiel 2×3 Hexominos, die in einem 6×6-Raster gekachelt sind. Zur Diskussion dieser Variante wird folgende Notation verwendet:

R × C bezeichnet einen rechteckigen Bereich mit R Reihen und C Spalten.
Die implizierte Rasterkonfiguration hat:
- Rastermaß N × N , wobei N = R × C
- N Blöcke ( Boxen ) der Größe R × C , angeordnet in einem C × R 'Supergrid'
- C Bänder der Größe R × N , bestehend aus R horizontal benachbarten Blöcken
- R Stapel der Größe N × C , bestehend aus C vertikal benachbarten Blöcken

Sudoku mit quadratischen N × N Regionen sind symmetrischer als rechteckige Sudoku, da jede Zeile und Spalte N Regionen schneidet und N Zellen mit jeder teilt . Die Anzahl der Bänder und Stapeln auch gleich N . Das "3×3"-Sudoku ist zusätzlich einzigartig: N ist auch die Anzahl der Zeilen-Spalten-Region-Beschränkungen aus der Einen Regel (dh es gibt N = 3 Arten von Einheiten ).

Puzzle-Sudokus

Ein Sudoku, dessen Regionen nicht (notwendigerweise) quadratisch oder rechteckig sind, wird als Jigsaw Sudoku bezeichnet. Insbesondere kann ein N × N- Quadrat, bei dem N eine Primzahl ist, nur mit unregelmäßigen N- Ominos belegt werden . Für kleine Werte von N wurde die Anzahl der Möglichkeiten zum Kacheln des Quadrats (ohne Symmetrien) berechnet (Sequenz A172477 im OEIS ). Für N ≥ 4 sind einige dieser Kacheln mit keinem lateinischen Quadrat kompatibel; dh alle Sudoku-Rätsel auf einer solchen Kachel haben keine Lösung.

Lösungen

Die Antwort auf die Frage 'Wie viele Sudoku-Gitter gibt es?' hängt von der Definition ab, wann ähnliche Lösungen als unterschiedlich angesehen werden.

Gewöhnliches Sudoku

Alle Lösungen

Für die Aufzählung aller möglichen Lösungen werden zwei Lösungen als unterschiedlich betrachtet, wenn sich einer ihrer entsprechenden (81) Zellenwerte unterscheidet. Symmetriebeziehungen zwischen ähnlichen Lösungen werden ignoriert, zB werden die Drehungen einer Lösung als verschieden angesehen. Symmetrien spielen bei der Aufzählungsstrategie eine bedeutende Rolle, jedoch nicht bei der Zählung aller möglichen Lösungen.

Die erste bekannte Lösung zur vollständigen Aufzählung wurde 2003 von QSCGZ (Günter Stertenbrink) in der rec.puzzles- Newsgroup veröffentlicht und erhielt 6.670.903.752.021.072.936.960 (6,67 × 10 ²¹ ) verschiedene Lösungen.

In einer Studie aus dem Jahr 2005 analysierten Felgenhauer und Jarvis die Permutationen des oberen Bandes, die in gültigen Lösungen verwendet wurden. Nachdem die Band1- Symmetrien und Äquivalenzklassen für die Teilgitterlösungen identifiziert waren, wurden die Vervollständigungen der unteren beiden Bänder konstruiert und für jede Äquivalenzklasse gezählt. Durch Summieren der Vervollständigungen über die Äquivalenzklassen, gewichtet nach Klassengröße, ergibt sich die Gesamtzahl der Lösungen von 6.670.903.752.021.072.936.960, was den von QSCGZ ermittelten Wert bestätigt. Der Wert wurde anschließend unabhängig voneinander mehrfach bestätigt. Später wurde eine zweite Aufzählungstechnik basierend auf der Bandgenerierung entwickelt, die deutlich weniger rechenintensiv ist. Diese nachfolgende Technik führte dazu, dass ungefähr 1/97 der Anzahl von Rechenzyklen als die ursprünglichen Techniken benötigt wurden, war jedoch wesentlich komplizierter einzurichten.

Grundsätzlich andere Lösungen

Gültigkeitserhaltende Transformationen

Zwei gültige Gitter sind im Wesentlichen gleich, wenn eines aus dem anderen abgeleitet werden kann, indem eine sogenannte Gültigkeitserhaltungstransformation (VPT) verwendet wird . Diese Transformationen transformieren immer ein gültiges Gitter in ein anderes gültiges Gitter. Es gibt zwei Haupttypen: Symbolpermutationen (Relabeling) und Zellpermutationen (Rearrangements). Sie sind:

Relabeling-Symbole (9!)
(Sobald alle möglichen Relabeling-Kombinationen eliminiert sind, bis auf eine: Wenn man beispielsweise die oberste Reihe auf [123456789] festhält, reduziert sich die Anzahl der festen Raster auf 18.383.222.420.692.992. Dieser Wert ist 6.670.903.752.021.072.936.960 geteilt durch 9!)

und neu anordnen (mischen):

Bandpermutationen (3!)
Zeilenpermutationen innerhalb eines Bandes (3!×3!×3!)
Stapel-Permutationen (3!)
Spaltenpermutationen innerhalb eines Stapels (3!×3!×3!)
Spiegelung, Transposition und Drehung (2)
(Bei einer einzigen Transposition oder Vierteldrehung in Verbindung mit den obigen Permutationen kann jede Kombination von Spiegelungen, Transpositionen und Drehungen erzeugt werden, so dass diese Operationen nur einen Faktor von 2 beitragen)

Diese Operationen definieren eine Beziehung zwischen äquivalenten Gittern. Bezüglich der 81 Gitterzellenwerte bilden die Umordnungsoperationen eine Untergruppe der symmetrischen Gruppe S ₈₁ , der Ordnung 3! ⁸ × 2 = 3.359.232. Die Umetikettierungsoperationen sind isomorph mit S ₉ und erzeugen eine zusätzliche 9! = 362.880 äquivalente Gitter. Die Anwendung dieser Operationen auf ein Gitter ergibt 3! ⁸ ×2×9! oder 1.218.998.108.160 im Wesentlichen äquivalente Raster. Es gibt jedoch eine kleine Anzahl von Sudokus, für die die obigen Operationen weniger Gitter erzeugen; Dies sind die selbstähnlichen oder automorphen Sudokus . Nur etwa 0,01% aller im Wesentlichen einzigartigen Gitter sind automorph, aber das Zählen ist notwendig, um die genaue Anzahl von im Wesentlichen unterschiedlichen Sudokus zu bewerten.

Die Sudoku-Symmetriegruppe

Die genaue Struktur der sudoku Symmetriegruppe kann kurz und bündig die Verwendung ausgedrückt wird Kranz Produkt (≀). Die möglichen Zeilen- (oder Spalten-) Permutationen bilden eine zu S ₃ ≀ S ₃ der Ordnung 3 isomorphe Gruppe ! ⁴ = 1.296. Die gesamte Umordnungsgruppe wird gebildet, indem die Transpositionsoperation (isomorph zu C ₂ ) auf zwei Kopien dieser Gruppe wirken lässt, eine für die Zeilenpermutationen und eine für die Spaltenpermutationen. Dies ist S ₃ ≀ S ₃ ≀ C ₂ , eine Gruppe der Ordnung 1.296 ² × 2 = 3.359.232. Schließlich kommutieren die Umetikettierungsoperationen mit den Umordnungsoperationen, sodass die vollständige Sudoku-(VPT)-Gruppe ( S ₃ ≀ S ₃ ≀ C ₂ ) × S ₉ der Ordnung 1.218.998.108.160 ist.

Fixpunkte und Burnsides Lemma

Die Menge äquivalenter Rastern , die erreicht werden können , diese Vorgänge unter Verwendung (ohne Relabeln) eine Umlaufbahn von Gittern unter der Wirkung der Umordnung Gruppe . Die Anzahl der wesentlich unterschiedlichen Lösungen ist dann die Anzahl der Umlaufbahnen, die mit dem Lemma von Burnside berechnet werden kann . Die Fixpunkte von Burnside sind Raster, die sich bei der Neuordnung entweder nicht ändern oder sich nur durch Umbenennung unterscheiden. Zur Vereinfachung der Berechnung werden die Elemente der Umordnungsgruppe in Konjugationsklassen einsortiert , deren Elemente alle die gleiche Anzahl von Fixpunkten haben. Es stellte sich heraus, dass nur 27 der 275 Konjugationsklassen der Umlagerungsgruppe Fixpunkte haben; Diese Konjugationsklassen repräsentieren die verschiedenen Symmetrietypen (Selbstähnlichkeit oder Automorphismus), die in abgeschlossenen Sudoku-Gittern zu finden sind. Mit dieser Technik waren Ed Russell und Frazer Jarvis die ersten, die die Anzahl der im Wesentlichen unterschiedlichen Sudoku-Lösungen mit 5.472.730.538 berechneten .

Konjugationsklassen der Umlagerungsgruppe mit Fixpunkten ("Automorphismen" und ihre Prävalenz)
Name oder Zusammensetzung	Code	Klasse Id.	Klassengröße	Zellzyklen	Ö	F	Anzahl Fixraster (bis Umetikettierung), pro Element	Anzahl der festen Gitter, pro Element	Anzahl Fixraster (bis Umetikettierung), ganze Klasse	Anzahl der festen Gitter, ganze Klasse
Identität	e	1	1		1	81	18.383.222.420.692.992	6.670.903.752.021.072.936.960	18.383.222.420.692.992	6.670.903.752.021.072.936.960
Minireihen (MR)	ccc	8	16	27×3	3	0	107.495.424	39.007.939.461.120	1.719.926.784	624.127.031.377.920
2 MR, 1 MD	ccc \| C	7	96	27×3	3	0	21.233.664	7.705.271.992.320	2.038.431.744	739.706.111.262.720
1 MR, 2 MD	ccc \| cc	9	192	27×3	3	0	4,204,224	1.525.628.805.120	807.211.008	292.920.730.583.040
Minidiagonalen (MD)	ccc \| ccc	10	64	27×3	3	0	2.508.084	910.133.521.920	160.517.376	58.248.545.402.880
Springende Reihen (JR)	C	25	144	27×3	3	0	14.837.760	5.384.326.348.800	2.136.637.440	775.342.994.227.200
2 JR, 1 GR	C \| C	28	864	27×3	3	0	2.085.120	756.648.345.600	1.801.543.680	653.744.170.598.400
1 JR, 2 GR	C \| cc	30	1.728	27×3	3	0	294.912	107.017.666.560	509.607.936	184.926.527.815.680
Gleitreihen (GR)	C \| ccc	32	1.152	27×3	3	0	6.342.480	2.301.559.142.400	7.306.536.960	2.651.396.132.044.800
Vollständige Reihen (FR)	C9	27	288	9×9	9	0	5.184	1.881.169.920	1.492.992	541.776.936.960
2 FR, 1 WR	C9 \| C	26	1.728	9×9	9	0	2.592	940.584.960	4.478.976	1.625.330.810.880
1 FR, 2 WR	C9 \| cc	29	3.456	9×9	9	0	1.296	470.292.480	4.478.976	1.625.330.810.880
Winkende Reihen (WR)	C9 \| ccc	31	2.304	9×9	9	0	648	235.146.240	1.492.992	541.776.936.960
Sprungdiagonalen (JD)	C \| C	22	5.184	27×3	3	0	323.928	117.546.992.640	1.679.242.752	609.363.609.845.760
Gebrochene Spalten (BC)	C \| C9	24	20.736	9×9	9	0	288	104.509.440	5.971.968	2.167.107.747.840
Volle Diagonalen (FD)	C9 \| C9	23	20.736	9×9	9	0	162	58.786.560	3.359.232	1.218.998.108.160
Diagonalspiegel (DM)	T	37	1.296	36×2	2	9	30.258.432	10.980.179.804.160	39.214.927.872	14.230.313.026.191.360
DM+MD	T ccc	40	10,368	3×3, 12×6	6	0	1.854	672.779.520	19.222.272	6.975.378.063.360
DM+JD	TC	43	93.312	3×3, 12×6	6	0	288	104.509.440	26.873.856	9.751.984.865.280
Vierteldrehung (QT)	T sS	86	69.984	20×4	4	1	13.056	4.737.761.280	913.711.104	331.567.485.419.520
Halbe Drehung (HT)	sS \| sS	79	2.916	40×2	2	1	155.492.352	56.425.064.693.760	453.415.698.432	164.535.488.647.004.160
Säulensticks (CS)	S \| sss	134	972	36×2	2	9	449.445.888	163.094.923.837.440	436.861.403.136	158.528.265.969.991.680
CS+MC	cS6 \| sss	135	3.888	3×3, 12×6	6	0	27.648	10.032.906.240	107.495.424	39.007.939.461.120
CS+GR	cS6 \| C6	142	31.104	3×3, 12×6	6	0	6.480	2.351.462.400	201.553.920	73.139.886.489.600
CS+ JR/B2,GR/B13	S6 \| C6	143	15.552	3×3, 12×6	6	0	1.728	627.056.640	26.873.856	9.751.984.865.280
CS+ GR/Band2,JR/B13	cS \| C6	144	15.552	3×3, 12×6	6	0	3.456	1.254.113.280	53.747.712	19.503.969.730.560
CS+JR	S \| C6	145	7.776	3×3, 12×6	6	0	13.824	5.016.453.120	107.495.424	39.007.939.461.120
(nicht trivial)									949.129.933.824	344.420.270.386.053.120
gesamt									18.384.171.550.626.816	6.671.248.172.291.458.990.080

Beachten Sie, dass ein Gitter ein Fixpunkt mehrerer Transformationen gleichzeitig sein kann; zum Beispiel hat jedes Gitter, das eine Viertelumdrehungssymmetrie hat, auch eine Halbumdrehungssymmetrie. Die Kombination aller Transformationen, die ein bestimmtes Gitter fixieren, ist die Stabilisatoruntergruppe ("Automorphismusgruppe") dieses Gitters.

Stabilisator-Untergruppen

Russell hat eine Liste von 122 "wesentlich unterschiedlichen" nicht-trivialen Stabilisator-Untergruppen- Konjugationsklassen ("Automorphismus-Gruppen") zusammengestellt, zusammen mit einem Beispielgitter, den VPT-Konjugationsklassen in der Gruppe, einem Satz von Generatoren und der Anzahl der im Wesentlichen unterschiedlichen Gitter (Bahnen) mit dieser Stabilisatorklasse. Bis auf Isomorphie gibt es 26 verschiedene Gruppenstrukturen. Es gibt 15 verschiedene mögliche Stabilisatorgruppengrößen, die im nächsten Abschnitt aufgelistet sind.

Anzahl im Wesentlichen äquivalenter Gitter

Jedes der im Wesentlichen einzigartigen Gitter kann auf Selbstähnlichkeiten ("Automorphismen") analysiert werden, um den "Mangel" in der Anzahl von im Wesentlichen äquivalenten Gittern zu bewerten. Die Ergebnisse sind in der folgenden Tabelle zusammengefasst. Insgesamt haben 560.151 der 5.472.730.538 im Wesentlichen einzigartigen Gitter (etwa 1/10.000) eine Form von Selbstähnlichkeit (ein nicht trivialer Stabilisator).

Die Größe der Umlaufbahn (d. h. die Anzahl der im Wesentlichen äquivalenten Gitter) kann mit dem Orbit-Stabilisator-Theorem berechnet werden : Es ist die Größe der Sudoku-Symmetriegruppe geteilt durch die Größe der Stabilisator- (oder "Automorphismus")-Gruppe. Das Multiplizieren der Anzahl von im Wesentlichen einzigartigen Gittern (der Anzahl von Umlaufbahnen) mit der Umlaufbahngröße ergibt die Gesamtanzahl von Gittern mit dieser Stabilisatorgruppengröße; Summation liefert dann wieder die Gesamtzahl der möglichen Sudoku-Gitter. "Automorphe" Gitter haben kleinere Umlaufbahnen, so dass die Wahrscheinlichkeit, dass ein zufälliges Gitter eine Symmetrie hat, sinkt: von ungefähr 1 zu 10.000 für im Wesentlichen verschiedene Gitter auf ungefähr 1 zu 20.000 für alle Gitter.

Anzahl der Sudoku-Raster nach Stabilisatorgruppengröße
Größe der Stabilisatorgruppe	Anzahl der im Wesentlichen einzigartigen Gitter (Anzahl der Umlaufbahnen)	Äquivalente Gitter ( Orbitgröße ), Umbenennung ignorieren	Anzahl der Raster, Umbenennung ignorieren	Äquivalente Raster (Bahngröße), einschließlich Umetikettierung	Gesamtzahl der Gitter
1	5.472.170.387	3.359.232	18.382.289.873.462.784	1.218.998.108.160	6.670.565.349.282.175.057.920
2	548.449	1.679.616	921.183.715.584	609.499.054.080	334.279.146.711.121.920
3	7.336	1.119.744	8.214.441.984	406.332.702.720	2.980.856.707.153.920
4	2.826	839.808	2.373.297.408	304.749.527.040	861.222.163.415.040
6	1.257	559.872	703.759.104	203.166.351.360	255.380.103.659.520
8	29	419.904	12.177.216	152.374.763.520	4.418.868.142.080
9	42	373,248	15.676.416	135.444.234.240	5.688.657.838.080
12	92	279.936	25.754.112	101.583.175.680	9.345.652.162.560
18	85	186.624	15.863.040	67.722.117.120	5.756.379.955.200
27	2	124.416	248.832	45.148.078.080	90.296.156.160
36	fünfzehn	93.312	1.399.680	33.861.058.560	507.915.878.400
54	11	62.208	684.288	22.574.039.040	248.314.429.440
72	2	46.656	93.312	16.930.529.280	33.861.058.560
108	3	31.104	93.312	11.287.019.520	33.861.058.560
162	1	20.736	20.736	7.524.679.680	7.524.679.680
648	1	5.184	5.184	1.881.169.920	1.881.169.920
>1	560.151		932.547.230.208		338.402.738.897.879.040
	5.472.730.538		18.383.222.420.692.992		6.670.903.752.021.072.936.960

Andere Varianten

Für viele Sudoku-Varianten wurden Aufzählungsergebnisse berechnet: Diese sind im Folgenden zusammengefasst.

Sudoku mit zusätzlichen Einschränkungen

Im Folgenden sind alle Einschränkungen des klassischen 3×3-Sudoku (9×9-Raster) aufgeführt. Die Typennamen wurden nicht standardisiert: Klicken Sie auf die Zuordnungslinks, um die Definitionen anzuzeigen.

Typ	Anzahl Gitter	Namensnennung	Verifiziert?
Quasi-Magisches Sudoku	248.832	Jones, Perkins und Roach	Jawohl
Magisches Sudoku	5.971.968	Stertenbrink	Jawohl
Hyperwürfel	37.739.520	Stertenbrink	Jawohl
3doku	104.015.259.648	Stertenbrink	Jawohl
NRC Sudoku	6.337.174.388.428.800	Brouwer	Jawohl
Sudoku X	55.613.393.399.531.520	Russell	Jawohl
Disjunkte Gruppen	201.105.135.151.764.480	Russell	Jawohl

Sudoku mit rechteckigen Regionen

In der Tabelle sind die Blockabmessungen die der Regionen (zB 3×3 im normalen Sudoku). Die Spalte "Rel Err" gibt an, wie eine einfache Näherung auf der Grundlage berechneter Bandzahlen (in den folgenden Abschnitten detailliert beschrieben) im Vergleich zur tatsächlichen Rasterzahl abschneidet: Sie ist in allen bisher ausgewerteten Fällen eine Unterschätzung. Die Nummern für quadratische Blockraster ( n ² × n ² ) sind in (Sequenz A107739 im OEIS ) und die Nummern für 2 × n Blöcke (2 n × 2 n Raster) sind in (Sequenz A291187 im OEIS ) aufgeführt. .

Ähnlich wie bei lateinischen Quadraten kann die Anzahl der Sudoku-Raster reduziert werden, indem man beachtet, dass es eine Eins-zu-Eins-Entsprechung mit einer teilweise standardisierten Form gibt, bei der der erste Block die kanonischen Beschriftungen hat und sowohl die oberste Reihe als auch die ganz linke Spalte sortiert sind (soweit es die Regeln erlauben, dh innerhalb von Blöcken und den Stacks/Bändern selbst). Bei einem Raster mit Blöcken entspricht jedes dieser reduzierten Raster $R\times C$

(RC)!\times (R!)^{C-1}(C-1)!\times (C!)^{R-1}(R-1)!=(RC-1)! \cdot R!^{C}\cdot C!^{R}

Gesamtraster, also 9! × 72 ² oder 1.881.169.920 für das normale 3×3-Sudoku. Diese Reduktion erfolgt immer eins zu eins, im Gegensatz zu der Wirkung des gesamten Satzes von gültigkeitserhaltenden Transformationen ('Sudoku-Symmetrien'), die unten diskutiert werden.

Maße		Anzahl der vollen Gitter				Europäische Sommerzeit. Error (siehe unten)	Ein Bruchteil von Lateinische Quadrate
Netz	Blöcke	Genau	Größe	Namensnennung	Verifiziert?	Europäische Sommerzeit. Error (siehe unten)	Ein Bruchteil von Lateinische Quadrate
4×4	2×2	288	2.8800 × 10 ²	verschieden	Jawohl	−11,1 %	0,5 × 10 ⁰
6×6	2×3	28.200.960	2.8201 × 10 ⁷	Pettersen	Jawohl	−5,88%	3,5 × 10 ^-2
8×8	2×4	29.136.487.207.403.520	2.9136 × 10 ¹⁶	Russell	Jawohl	−1,91%	2,7 × 10 ^-4
9×9	3×3	6.670.903.752.021.072.936.960	6,6709 × 10 ²¹	Stertenbrink	Jawohl	−0,207%	1,2 × 10 ^-6
10×10	2×5	1.903.816.047.972.624.930.994.913.280.000	1,9038 × 10 ³⁰	Pettersen	Jawohl	−0,375%	1,9 × 10 ^-7
12×12	3×4	81.171.437.193.104.932.746.936.103.027.318.645.818.654.720.000	8.1171 × 10 ⁴⁶	Pettersen/Silber	Nein	−0,132%	Unbekannt
12×12	2×6	38.296.278.920.738.107.863.746.324.732.012.492.486.187.417.600.000	3,8296 × 10 ⁴⁹	Pettersen	Nein	−0,238%	Unbekannt
15×15	3×5	Unbekannt	Europäische Sommerzeit. 3.5086 × 10 ⁸⁴	Silber	Nein	n / A	Unbekannt
16×16	4×4	Unbekannt	Europäische Sommerzeit. 5,9584 × 10 ⁹⁸	Silber	Nein	n / A	Unbekannt
20×20	4×5	Unbekannt	Europäische Sommerzeit. 3,1764 × 10¹⁷⁵	Silber	Nein	n / A	Unbekannt
25×25	5×5	Unbekannt	Europäische Sommerzeit. 4,3648 × 10³⁰⁸	Silber/Pettersen	Nein	n / A	Unbekannt

Ein gelöstes Sudoku bleibt unter den Einwirkungen der gültigkeitserhaltenden Transformationen gültig (siehe auch Jarvis). Durch sorgfältiges Zählen der Anzahl der invarianten Gitter für jede Transformation kann man die Anzahl der im Wesentlichen unterschiedlichen Sudoku-Gitter berechnen (siehe oben). Ähnliche Methoden wurden auf Sudoku-Gitter anderer Dimensionen angewendet; die Ergebnisse sind in der folgenden Tabelle zusammengefasst. Für quadratische Blockraster (Sequenz A109741 im OEIS ) kann die Transpositionstransformation (siehe unten) in die VPT-Gruppe (Symmetrie) aufgenommen werden oder nicht. Die Anzahl der im Wesentlichen unterschiedlichen Gitter kann geschätzt werden, indem die Gesamtanzahl der Gitter (entweder bekannt oder geschätzt) durch die Größe der VPT-Gruppe (die leicht berechnet wird) geteilt wird, was im Wesentlichen davon ausgeht, dass die Anzahl der automorphen Sudokus vernachlässigbar ist. Die Nummern für 2 × n Blöcke (2 n × 2 n Gitter) sind in (Sequenz A291188 im OEIS ) aufgeführt.

Maße		VPT-Gruppe			Anzahl der im Wesentlichen unterschiedlichen Gitter	Referenz
Netz	Blöcke	T	Größe	Konj. Klassen (ohne Umetikettierung)	Anzahl der im Wesentlichen unterschiedlichen Gitter	Referenz
4×4	2×2	Jawohl	128×4!		2
4×4	2×2	Nein	64×4!		3
6×6	2×3	Nein	3.456 × 6!	90	49	Jarvis/Russell, Pettersen
8×8	2×4	Nein	4.423.368 × 8!	400	1.673.187	Russell, Pettersen
9×9	3×3	Jawohl	3.359.232 × 9!	275	5.472.730.538	Jarvis/Russell, Pettersen
9×9	3×3	Nein	1.679.616 × 9!	484	10.945.437.157	Jarvis/Russell, Pettersen
10×10	2×5	Nein	110.592.000 × 10!	1260	4.743.933.602.050.718	Pettersen/Russell
16×16	4×4	Jawohl	(4!) ¹⁰ × 2 × 16!		Europäische Sommerzeit. 2,2458 × 10 ⁷¹	(Schätzung im Text erklärt)
16×16	4×4	Nein	(4!) ¹⁰ ×16!		Europäische Sommerzeit. 4,4916 × 10 ⁷¹	(Schätzung im Text erklärt)

Schätzmethode

Die Methode von Kevin Kilfoil (verallgemeinert von Pettersen) kann verwendet werden, um die Anzahl der abgeschlossenen Gitter unter Verwendung der Anzahl der möglichen abgeschlossenen Bänder und Stapel zu schätzen. Das Verfahren behauptet, dass die Sudoku-Zeilen- und Spaltenbeschränkungen in erster Näherung bedingt unabhängig sind, wenn die Boxbeschränkung gegeben ist. Daraus ergibt sich die Kilfoil-Silver-Pettersen-Formel :

{\mbox{Anzahl der RC×RC-Gitter mit R×C-Boxen}}\simeq {\frac {(b_{R,C})^{C}\times (b_{C,R})^{ R}}{(RC)!^{RC}}}

wobei die Anzahl der Möglichkeiten zum Füllen eines R × RC- Bandes von R horizontal benachbarten R × C- Boxen ist (entspricht der Anzahl der Möglichkeiten zum Füllen eines RC × C- Stapels von C vertikal benachbarten R × C- Boxen) und der Nenner ( RC )! ^RC ist die Anzahl der Möglichkeiten, das Raster zu füllen, während nur die Boxbeschränkungen erfüllt werden. $b_{R,C}$ $b_{C,R}$

Wie Pettersen erklärt: "So ist es: Sei $X$ der Raum von -Gittern, die von legalen Sudoku-Bändern gebildet werden, aber ohne darauf zu achten, ob die Spalten den Regeln des Sudoku folgen. Die Größe von $X$ ist . Sei auch $Y$ die Menge von Gittern, die von legalen Stapeln gebildet werden, ohne dass die Zeilen $beachtet werden$ , $#Y$ ist dann .Die nxm-Sudoku-Gitter sind dann der Schnittpunkt von $X$ und $Y.$ A zufällig und sind in einer gegebenen Box mit Wahrscheinlichkeit identisch , und unter der Annahme dass diese Wahrscheinlichkeiten für jede Box unabhängig sind, kommen wir zu der obigen Schätzung." $(nm)\times (nm)$ $b(n,m)^{m}$ $b(m,n)^{n}$ $x(\in X)$ $y(\in Y)$ $(nm)!$

Diese Schätzung hat sich für das klassische 9×9-Gitter mit einer Genauigkeit von ca. 0,2 % und für größere Gitter, für die genaue Werte bekannt sind, innerhalb von 1 % als genau erwiesen (siehe Tabelle oben).

Anzahl der Bänder

Genaue Formeln für die Anzahl der möglichen Bänder in einem gefüllten Sudoku-Gitter mit Blöcken der Größe R × C sind bekannt: $b_{R,C}$

Maße		Anzahl der Bänder	Namensnennung	Verifiziert?
Band	Blöcke	Anzahl der Bänder	Namensnennung	Verifiziert?
2×2 C	2× C	$b_{2,C}=(2C)!(C!)^{2}$	(offensichtliches Ergebnis)	Jawohl
3×3 C	3× C	$b_{3,C}=(3C)!(C!)^{6}\sum _{k=0}^{C}{C \choose k}^{3}$ wobei die Summe als $C-$ ^te Franel-Zahl bekannt ist (Sequenz A000172 im OEIS )	Pettersen	Jawohl
4×4 C	4× C	$b_{4,C}=(4C)!(C!)^{12}\sum _{a,b,c}{\left({\frac {C!^{2}}{a! b!c!}}\cdot \sum _{k_{12},k_{13},k_{14}, \atop k_{23},k_{24},k_{34}}{{a \wähle k_ {12}}{b \choose k_{13}}{c \choose k_{14}}{c \choose k_{23}}{b \choose k_{24}}{a \choose k_{34}}} \right)^{2}}$ wo: der äußere Summand wird über alle a , b , c mit 0≤ a , b , c und a + b + c = 2 C übernommen . der innere Summand wird über alle k ₁₂ , k ₁₃ , k ₁₄ , k ₂₃ , k ₂₄ , k ₃₄ ≥ 0 übernommen, so dass k ₁₂ , k ₃₄ ≤ a und k ₁₃ , k ₂₄ ≤ b und k ₁₄ , k ₂₃ ≤ c und k ₁₂ + k ₁₃ + k ₁₄ = a − k ₁₂ + k ₂₃ + k ₂₄ = b − k ₁₃ + c − k ₂₃ + k ₃₄ = c − k ₁₄ + b − k ₂₄ + a − k ₃₄ = C Die äußere Summation entspricht einer Aufteilung des Bandes in zwei "Unterbänder" von jeweils 2 Kästchen; die Zahlen a , b und c beschreiben die Aufteilung und müssen für beide Teilbänder übereinstimmen, damit der Summand quadriert werden kann. Die geteilten Variablen werden wie folgt beschrieben: " a ist die Anzahl der Symbole in Zeile 1 und 2 in den ersten Boxen (d. h. Symbole, die sich entweder in Zeile 1 in Box 1 und Zeile 2 in Box 2 befinden ODER in Zeile 1 in Box 2 und Zeile 2 in Box 1) Es wird dann auch die Anzahl der Symbole in Zeile 3 und 4 in den ersten beiden Boxen, sowie die Anzahl der Symbole in Zeile 1 und 2 in den beiden letzten Boxen, und die Anzahl der Symbole in Reihe 3 und 4 in den ersten beiden Feldern b ist die Anzahl der Symbole in Reihe 1 und 3 in den ersten beiden Feldern, zusammen mit anderen Kombinationen wie bei der Variablen a . c ist die Anzahl der Symbole in Reihe 1 und 4 in den ersten beiden Kästchen." Die innere Summation zählt die Anzahl der Teilbänder für eine gegebene a , b , c Spezifikation: "Unter den a- Symbolen, die in Zeile 1 und 2 in Box 1 und 2 liegen, zählt k _12, wie viele davon in Zeile 1 in Box liegen 1 (und damit auch in Zeile 2 in Box 2) Im Allgemeinen sagt k _ij für i < j unter den Symbolen auf Zeile i und j in den ersten beiden Boxen, wie viele davon in Zeile i in Box 1 und Zeile j in Feld 2."	Pettersen	Jawohl

Einige bekannte Bandzahlen sind unten aufgeführt. Petersens Algorithmus, wie von Silver implementiert und verbessert, teilt das Band in Unterbänder auf, die dann in Äquivalenzklassen gruppiert werden; es ist derzeit die schnellste bekannte Technik zur genauen Auswertung dieser b _R,C .

Maße		Anzahl der Bänder	Namensnennung	Verifiziert?
Band	Blöcke	Anzahl der Bänder	Namensnennung	Verifiziert?
3×6	3×2	6! × 2! ⁶ × 10 = 460800	Pettersen (Formel)
3×9	3×3	9! × 3! ⁶ × 56 = 9! × 2612736 = 9481096396809,4811 × 10 ¹¹ (44 Äquivalenzklassen)	Verschieden
3×12	3×4	12! × 4! ⁶ × 346 = 316723664189915136003,1672 × 10 ¹⁹	Stertenbrink	Jawohl
3×15	3×5	fünfzehn! × 5! ⁶ × 2252 Zoll8,7934 × 10 ²⁷	Pettersen (Formel)
(größere 3×C-Werte können leicht mit der oben angegebenen Formel berechnet werden)
4×8	4×2	8! × 2! ¹² × 5016 = 8283960115208.2840 × 10 ¹¹
4×12	4×3	12! × 3! ¹² × 2180544 = 22736144626433648492544002,2736 × 10 ²⁴	Pettersen	Jawohl
4×16	4×4	16! × 4! ¹² × 12734319609.7304 × 10 ³⁸	Silber	Jawohl
4×20	4×5	20! × 5! ¹² × 8794911450241,9078 × 10 ⁵⁵	Russell	Jawohl
4×24	4×6	24! × 6! ¹² × 6775428450610568.1589 × 10 ⁷²	Russell	Jawohl
4×28	4×7	28! × 7! ¹² × 5636907472384650244,6169 × 10 ⁹¹	Russell	Jawohl
(Berechnungen bis 4×100 wurden von Silver durchgeführt, sind aber hier nicht aufgeführt)
5×10	5×2	10! × 2! ²⁰ × 3648677761.3883 × 10 ²¹ (355 Äquivalenzklassen)		Nein
5×15	5×3	fünfzehn! × 3! ²⁰ × 3244089879920641.5510 × 10 ⁴²	Silber	Ja ^{gleicher Autor, andere Methode}
5×20	5×4	20! × 4! ²⁰ × 5189104237302143141765.0751 × 10 ⁶⁶	Silber	Ja ^{gleicher Autor, andere Methode}
5×25	5×5	25! × 5! ²⁰ × 11650375504328851197092413446.9280 × 10 ⁹³	Pettersen / Silber	Nein
5×30	5×6	30! × 6! ²⁰ × 32617346918362171810027728233103361.2127 × 10 ¹²³	Pettersen / Silber	Nein
5×35	5×7	35! × 7! ²⁰ × 106645099892091995332825395255357934141441,2325 × 10 ¹⁵⁴	Pettersen / Silber	Nein
5×40	5×8	40! × 8! ²⁰ × 391193124090108259661160466453683939361228556164.1157 × 10 ¹⁸⁶	Pettersen / Silber	Nein
5×45	5×9	45! × 9! ²⁰ × 1568054480160061659402591313783290769116340372428349442.9406 × 10 ²²⁰	Pettersen / Silber	Nein
5×50	5×10	50! × 10! ²⁰ × 6744317487012274926644211384902243159311267347655819487477763.2157 × 10 ²⁵⁵	Pettersen / Silber	Nein

6×12	6×2	12! × 2! ³⁰ × 9480675056071680 = 48761392075279660441880619909120004.8761 × 10 ³³	Pettersen	Nein

Rätsel

Mindestanzahl an gegebenen

Gewöhnliche Sudokus ( richtige Rätsel) haben eine einzigartige Lösung. Ein minimales Sudoku ist ein Sudoku, von dem kein Hinweis entfernt werden kann, so dass es ein richtiges Sudoku bleibt. Verschiedene minimale Sudokus können eine unterschiedliche Anzahl von Hinweisen haben. In diesem Abschnitt wird die minimale Anzahl von gegebenen Bedingungen für richtige Rätsel beschrieben.

Gewöhnliches Sudoku

Ein Sudoku mit 17 Hinweisen.

Ein Sudoku mit 17 Hinweisen und diagonaler Symmetrie.

Ein Sudoku mit 18 Hinweisen und orthogonaler Symmetrie.

Ein automorphes Sudoku mit 24 Hinweisen und vollständiger geometrischer Symmetrie.

Ein Sudoku mit 19 Hinweisen und orthogonaler Zwei-Wege-Symmetrie.

Viele Sudokus wurden mit 17 Hinweisen gefunden, obwohl es keine triviale Aufgabe ist, sie zu finden. Ein am 1. Januar 2012 veröffentlichter Artikel von Gary McGuire, Bastian Tugemann und Gilles Civario erklärt, wie durch eine umfassende Computersuche nachgewiesen wurde, dass die Mindestanzahl von Hinweisen in jedem richtigen Sudoku 17 beträgt, und dies wurde im September 2013 unabhängig bestätigt Einige 17-Hinweis-Rätsel mit diagonaler Symmetrie wurden von Ed Russell bereitgestellt, nachdem er die Äquivalenztransformationen von Gordon Royles Datenbank mit 17-Hinweis-Rätseln durchsucht hatte. Sudoku-Rätsel mit 18 Hinweisen wurden mit 180°-Rotationssymmetrie und andere mit orthogonaler Symmetrie gefunden, obwohl nicht bekannt ist, ob diese Anzahl von Hinweisen in beiden Fällen minimal ist. Es wurden Sudoku-Rätsel mit 19 Hinweisen mit bidirektionaler orthogonaler Symmetrie gefunden, und auch hier ist nicht bekannt, ob diese Anzahl von Hinweisen für diesen Fall minimal ist.

Ein Sudoku mit 24 Hinweisen, Diedersymmetrie (Symmetrie auf beiden orthogonalen Achsen, 90° Rotationssymmetrie, 180° Rotationssymmetrie und diagonale Symmetrie) ist bekannt und auch automorph . Auch hier ist nicht bekannt, ob diese Anzahl von Hinweisen für diese Sudoku-Klasse minimal ist. Die wenigsten Hinweise in einem Sudoku mit bidirektionaler Diagonalsymmetrie werden auf 18 geschätzt, und in mindestens einem Fall weist ein solches Sudoku auch Automorphismus auf .

Von den 5.472.730.538 im Wesentlichen unterschiedlichen Lösungsrastern haben nur 4 kein 20-Hinweis-Puzzle - diese 4 Raster haben ein 21-Hinweis-Puzzle.

Sudokus anderer Größen

4×4 (2×2) Sudoku: Die wenigsten Hinweise in einem 4×4-Sudoku sind 4, von denen es 13 nicht gleichwertige Rätsel gibt. (Die Gesamtzahl der nicht-äquivalenten minimalen Sudokus dieser Größe beträgt 36.)
6×6(2×3) Sudoku: Die wenigsten Hinweise sind 8.
8×8(2×4) Sudoku: Die wenigsten Hinweise sind 14.
10×10(2×5) Sudoku: Mindestens ein Puzzle mit 22 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.
12×12(2×6) Sudoku: Mindestens ein Puzzle mit 32 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.
12×12(3×4) Sudoku: Mindestens ein Puzzle mit 30 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.
15×15(3×5) Sudoku: Mindestens ein Puzzle mit 48 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.
16×16(4×4) Sudoku: Mindestens ein Puzzle mit 55 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.
25×25(5×5) Sudoku: Ein Puzzle mit 151 Hinweisen wurde erstellt. Es ist nicht bekannt, ob dies die geringstmöglichen sind.

Sudoku mit zusätzlichen Einschränkungen

Disjunkte Gruppen: 11 Hinweise

Zusätzliche Einschränkungen (hier auf 3×3 Sudokus) führen zu einer geringeren Mindestanzahl an Hinweisen.

Disjunkte Gruppen: Glenn Fowler hat einige Rätsel mit 12 Hinweisen demonstriert. Später wurden auch 11-Hinweis-Rätsel gefunden. Es ist nicht bekannt, ob dies die bestmögliche ist.
Hypercube: Verschiedene 8-Hinweis-Rätsel wurden von Günter Stertenbrink demonstriert. Dies ist das bestmögliche.
Magic Sudoku: Ein 7-Hinweis-Beispiel wurde von Günter Stertenbrink bereitgestellt. Es ist nicht bekannt, ob dies die bestmögliche ist.
Anti-Ritter-Sudoku: Ein 8-Hinweis-Beispiel wurde von Reddit-Benutzer u/_ryokousha bereitgestellt. Dies ist das bestmögliche.
Sudoku X: Ruud van der Werf hat eine Liste von 7193 12-Hinweis-Rätseln zusammengestellt. Es ist nicht bekannt, ob dies die bestmögliche ist.
NRC Sudoku: Ein 11-Hinweis-Beispiel wurde von Andries Brouwer bereitgestellt. Es ist nicht bekannt, ob dies die bestmögliche ist.
2-Quasi-Magic Sudoku: Ein 4-Hinweis-Beispiel wurde von Tony Forbes bereitgestellt. Es wird vermutet, dass dies das bestmögliche ist.

Sudoku mit unregelmäßigen Regionen

"Du-sum-oh"-Rätsel (auch bekannt als "Geometrienummer-Platz") ersetzen die 3 × 3 (oder R × C ) Regionen von Sudoku durch unregelmäßige Formen einer festen Größe. Bob Harris hat bewiesen, dass es immer möglich ist, ( N − 1)-Hinweis du-sum-ohs auf einem N × N- Gitter zu erzeugen , und hat mehrere Beispiele konstruiert. Johan de Ruiter hat bewiesen, dass es für jedes N > 3 Polyomino-Kacheln gibt, die nicht in ein Sudoku-Puzzle mit N unregelmäßigen Formen der Größe N umgewandelt werden können .

Summenzahlstelle ("Killer-Sudoku")

An der Stelle der Summenzahl (Samunampure) gelten die üblichen Beschränkungen, dass sich in keiner Zeile, Spalte oder Region ein Wert wiederholt; zusätzlich sind zusätzliche Regionen ("Käfige") unterschiedlicher Größe und Form vorhanden, die keine Wiederholungen enthalten können, mit Hinweisen, die die Ziffernsumme innerhalb des Käfigs angeben (zB ein 4-Zellen-Käfig mit der Summe 10 muss aus den Werten 1,2,3 . bestehen ,4 in einiger Reihenfolge). Die minimale bekannte Zellenabdeckung beträgt 18 Zellen, die von Philip Newman bereitgestellt werden, und dies wird als die geringstmögliche angesehen (ein 17-Zellen-Beispiel würde ein derzeit unbekanntes klassisches Sudoku mit 17 Hinweisen implizieren). Die minimale Anzahl bekannter Käfige ist 7, ebenfalls von Philip Newman; es ist nicht bekannt, ob dies die geringstmöglichen sind.

Eine Variante auf der Website von Miyuki Misawa ersetzt Summen durch Relationen: Die Hinweise sind Symbole = , < und >, die die relativen Werte (einer, aber nicht aller) benachbarter Regionensummen anzeigen. Sie zeigt ein Beispiel mit nur acht Beziehungen. Ob dies die bestmögliche ist, ist nicht bekannt.

Maximale Anzahl von Geschenken

Ein minimales Sudoku mit 40 Hinweisen.

Die meisten Hinweise für ein minimales Sudoku werden auf 40 geschätzt, von denen nur zwei bekannt sind. Wenn ein Hinweis von einem dieser Sudokus entfernt wird, hätte das Rätsel mehr als eine Lösung (und wäre somit kein richtiges Sudoku). Bei der Suche nach diesen Sudokus wurden weitere High-Clue-Rätsel katalogisiert, darunter mehr als 6.500.000.000 Minimal-Rätsel mit 36 Hinweisen. Etwa 2600 minimale Sudokus mit 39 Hinweisen wurden ebenfalls gefunden.

Wenn die Anforderung an die Eindeutigkeit der Lösung fallengelassen wird, sind 41-Hinweis-minimale Pseudo-Puzzles bekannt, die jedoch zu mehr als einem Lösungsraster vervollständigt werden können. Das Entfernen eines Hinweises erhöht die Anzahl der Vervollständigungen und aus dieser Perspektive ist keiner der 41 Hinweise überflüssig. Da etwas mehr als die Hälfte des Gitters mit gegebenen Bedingungen gefüllt ist (41 von 81 Zellen), dominiert die Eindeutigkeit der Lösungsbeschränkung immer noch die Minimalitätsbeschränkung .

Was die meisten Hinweise angeht, die in einem Sudoku möglich sind, obwohl es immer noch keine eindeutige Lösung liefert, fehlt es vier an einem vollen Raster (77). Wenn zwei Vorkommen von jeweils zwei Zahlen fehlen und die Zellen, die sie belegen sollen, die Ecken eines orthogonalen Rechtecks sind und genau zwei dieser Zellen in einem Bereich liegen, gibt es zwei Möglichkeiten, die letzten Ziffern zu addieren (zwei Lösungen).

Anzahl der minimalen Rätsel

Die Anzahl der minimalen Sudokus (Sudokus, bei denen kein Hinweis gelöscht werden kann, ohne die Eindeutigkeit der Lösung zu verlieren) ist nicht genau bekannt. Statistische Techniken in Kombination mit einem Generator ( 'Unbiased Statistics of a CSP – A Controlled-Bias Generator' ) zeigen jedoch, dass es ungefähr (mit 0,065% relativem Fehler) gibt:

3,10 × 10 ³⁷ minimale Rätsel,
2,55 × 10 ²⁵ nicht im Wesentlichen gleichwertige minimale Rätsel.

Andere Autoren verwendeten schnellere Methoden und berechneten zusätzliche genaue Verteilungsstatistiken.

Einschränkungen der Hinweisgeometrie

Eine Reihe von Hinweispositionen, die für ein richtiges Sudoku nicht ausreichend sind.

Sudoku mit einem leeren Rechteck mit 30 Zellen (5 x 6). (22 Hinweise)

Sudoku mit neun leeren Gruppen. (22 Hinweise)

Es wurde vermutet, dass kein richtiges Sudoku Hinweise haben kann, die auf den Bereich der Positionen im freien Raum des ersten Bildes oben beschränkt sind. Es wird angenommen, dass das größte rechteckige orthogonale "Loch" (Region ohne Hinweise) in einem richtigen Sudoku ein Rechteck von 30 Zellen ist (eine rechteckige Fläche von 5 × 6). Ein Beispiel ist ein Sudoku mit 22 Hinweisen (zweites Bild). Es wird angenommen, dass die größte Gesamtzahl leerer Gruppen (Zeilen, Spalten und Kästchen) in einem Sudoku neun beträgt. Ein Beispiel ist ein Sudoku mit 3 leeren Zeilen, 3 leeren Spalten und 3 leeren Kästchen (drittes Bild).

Automorphe Sudokus

Ein Sudoku-Gitter ist automorph, wenn es so transformiert werden kann, dass es zum ursprünglichen Gitter zurückführt, wenn dieselbe Transformation sonst nicht zum ursprünglichen Gitter zurückführen würde. Ein Beispiel für ein automorphes Gitter wäre ein Gitter, das um 180 Grad gedreht werden kann, was zu einem neuen Gitter führt, bei dem die neuen Zellenwerte eine Permutation des ursprünglichen Gitters sind. Automorphe Sudokus sind Sudoku-Rätsel, die sich zu einem automorphen Raster lösen. Zwei Beispiele für automorphe Sudokus und ein automorphes Gitter werden unten gezeigt.

Ein automorphes Sudoku mit 18 Hinweisen (Zwei-Wege-Diagonalsymmetrie)

Ein automorphes Sudoku mit 24 Hinweisen (Zweiwege-Diagonalsymmetrie und Translationssymmetrie)

Das "Most Canonical" Lösungsraster (648 Automorphismen)

Anzahl von im Wesentlichen unterschiedlichen Gittern bei jeder
Automorphismus-Zählung
auto- morphisms	Anzahl Gitter	auto- morphisms	Anzahl Gitter
1	5472170387	18	85
2	548449	27	2
3	7336	36	fünfzehn
4	2826	54	11
6	1257	72	2
8	29	108	3
9	42	162	1
12	92	648	1

Beachten Sie in den ersten beiden Beispielen, dass das Sudoku, wenn es um 180 Grad gedreht wird und die Hinweise mit der Permutation (123456789) -> (987654321) umbenannt werden, zum selben Sudoku zurückkehrt. Anders ausgedrückt haben diese Sudokus die Eigenschaft, dass jedes 180-Grad-Rotationspaar von Hinweisen (a, b) der Regel (a) + (b) = 10 folgt.

Da diese Sudokus automorph sind, sind auch ihre Lösungsgitter automorph. Außerdem hat jede gelöste Zelle einen symmetrischen Partner, der mit der gleichen Technik gelöst wird (und das Paar würde die Form a + b = 10 annehmen). Beachten Sie, dass das Sudoku im zweiten Beispiel auch Translations- (oder Wiederholungs-)Symmetrie aufweist; Hinweise werden in Gruppen gruppiert, wobei die Hinweise in jeder Gruppe sequentiell geordnet sind (dh n, n+1, n+2 und n+3).

Das dritte Bild ist das kanonischste Lösungsraster. Dieses Gitter hat 648 Automorphismen und trägt zu allen ~6,67 × 10 ²¹ Lösungsgitter um den Faktor 1/648 im Vergleich zu jedem nicht-automorphen Gitter.

In diesen Beispielen sind die Automorphismen leicht zu identifizieren, aber im Allgemeinen ist Automorphismus nicht immer offensichtlich. Die Tabelle rechts zeigt die Anzahl der im Wesentlichen unterschiedlichen Sudoku-Lösungsgitter für alle existierenden Automorphismen.

Details zum Aufzählen verschiedener Raster (9×9)

Es wurde eine Aufzählungstechnik basierend auf Bandgenerierung entwickelt, die deutlich weniger rechenintensiv ist. Die Strategie beginnt mit der Analyse der Permutationen des oberen Bandes, die in gültigen Lösungen verwendet werden. Sobald die Band1- Symmetrien und die Äquivalenzklasse für die Teillösungen identifiziert sind, werden die Vervollständigungen der unteren beiden Bänder konstruiert und für jede Äquivalenzklasse gezählt.

Zählen der Top-Band-Permutationen

1	2	3
4	5	6
7	8	9

Der Band1-Algorithmus geht wie folgt vor:

Wählen Sie eine kanonische Beschriftung der Ziffern, indem Sie Werte für B1 zuweisen (siehe Raster), und berechnen Sie den Rest der Band1-Permutationen relativ zu B1.
Berechnen Sie die Permutationen von B2 durch Partitionieren der B1 - Zellwerte über die B2 Reihe Tripletts . Berechnen Sie aus den Triplettkombinationen die B2-Permutationen. Es gibt k=0..3 Möglichkeiten zur Auswahl der:

B1 r11 Werte für B2 r22, der Rest muss zu r16 gehen,

B1 r12 Werte für B2 r23, der Rest muss zu r16 gehen,

B1 r13 Werte für B2 r21, der Rest muss zu r16 gehen, dh

{\mbox{N Kombinationen für B2}}=\sum _{k=0}^{3}{{3 \choose k}^{3}}

(Dieser Ausdruck kann auf jede beliebige R × 3 Boxband-Variante verallgemeinert werden . (Pettersen). B2 trägt also 56 × 6 ³ Permutationen bei.

Die Auswahl für B3-Triolen wird reihenweise durch die B1-B2-Reihen-Tripletts bestimmt. B3 trägt immer 6 ³ Permutationen bei.

Die Permutationen für Band1 sind $9! \times 56 \times 6 6 = 9! \times 2612736 9,48 \times 1011$ .

Permutationsdetails für Band1

Triplet rBR(Box/Reihe) Etiketten

R	1	1
R	1	2
R	1	3

R	2	1
R	2	2
R	2	3

R	3	1
R	3	2
R	3	3

Die Permutationen von B1 sind die Anzahl der Möglichkeiten, die 9 Ziffern umzubenennen, 9! = 362880. Das Zählen der Permutationen für B2 ist komplizierter, da die Auswahl für B2 von den Werten in B1 abhängt. (Dies ist eine visuelle Darstellung des oben angegebenen Ausdrucks.) Die bedingte Berechnung benötigt für jede Alternative eine Verzweigung (Unterberechnung). Glücklicherweise gibt es nur 4 Fälle für das oberste B2-Triplett (r21): Es enthält entweder 0, 1, 2 oder 3 der Ziffern aus dem B1-Triolen der mittleren Reihe (r12). Sobald diese Auswahl für die B2-Oberreihe getroffen wurde, sind die restlichen B2-Kombinationen festgelegt. Die Triplet-Beschriftungen der Reihe Band1 werden rechts angezeigt.

(Hinweis: Bedingte Kombinationen werden mit fortschreitender Berechnung durch das Gitter immer schwieriger. Zu diesem Zeitpunkt sind die Auswirkungen minimal.)

Fall 0 Matching Cells Triplets

1	2	3
4	5	6
7	8	9

7	8	9
1	2	3
4	5	6

4	5	6
7	8	9
1	2	3

Fall 0: Keine Überlappung. Die Auswahlmöglichkeiten für die Tripletts können durch Eliminierung bestimmt werden.

r21 kann nicht r11 oder r12 sein, also muss es = r13 sein; r31 muss = r12 sein usw.

Das Diagramm Fall 0 zeigt diese Konfiguration, wobei die rosa Zellen Triplettwerte sind, die in beliebiger Reihenfolge innerhalb des Tripletts angeordnet werden können. Jedes Drilling hat 3! = 6 Permutationen. Die 6 Tripletts tragen 6 ⁶ Permutationen bei.

Fall 3: 3-stellige Übereinstimmung: Triplett r21 = r12. Es gilt die gleiche Logik wie im Fall 0, jedoch mit einer anderen Triplettverwendung. Triplett r22 muss = r13 sein usw. Die Anzahl der Permutationen ist wieder 6 ⁶ (Felgenhauer/Jarvis). Nennen Sie die Fälle 0 und 3 den reinen Match- Fall.

Fall 1-Match – Triplet-Zellenoptionen

1	2	3
4	5	6
7	8	9

3	3	2
1	3	2
1	2	1

3	2	1
3	2	1
3	2	1

Fall 1: 1 Match für r21 von r12

Im Diagramm Fall 1 zeigen B1-Zellen kanonische Werte, die farbcodiert sind, um ihre reihenweise Verteilung in B2-Tripletts anzuzeigen. Farben spiegeln die Verteilung wider, aber nicht den Standort oder die Werte. Für diesen Fall: das B2-Triol der obersten Reihe (r21) hat 1 Wert aus dem mittleren B1-Triol, die anderen Färbungen können nun abgeleitet werden. ZB wird die Farbgebung des B2-Triolen der unteren Reihe (r23) durch r21 erzwungen: die anderen 2 B1-Mittelwerte müssen nach unten gehen usw. Geben Sie die Anzahl der B2-Optionen für jede Farbe ein, 3..1, beginnend oben links. Die B3-Farbcodierung entfällt, da die B3-Auswahl reihenweise durch B1, B2 bestimmt wird. B3 trägt immer 3 bei! Permutationen pro Zeilentripel oder 6 ³ für den Block.

Für B2 können die Triplettwerte in jeder Position erscheinen, also eine 3! Für jedes Triplett gilt weiterhin der Permutationsfaktor. Da jedoch einige der Werte relativ zu ihrem Ursprung gepaart wurden, würde die Verwendung der Rohoptionszählungen aufgrund der Austauschbarkeit innerhalb der Paarung die Anzahl der Permutationen überzählen. Die Anzahl der Optionen muss durch die permutierte Größe ihrer Gruppierung (2) geteilt werden, hier 2! = 2 (Siehe ) Das Paar in jeder Reihe hebt die 2er für die B2-Optionszählungen auf, so dass ein B2-Beitrag von $3$ $3$ $\times 6$ $3 übrigbleibt$ . Der kombinierte Beitrag B2×B3 beträgt $3$ $3$ $\times 6$ $6$ . $\color {Blau}{n \choose k}$

Fall 2 Match – Triplet-Zellenoptionen

1	2	3
4	5	6
7	8	9

3	2	3
2	1	3
2	1	1

3	2	1
3	2	1
3	2	1

Fall 2: 2 Übereinstimmungen für r21 von r12. Es gilt dieselbe Logik wie in Fall 1, jedoch mit umgekehrter Spaltengruppierung der Option B2. Fall 3 trägt auch 3 ³ × 6 ⁶ Permutationen bei.

Die Summe der 4 Fälle für Band1 B1..B3 ergibt $9! \times 2 \times (3 3 + 1) \times 6 6 = 9! 56 \times 6 6$ Permutationen.

Band1-Symmetrien und Äquivalenzklassen

Symmetrien werden verwendet, um den Rechenaufwand zum Aufzählen der Band1-Permutationen zu reduzieren. Eine Symmetrie ist eine Operation, die die Qualität eines Objekts bewahrt. Bei einem Sudoku-Gitter ist eine Symmetrie eine Transformation, deren Ergebnis ebenfalls ein gültiges Gitter ist. Für das obere Band gelten unabhängig voneinander folgende Symmetrien:

Die Werte von Block B1 können umbenannt werden, was 9 ergibt! Permutationen
Blöcke B1..3 dürfen mit 3!=6 Permutationen vertauscht werden
Die Zeilen 1..3 dürfen vertauscht werden, mit 3!=6 Permutationen
Innerhalb jedes Blocks können die 3 Spalten vertauscht werden, was 3 ergibt! ³ = 6 ³ Permutationen.

Zusammen ergeben die Symmetrien 9! × 6 ⁵ = 362880 × 7776 äquivalente Permutationen für jede Band1-Lösung.

Eine Symmetrie definiert eine Äquivalenzbeziehung , hier zwischen den Lösungen, und Trennwänden , die Lösungen in einen Satz von Äquivalenzklassen . Die Band1-Zeilen-, Spalten- und Blocksymmetrien teilen die Permutationen in (nicht weniger als) 336 (56×6) Äquivalenzklassen mit (bis zu) 6 ⁵ Permutationen in jeder und 9! Umbenennung von Permutationen für jede Klasse. ( Min/Max- Vorbehalte gelten, da einige Permutationen aufgrund der Umetikettierung möglicherweise keine unterschiedlichen Elemente ergeben.) $56\times 6^{6}$

Da die Lösung für jedes Element einer Äquivalenzklasse aus der Lösung jedes anderen Elements generiert werden kann, müssen wir nur die Lösungen für ein einzelnes Element aufzählen, um alle Lösungen über alle Klassen aufzuzählen. Lassen

sb : eine gültige Permutation des oberen Bandes sein
Sb = [sb] : sei eine Äquivalenzklasse, relativ zu sb und einer Äquivalenzrelation
Sb.z = |Sb| : die Größe von Sb, sei die Anzahl der sb Elemente (Permutationen) in [sb]
Sb.n : die Anzahl der Band2,3-Vervollständigungen für (beliebige) sb in Sb
{Sb} : die Menge aller Sb-Äquivalenzklassen relativ zur Äquivalenzrelation
{Sb}.z = |{Sb}| : sei die Anzahl der Äquivalenzklassen

Die Gesamtzahl der Lösungen N ist dann:

N =Sb.z × Sb.n

Lösungs- und Zählpermutationssymmetrie

Die Band1-Symmetrien (oben) sind Lösungs-Permutationssymmetrien, die so definiert sind, dass eine permutierte Lösung auch eine Lösung ist. Um Lösungen aufzuzählen, kann eine Zählsymmetrie zur Gittervervollständigung verwendet werden, um Bandäquivalenzklassen zu definieren, die eine minimale Anzahl von Klassen ergeben.

Durch das Zählen der Symmetrie werden gültige Band1-Permutationen in Klassen unterteilt, die den unteren Bändern die gleichen Vervollständigungsbeschränkungen auferlegen; alle Mitglieder einer Symmetrie- Äquivalenzklasse für die Bandzählung müssen dieselbe Anzahl von Gittervervollständigungen aufweisen, da die Vervollständigungsbeschränkungen äquivalent sind. Zählsymmetriebeschränkungen werden durch die Band1-Spaltentripel identifiziert (ein Spaltenwertsatz, keine implizierte Elementreihenfolge). Unter Verwendung der Bandzählsymmetrie wurde ein minimaler Generatorsatz von 44 Äquivalenzklassen erstellt.

(1) Band1 Beispiel

1	2	3
4	5	6
7	8	9

5	8	6
9	1	7
4	3	2

7	4	9
8	2	3
5	1	6

(2) Säulentripel

1	2	3
4	5	6
7	8	9

4	1	2
5	3	6
9	8	7

5	1	3
7	2	6
8	4	9

(3) Bestellte Col. Triplets

1	2	3
4	5	6
7	8	9

1	3	5
2	6	7
4	9	8

1	2	4
3	6	5
8	7	9

Die folgende Sequenz zeigt die Zuordnung einer Bandkonfiguration zu einer Zählsymmetrie-Äquivalenzklasse. Beginnen Sie mit einer gültigen Bandkonfiguration (1). Erstellen Sie Spaltentripel, indem Sie die Spaltenwerte innerhalb jeder Spalte anordnen. Dies ist kein gültiges Sudoku-Band, erlegt aber den unteren Bändern die gleichen Beschränkungen auf wie im Beispiel (2). Konstruieren Sie eine Äquivalenzklassen-ID aus den Tripletwerten der Spalten B2, B3. Verwenden Sie Spalten- und Box-Swaps, um die niedrigste lexikografische ID zu erreichen. Die letzte Abbildung zeigt die Spalten- und Kästchenreihenfolge für die ID: 124 369 578 138 267 459. Alle Band1-Permutationen mit dieser Zählsymmetrie-ID haben dieselbe Anzahl von Gittervervollständigungen wie im ursprünglichen Beispiel. Eine Erweiterung dieses Prozesses kann verwendet werden, um die größtmöglichen Symmetrieäquivalenzklassen für die Bandzählung zu bilden (3).

Beachten Sie, dass Spaltentripel verwendet werden, um die Äquivalenzklassen zu konstruieren und zu identifizieren, die Klassenmitglieder selbst jedoch die gültigen Band1-Permutationen sind: Die Klassengröße (Sb.z) spiegelt Spaltentripel-Permutationen wider, die mit den Anforderungen der One-Regel- Lösung kompatibel sind. Die Zählsymmetrie ist eine Vervollständigungseigenschaft und gilt nur für ein Teilgitter (Band oder Stapel). Lösungssymmetrie zur Konservierung von Lösungen kann entweder auf Teilgitter (Bänder, Stapel) oder Vollgitterlösungen angewendet werden. Beachten Sie schließlich, dass die Zählsymmetrie restriktiver ist als die einfache numerische Vervollständigungs-Zählgleichheit: Zwei (verschiedene) Bänder gehören nur dann zur gleichen Zählsymmetrie- Äquivalenzklasse, wenn sie äquivalente Vervollständigungsbeschränkungen auferlegen.

Details zur Reduzierung von Band 1

Symmetrien gruppieren ähnliche Objekte in Äquivalenzklassen . Für Äquivalenzklassen und Bandsymmetrien, wie hier verwendet, sind zwei Zahlen zu unterscheiden, eine dritte:

die Anzahl der Äquivalenzklassen ({Sb}.n).
die Kardinalität , Größe oder Anzahl der Elemente in einer Äquivalenzklasse, die je nach Klasse variieren kann (Sb.z)
die Anzahl der Band2,3-Vervollständigungen, die mit einem Mitglied einer Band1-Äquivalenzklasse (Sb.n) kompatibel sind

Die Symmetrien von Band1 (6 ⁵ ) teilen die (56×6 ⁶ ) gültigen Permutationen von Band1 in (nicht weniger als) 336 (56×6) Äquivalenzklassen mit jeweils (bis zu) Permutationen. Die Vorbehalte von mindestens und bis zu sind erforderlich, da einige Kombinationen der Transformationen möglicherweise keine eindeutigen Ergebnisse liefern, wenn eine Umetikettierung erforderlich ist (siehe unten). Folglich können einige Äquivalenzklassen weniger als 6 ⁵ verschiedene Permutationen enthalten und die theoretische Mindestanzahl von Klassen wird möglicherweise nicht erreicht. $6^{5}$

Jede der gültigen Band1-Permutationen kann mit den Band2,3-Permutationen in eine bestimmte Anzahl von Lösungen erweitert (vervollständigt) werden. Aufgrund ihrer Ähnlichkeit hat jedes Mitglied einer Äquivalenzklasse die gleiche Anzahl von Vervollständigungen. Folglich müssen wir nur die Lösungen für ein Mitglied jeder Äquivalenzklasse konstruieren und dann die Anzahl der Lösungen mit der Größe der Äquivalenzklasse multiplizieren. Es bleibt noch die Aufgabe, die Größe jeder Äquivalenzklasse zu identifizieren und zu berechnen. Weitere Fortschritte erfordern die geschickte Anwendung von Rechentechniken zum Katalogisieren (Klassifizieren und Zählen) der Permutationen in Äquivalenzklassen.

Felgenhauer/Jarvis katalogisierten die Band1-Permutationen unter Verwendung lexikographisch geordneter IDs basierend auf den geordneten Ziffern aus den Blöcken B2,3. Block 1 verwendet eine kanonische Ziffernzuordnung und wird für eine eindeutige ID nicht benötigt. Die Identifizierung und Verknüpfung von Äquivalenzklassen verwendet die niedrigste ID innerhalb der Klasse.

Die Anwendung der (2×6 ² ) B2,3-Symmetriepermutationen erzeugt 36288 (28×6 ⁴ ) Äquivalenzklassen, jede der Größe 72. Da die Größe fest ist, muss die Berechnung nur die 36288 Äquivalenzklassen-IDs finden. (Hinweis: In diesem Fall liefert für jede Band1-Permutation die Anwendung dieser Permutationen zum Erzielen der niedrigsten ID einen Index für die zugehörige Äquivalenzklasse.)

Die Anwendung der restlichen Block-, Spalten- und Zeilensymmetrien führte zu einer weiteren Reduzierung, dh Aufteilung der 36288 IDs in weniger, größere Äquivalenzklassen. Wenn die kanonische B1-Bezeichnung durch eine Transformation verloren geht, wird das Ergebnis in die kanonische B1-Verwendung umbenannt und dann unter dieser ID katalogisiert. Dieser Ansatz erzeugte 416 Äquivalenzklassen, etwas weniger effektiv als die theoretische Mindestgrenze von 336 für eine vollständige Reduzierung. Die Anwendung von Zählsymmetriemustern für doppelte gepaarte Ziffern führte zu einer Reduktion auf 174 und dann auf 71 Äquivalenzklassen. Die Einführung von Äquivalenzklassen basierend auf Bandzählsymmetrie (nach Felgenhauer/Jarvis von Russell) reduzierte die Äquivalenzklassen auf einen minimalen Generatorsatz von 44.

Die Vielfalt der ~2,6 × 10 ⁶ , 56 × 6 ⁶ Band1-Permutationen können auf einen Satz von 44 Band1-Äquivalenzklassen reduziert werden. Jede der 44 Äquivalenzklassen kann zu Millionen unterschiedlicher vollständiger Lösungen erweitert werden, aber der gesamte Lösungsraum hat einen gemeinsamen Ursprung in diesen 44. Die 44 Äquivalenzklassen spielen auch in anderen Aufzählungsansätzen eine zentrale Rolle, und Spekulationen werden auf die Eigenschaften der 44 Klassen, wenn die Rätseleigenschaften später untersucht werden.

Band 2–3 Abschluss und Ergebnisse

Das Aufzählen der Sudoku-Lösungen gliedert sich in eine anfängliche Einrichtungsphase und dann in zwei verschachtelte Schleifen. Anfänglich werden alle gültigen Band1-Permutationen in Äquivalenzklassen gruppiert, die jeweils eine gemeinsame Einschränkung für die Band2,3-Vervollständigungen auferlegen. Für jede der Band1-Äquivalenzklassen müssen alle möglichen Band2,3-Lösungen aufgezählt werden. Eine äußere Band1-Schleife iteriert über die 44 Äquivalenzklassen. In der inneren Schleife werden alle unteren Bandvervollständigungen für jede der Band1-Äquivalenzklassen gefunden und gezählt.

Die für die Suche nach einer Lösung im unteren Band erforderliche Berechnung kann durch die gleiche Art von Symmetrieanwendung, die für Band1 verwendet wird, minimiert werden. Es sind 6! (720) Permutationen für die 6 Werte in Spalte 1 von Band2,3. Das Anwenden der Permutationen des unteren Bandes (2) und der Reihe innerhalb des Bandes (6×6) erzeugt 10 Äquivalenzklassen der Größe 72. An diesem Punkt ist das Vervollständigen von 10 Lösungssätzen für die verbleibenden 48 Zellen mit einem rekursiven Abstieg, Backtracking- Algorithmus mit 2 . machbar GHz-Klasse PC, so dass keine weitere Vereinfachung erforderlich ist, um die Aufzählung durchzuführen. Mit diesem Ansatz hat sich gezeigt, dass 6.670.903.752.021.072.936.960 (6,67 × 10 ²¹ ).

Das von Russell bestätigte Ergebnis enthält auch die Verteilung der Lösungszahlen für die 44 Äquivalenzklassen. Die aufgeführten Werte sind vor Anwendung der 9! Faktor für die Markierung und die beiden 72 Faktoren (72 ² = 5184) für jede der Stack 2,3- und Band2,3-Permutationen. Die Anzahl der Vervollständigungen für jede Klasse liegt durchweg in der Größenordnung von 100.000.000, während die Anzahl der Band1-Permutationen, die von jeder Klasse abgedeckt werden, jedoch zwischen 4 und 3240 variiert. Innerhalb dieses breiten Größenbereichs gibt es eindeutig zwei Cluster. Nach Größe geordnet, durchschnittlich die unteren 33 Klassen ~400 Permutationen/Klasse, während die oberen 11 durchschnittlich ~2100. Die Diskrepanz in der Konsistenz zwischen den Verteilungen für Größe und Anzahl der Fertigstellungen oder die Trennung in zwei Cluster nach Größe muss noch untersucht werden.

Siehe auch

Kombinatorische Explosion (mit Zusammenfassung der Rasterzahl von Sudoku im Vergleich zu lateinischen Quadraten)
Tanzende Links
Glossar von Sudoku
Sudokian
Sudoku-Code

Verweise

Weiterlesen

Rosenhaus, Jason ; Taalmann, Laura (2011). Unter Sudoku Im Ernst: Die Mathematik hinter der beliebtestenen Bleistift Puzzle der Welt . Oxford University Press.

Externe Links

Der Difference-Map-Algorithmus von V. Elser löst auch Sudoku
Sudoku Puzzle – eine Übung in Constraint Programming und Visual Prolog 7 von Carsten Kehler Holst (in Visual Prolog )
Sudoku Squares and Chromatic Polynomials von Herzberg und Murty behandelt Sudoku-Rätsel als Probleme der Vertexfärbung in der Graphentheorie .

Languages

In other projects

Mathematik des Sudoku - Mathematics of Sudoku

Überblick

Mathematischer Kontext

Sudokus von Gruppentischen

Varianten

Rechteckige Bereiche

Puzzle-Sudokus

Lösungen

Gewöhnliches Sudoku

Alle Lösungen

Grundsätzlich andere Lösungen

Gültigkeitserhaltende Transformationen

Die Sudoku-Symmetriegruppe

Fixpunkte und Burnsides Lemma

Stabilisator-Untergruppen

Anzahl im Wesentlichen äquivalenter Gitter

Andere Varianten

Sudoku mit zusätzlichen Einschränkungen

Sudoku mit rechteckigen Regionen

Schätzmethode

Anzahl der Bänder

Rätsel

Mindestanzahl an gegebenen

Gewöhnliches Sudoku

Sudokus anderer Größen

Sudoku mit zusätzlichen Einschränkungen

Sudoku mit unregelmäßigen Regionen

Summenzahlstelle ("Killer-Sudoku")

Maximale Anzahl von Geschenken

Anzahl der minimalen Rätsel

Einschränkungen der Hinweisgeometrie

Automorphe Sudokus

Details zum Aufzählen verschiedener Raster (9×9)

Zählen der Top-Band-Permutationen

Permutationsdetails für Band1

Band1-Symmetrien und Äquivalenzklassen

Lösungs- und Zählpermutationssymmetrie

Details zur Reduzierung von Band 1

Band 2–3 Abschluss und Ergebnisse

Siehe auch

Verweise

Weiterlesen

Externe Links