Themabewertung:
  • 0 Bewertung(en) - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
Neuer (?) Fund über Sudoku-Geometrie
#1
Photo 
Hallo zusammen,

ich hab letztens ein bisschen über die Geometrie des Sudoku-Gitters nachgegrübelt und bin dabei auf einen interessanten Fund gestoßen. Da ich leider nicht allzu erfahren bin, kann es natürlich gut sein, dass das schon ein alter Hut ist. Daher wollte ich euch auf Eure Erfahrung zurück greifen und Euch fragen, ob euch das vielleicht bekannt ist.

Meine Überlegung begann bei der folgenden Geometrie, bei der man leicht zeigen kann, dass die Summe der Ziffern in den dunkelroten Blöcken der Summe der Ziffern im blauen Gebiet entspricht:
[Bild: bild.php?data=be82f74e-6191-3030303343332d31]
Möchte man die Summe der Ziffern im gesamten roten Gebiet bestimmen, gibt es im Wesentlichen zwei Möglichkeiten:
1. Es werden die Zeilen 1, 2, 8 und 9 und die Spalten 1, 2, 8 und 9 aufsummiert und davon die dunkelroten Käfige A, B, C und D abgezogen, d.h.
8*45-A-B-C-D.
2. Es werden alle 3x3-Blöcke bis auf den mittleren aufsummiert und das blaue Gebiet davon abgezogen, d.h.
8*45-blaues Gebiet.
Damit erhalten wir: Summe der Ziffern im blauen Gebiet=A+B+C+D.

Was mir allerdings keine Ruhe ließ, war die Beobachtung, dass in jedem Beispiel, das ich mir ansah, nicht nur die Summen gleich waren, sondern auch alle Ziffern und deren Anzahl in den dunkelroten Blöcken und dem blauen Gebiet übereinstimmten. Nach einigem Grübeln fand ich einen Beweis dafür (der hoffentlich stimmt...):
[Bild: bild.php?data=b2a6bb64-6192-3030303343332d32]
Um die Behauptung zu zeigen, betrachten wir die Zeilen 3 und 7, die Spalten 3 und 7, sowie die 3x3-Blöcke in den vier Ecken. Um den Sachverhalt einfacher zu beschreiben, werden Spalten und Zeilen einfach als Linien bezeichnet. Sei nun "n" eine Ziffer von 1 bis 9. Dann muss "n" jeweils genau einmal in den 4 Linien und den 4 Blöcken auftreten. Wenn "n" also in einer
- grünen Zelle auftaucht, werden dadurch eine Linie und eine Box abgedeckt,
- roten Zelle auftaucht, wird dadurch eine Box abgedeckt,
- blauen Zelle auftaucht, wird dadurch eine Linie abgedeckt,
- orangen Zelle auftaucht, werden dadurch zwei Linie und eine Box abgedeckt.

Also haben nur die grünen Zellen eine Balance zwischen der Anzahl an Linien und Boxen, die sie abdecken. Damit muss für jedes Mal, das "n" in einer roten Zelle auftaucht, "n" auch in einer blauen oder orangen Zelle auftauchen und umgekehrt. Nachdem das für jede Ziffer zwischen 1 und 9 gilt, muss das rote Gebiet die gleichen Ziffern in der gleichen Anzahl enthalten wie das blaue und das orange Gebiet zusammen.

Kennt jemand von euch ein Ergebnis von dieser Art? Ich wäre euch sehr dankbar, wenn ihr mir Feedback dazu geben würdet - natürlich auch zu etwaigen Fehlern oder interessanten Folgerungen.
Zitieren
#2
Zwei Folgerungen sind mir selbst noch aufgefallen:
1. Der Trick gilt nicht exklusiv für die 3. und 7. Zeile und Spalte. Er kann auf jedes Quadrupel von zwei Zeilen und zwei Spalten angewendet werden, deren Schnittpunkte in vier unterschiedlichen 3x3-Boxen sind. Für das folgende Beispiel hab ich die Zeilen 4 und 8, sowie die Spalten 6 und 8 gewählt und wiederum enthält das rote Gebiet die gleichen Ziffern in der gleichen Verteilung wie das blaue und orange Gebiet zusammen:
[Bild: bild.php?data=438a478d-6193-3030303343332d33]

2. Nachdem zudem das ein gültiges Sudoku gültig bleibt, wenn zwei Zeilen oder zwei Spalten vertauscht werden, können wir auch eine Geometrie wie im folgenden Beispiel erhalten, bei dem wiederum das rote Gebiet die gleiche Verteilung von Ziffern aufweist wie das blaue und orange Gebiet zusammen:

[Bild: bild.php?data=e685dd98-6194-3030303343332d34]
Zitieren
#3
Dein Beweis, dass die Summe gleich ist, funktioniert doch auch schon für die Mengen der Ziffern? Da braucht es m.E. gar kein weiteres Grübeln über einen weiteren Beweis. Solche Invarianten sind super interessant, allerdings denke ich, man sollte sie eher nicht als Lösungsschritte irgendwo einbauen :-) Sie eignen sich aber, um manchmal zu sehen, dass ein teilweise fertiges Sudoku überhaupt keine Lösung mehr haben kann, obwohl man keinen sofortigen Widerspruch sieht. Wobei alles, was durch Vertauschen aus der "symmetrischen" Variante folgt, im Kopf wohl nur schwer zu überblicken ist.

Das letzte Bild halte ich für falsch, du kannst nur Zeilen und Spalten innerhalb desselben Blockes tauschen oder komplette Blöcke. Damit kann man m.E. die roten 2x4-Boxen in den Ecken nicht durch Vertauschen aus den vorherigen Beispielen erzeugen. Der Beweis durch doppeltes Abzählen (was ja eine Standardtechnik in der Kombinatorik ist) funktioniert dort aber genauso.
Zitieren
#4
(11.04.2020, 17:27)Realshaggy schrieb: Dein Beweis, dass die Summe gleich ist, funktioniert doch auch schon für die Mengen der Ziffern?

Du hast recht! Danke, das ist mir gar nicht aufgefallen.

(11.04.2020, 17:27)Realshaggy schrieb: Das letzte Bild halte ich für falsch, du kannst nur Zeilen und Spalten innerhalb desselben Blockes tauschen oder komplette Blöcke. Damit kann man m.E. die roten 2x4-Boxen in den Ecken nicht durch Vertauschen aus den vorherigen Beispielen erzeugen.
Auch hier hast du natürlich recht. Dankeschön für die Rückmeldung.  :-)

(11.04.2020, 17:27)Realshaggy schrieb: Solche Invarianten sind super interessant, allerdings denke ich, man sollte sie eher nicht als Lösungsschritte irgendwo einbauen :-)

Warum fühle ich mich nur so ertappt? ;-)
Zitieren
#5
(11.04.2020, 18:16)Phistomefel schrieb:
(11.04.2020, 17:27)Realshaggy schrieb: Solche Invarianten sind super interessant, allerdings denke ich, man sollte sie eher nicht als Lösungsschritte irgendwo einbauen :-)

Warum fühle ich mich nur so ertappt? ;-)

Also ich würde gerne sehen, was du damit machen kannst. Gerade wenn die Gestaltung des Rätsels auf solche Geometrie hinweist, kann das durchaus findbar sein.

Ich vermute, dass ein klassisches Sudoku, dessen Konstruktion hierauf fußt, sich auf einfachere Argumente reduziert, lasse mich aber gerne eines Besseren belehren. Beim Killer scheint es mir vielversprechender, da man da mit Kästchengruppen arbeiten kann.

Jedenfalls eine spannende Beobachtung, danke!
Zitieren
#6
Ja, mit "Vorwarnung" und wenn das Layout einen etwas in die richtige Richtung schubst, ist das natürlich etwas anderes. Ich hab da auch noch eine Idee. Standard-Sudoku sind eh eine Kunst für sich, die ich nicht ansatzweise beherrsche. Ich schaffe es noch nicht mal bei einfacheren Schlussweisen, die ich einbauen möchte, diese später nicht kaputtzumachen. Bei Varianten ist das irgendwie viel einfacher.

Du hattest noch nach anderen Beispielen gefragt. Vor einigen Jahren (das müßte mindestens vor 2011 gewesen sein, weil ich in dem Jahr mal ein Rätsel dazu gebaut habe) hat Roland Voigt (hausigel) mal etwas über Lateinische 6x6-Quadrate mit zusätzlicher Diagonalenbedingung geschrieben. Entweder in seinem damaligen Blog oder einem Artikel in unserer Mitgliederzeitschrift, ich weiß es nicht mehr. Jedenfalls gibt es da mehrere Gruppen aus vier Feldern, die dieselben Ziffern enthalten und diese Ziffern sind, wenn ich mich richtig erinnere, auch noch alle verschieden (trotz dass sie so liegen, dass das erstmal nicht zwingend aussieht). Er hat keinen logischen Beweis gefunden, aber es ließ sich mit Fallunterscheidung noch komplett verifizieren. Wenn man das weiß, wird dieses Rätsel etwas einfacher, auch wenn man es auch anders lösen kann: https://logic-masters.de/Raetselportal/R...&id=0001DH
Vielleicht gibt es ähnliches auch noch bei größeren Rätseln und vielleicht gibt's auch bei Sudokus noch unentdeckte Geheimnisse, das Problem ist halt immer, dass es wenn kein schlüssiger Beweise dahin führt (wie in deinem Beispiel) erstmal jemand drauf kommen muss.
Zitieren
#7
(11.04.2020, 21:41)rob schrieb: Also ich würde gerne sehen, was du damit machen kannst. Gerade wenn die Gestaltung des Rätsels auf solche Geometrie hinweist, kann das durchaus findbar sein.

Ich vermute, dass ein klassisches Sudoku, dessen Konstruktion hierauf fußt, sich auf einfachere Argumente reduziert, lasse mich aber gerne eines Besseren belehren. Beim Killer scheint es mir vielversprechender, da man da mit Kästchengruppen arbeiten kann.
Deine Überlegungen zu einem Rätsel, das die Beobachtung ausnutzt, decken sich mit meinen. Ich hab versucht, ein klassisches Sudoku dazu zu erstellen, aber da gab es immer irgend eine andere Option, um ans Ziel zu kommen. Allerdings hab ich geschafft ein Killer-Sudoku zu basteln, das diese Geometrie ausnutzt, nur ist der nötige Trick fast unmöglich zu sehen, wenn man ihn nicht kennt. Deswegen werde ich es nicht ins Portal stellen. Nachdem du danach gefragt hast, Rob, zeige ich es aber natürlich gerne:
[Bild: bild.php?data=beef4cfd-6206-3030303343332d35]
Die Farben haben keinerlei Bedeutung, sie sind nur zur Unterscheidung der Käfige da. Ich glaube, dass dieses Rätsel ohne den Trick nur unter massivem Einsatz von T&E lösbar ist.
Zitieren
#8
(12.04.2020, 00:55)Realshaggy schrieb: Standard-Sudoku sind eh eine Kunst für sich, die ich nicht ansatzweise beherrsche. Ich schaffe es noch nicht mal bei einfacheren Schlussweisen, die ich einbauen möchte, diese später nicht kaputtzumachen. Bei Varianten ist das irgendwie viel einfacher.
DANKE! Ich hab nicht den Hauch einer Ahnung, wie man ein gutes klassisches Sudoku erstellt - ich vermute mal, mit einer Tonne Intuition und noch mehr Trial and Error. Ich bin froh, dass ich damit nicht alleine bin.
(12.04.2020, 00:55)Realshaggy schrieb: Du hattest noch nach anderen Beispielen gefragt. Vor einigen Jahren (das müßte mindestens vor 2011 gewesen sein, weil ich in dem Jahr mal ein Rätsel dazu gebaut habe) hat Roland Voigt (hausigel) mal etwas über Lateinische 6x6-Quadrate mit zusätzlicher Diagonalenbedingung geschrieben. Entweder in seinem damaligen Blog oder einem Artikel in unserer Mitgliederzeitschrift, ich weiß es nicht mehr. Jedenfalls gibt es da mehrere Gruppen aus vier Feldern, die dieselben Ziffern enthalten und diese Ziffern sind, wenn ich mich richtig erinnere, auch noch alle verschieden (trotz dass sie so liegen, dass das erstmal nicht zwingend aussieht). Er hat keinen logischen Beweis gefunden, aber es ließ sich mit Fallunterscheidung noch komplett verifizieren. Wenn man das weiß, wird dieses Rätsel etwas einfacher, auch wenn man es auch anders lösen kann: https://logic-masters.de/Raetselportal/R...&id=0001DH
Dankeschön, Christoph!
Zitieren
#9
Es geht auch ohne jegliches T&E, und hat meines Erachtens auch einen sehr schönen Lösungsweg - stell es ruhig ins Portal, dann skizziere ich meinen Lösungsweg als versteckten Kommentar.

Gemessen an den sonstigen Portalrätseln finde ich es auch nicht übermäßig schwer, sicher nicht mehr als drei Sterne.
Zitieren
#10
Also im Gegensatz zu Ulrich komme ich da nicht besonders weit (ohne das beschriebene Argument).
Zitieren


Möglicherweise verwandte Themen...
Thema Verfasser Antworten Ansichten Letzter Beitrag
  First Sudoku, Solvers Wanted Big Tiger 9 388 15.05.2020, 21:22
Letzter Beitrag: Big Tiger
  What is a Sudoku? CHalb 0 278 23.04.2020, 12:53
Letzter Beitrag: CHalb
  Sudoku-Bücher Wolbecker1 2 1.628 30.09.2019, 11:59
Letzter Beitrag: Wolbecker1
  Sudoku - Helft mir! karina 4 1.738 17.07.2019, 23:01
Letzter Beitrag: karina
  Neuer Puzzle-Blog logik66 5 8.891 05.09.2017, 23:14
Letzter Beitrag: JonaS2010

Gehe zu:


Benutzer, die gerade dieses Thema anschauen: 1 Gast/Gäste