+- Logic Masters Forum (https://forum.logic-masters.de)
+-- Forum: Allgemeines (https://forum.logic-masters.de/forumdisplay.php?fid=3)
+--- Forum: Rätseldiskussionen (https://forum.logic-masters.de/forumdisplay.php?fid=13)
+--- Thema: Gibt es ein Ur-Sudoku? (/showthread.php?tid=296)
Seiten:
1
2
Gibt es ein Ur-Sudoku? - eric - 25.11.2008
Hi!
Ich frage mich, ob es möglich ist, alle möglichen Sudokus (alle Felder bereits ausgefüllt), durch Vertauschen von Zeilen und Splaten oder Zahlen oder Blöcken auf ein Ur-Sudoku zurückzuführen?
Mit "Vertauschen von Zahlen" ist gemeint: Nimm alle 5er und ersetze sie durch 7er und alle 7er und ersetze sie durch 5er.
Kann man also zum Beispiel
123 456 789
456 789 123
789 123 456
234 567 891
567 891 234
891 234 567
345 678 912
678 912 345
912 345 678
durch irgendwelche Drehungen und Vertauschungen in JEDES gültige, gelöste Sudoku überführen?
Bin gespannt auf Lösungsansätze oder den Gegenbeweis, denn bei mir klappt's nicht.
Bis dann, Eric
p.s.: Ich habe die Frage schon in mehreren anderen Foren gestellt, aber noch keine befriedigende Lösung bekommen. Also wundert euch nicht, wenn google diese Topic bereits kennt.
RE: Gibt es ein Ur-Sudoku? - uvo - 25.11.2008
Nein, geht nicht.
Frage: Wieviele verschiedene Sudokus kann man aus deinem Ur-Sudoku durch die von dir genannten Operationen erzeugen? Dazu muß man sich überlegen, welche derartigen Operationen überhaupt möglich sind:
1) Man kann das gesamte Sudoku um 90°, 180° oder 270° drehen. Aus einem Sudoku entstehen damit vier verschiedene, macht also einen Faktor 4.
2) Man kann das gesamte Sudoku spiegeln; da wir Drehungen bereits berücksichtigt haben, ist es egal, an welcher Achse wir spiegeln - Faktor 2.
3) Wenn wir das Diagramm in drei Blöcke zu je drei Zeilen zerlegen, können wir diese Blöcke beliebig permutieren; dafür gibt es 3!=3*2*1=6 Möglichkeiten. Innerhalb jedes Blocks können die je drei Zeilen ebenfalls beliebig permutiert werden, das ergibt noch dreimal den Faktor 3!. Insgesamt ergibt sich also ein Faktor (3!)^4 = 1296.
4) Das Gleiche gilt natürlich analog für die Spalten, ergibt nochmal den Faktor 1296.
5) Und schließlich können wir die Ziffern beliebig permutieren, damit erhalten wir den Faktor 9! = 362880.
(Ich hoffe, ich habe nichts vergessen...)
Aus einem komplett ausgefüllten Sudoku erhalten wir also insgesamt
4*2*1296*1296*362880 = 4.875.992.432.640 verschiedene (ausgesprochen: fast 5 Billionen).
Ein Mathematiker hat jedoch mal ausgerechnet, daß es insgesamt 6.670.903.752.021.072.936.960 (über 6 Trilliarden) verschiedene komplett gelöste Sudoku gibt (Quelle: Wikipedia). Die können also bei weitem nicht alle aus einem Ur-Sudoku stammen.
Grüße,
uvo
RE: Gibt es ein Ur-Sudoku? - eric - 25.11.2008
Die Antwort ist gut... wirklich gut! Damit kann man erstmal zufrieden sein...
Aber genau das:
(25.11.2008, 14:55)uvo schrieb: (Ich hoffe, ich habe nichts vergessen...)ist ein Haken! Vielleicht gibt es ja noch andere Aktionen, mit denen man die Anordnung der Zahlen legal vertauschen kann.
Aber danke für die Antwort. Sieht alles logisch und schlüssig aus!
Eric
RE: Gibt es ein Ur-Sudoku? - tyskhubi - 25.11.2008
Jetzt sind wir an der Stelle, wo wieder die Betrachtungsweise ins Spiel kommt. Es gibt noch einige weitere legale Operationen, mit denen man Sudokus erzeugen kann. Beispielsweise wenn man ein Rechteck mit jeweils zwei gleichen Zahlen an den Ecken hat können diese paarweise vertauscht werden. Diese Vertauschung muss sich meiner Meinung nach nicht durch die von uvo aufgezählten Manipulationen bewerkstelligen lassen.
Wir haben also eine weitere Manipulation gefunden, bei der allerdings 4 Zahlen im Spiel sind. Jetzt kann man mit entsprechendem Aufwand noch mehr solcher Manipulationen finden, und mit deren Hilfe kann man wirklich alle Sudokus erzeugen (Im Zweifelsfall durch eine Permutation die 81 Zahlen tatsächlich verändert...)
Die Frage, ob es ein Ur-Sudoku gibt, hat also zur Antwort dass jedes Sudoku ein Ur-Sudoku ist.
Ich hoffer wiederum, ich habe keinen Fehler in der Argumentation gemacht.
Hubert
RE: Gibt es ein Ur-Sudoku? - eric - 25.11.2008
Okay... das, wenn es ein Ur-Sudoku gibt, jedes Sudoku ein Ur-Sudoku ist, ist klar...
Aber das mit dem Rechteck verstehe ich überhaupt nicht. Soll nicht heißen, daß ein Fehler in deiner Überlegung ist - ich versteh's schlicht und ergreifend nicht.
Ist ein Rechteck bei dir eine 3x3-Box oder einfach irgendwas? Und welche Zahlen an den Ecken meinst du. ich kann's mir irgendwie nicht vorstellen...
Grüße, Eric
RE: Gibt es ein Ur-Sudoku? - uvo - 25.11.2008
Ich nehme an, er meint folgendes:
Stell dir vor, du hast ein Sudoku, wo beispielsweise irgendwo das folgende Muster vorkommt:
8XXX2
XXXXX
XXXXX
2XXX8
Hier kannst du offenbar die 2er und 8en vertauschen. Die Frage ist: Zählen solche Operationen ebenfalls als "aus dem Ur-Sudoku entstanden"?
Oder mit einem etwas komplizierten Beispiel:
67XXX
XXXXX
7XXX6
X6XX7
Wäre so etwas auch erlaubt im Sinne deiner Fragestellung?
Wenn ja: Wie kompliziert darfs denn werden? Letztendlich entstehen ja alle Sudokus aus einem Ur-Sudoku dadurch, daß alle 81 Ziffern auf geeignete Weise vertauscht werden
Grüße,
uvo
RE: Gibt es ein Ur-Sudoku? - eric - 25.11.2008
Ja, sowas soll auch erlaubt sein. Dann scheint es aber recht schnell sehr kompliziert zu werden.
Aber: Man kann sich schonmal die drei oberen/mittleren/unteren Blöcke nehmen und dann zwei Zahlen aus einer der drei SPALTEN von Block eins nehmen und vertauschen. in Block zwei und drei macht man das das gleiche -> ein "neues" Sudoku.
Außerdem kann man die drei linken/mittleren/rechten Blöcke nehmen und zwei Zahlen einer ZEILE tauschen.
Super Taktik!!! Funktioniert aber glaube ich nur innerhalb von Blöcken und nicht blockübergreifend - oder?!?
Hier unten darf ich ja zum Beispiel nicht die 1er gegen die 9er tauschen, denn bei dem "y" könnte ja eine "9" stehen!
1xx xxx xx9
xxx xxx xxx
xxy xxx xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx
xxx xxx xxx
9xx xxx xx1
RE: Gibt es ein Ur-Sudoku? - eric - 26.11.2008
wow... wenn man tyskhubi's bzw. uvo's idee nimmt, dann explodieren die möglichkeiten ja förmlich!
a23 b56 789
b56 789 a23
789 a23 b56
234 567 891
567 891 234
891 234 567
345 678 912
678 912 345
912 345 678
hier kann a=1||4 und folglich b=4||1 sein. da sind es in den ersten drei zeilen schon 9 verschiedenen sudokus. nochmal 9 mit den zweiten drei reihen und 9 mit den dritten - macht einen faktor 729 mehr. dann das gleiche noch mit den spalten macht nochmal 729 mehr. dann kann ich ja auch noch in den ersten drei zeilen tauschen und zusätzlich in den zweiten drei- macht nochmal 9*9 mehr, usw...
damit sollte man doch zumindest in die nähe von 6,6 trilliarden kommen. das scheint ziemlich ultimativ zu sein!
dann mal gute nacht
RE: Gibt es ein Ur-Sudoku? - berni - 26.11.2008
(26.11.2008, 02:11)eric schrieb: wow... wenn man tyskhubi's bzw. uvo's idee nimmt, dann explodieren die möglichkeiten ja förmlich!
Ja, wie schon mehrfach geschrieben: Wenn ich Operationen zulasse, bei denen man einfach alle Ziffern irgendwie so vertauscht, dass dabei wieder ein Sudoku - besser: Eine Sudokulösung - herauskommt, kann man natürlich alle möglichen Sudokulösungen erhalten.
Was ich viel spannender finde, ist, nur Operationen zu betrachten, bei denen auch der Lösungsweg eines Sudoku (bei dem natürlich noch nicht alle Ziffern vorgegeben sind) erhalten bleibt. Wenn ich beispielsweise die erste und zweite Zeile eines Sudoku vertausche, dann habe ich ein neues Sudoku, bei dem aber der Lösungsweg einfach der selbe bleibt (man muss halt nur überall, wo im Lösungsweg die erste Zeile vorkommt, die zweite Zeile nehmen und umgekehrt).
Bei der Operation von Tykshubi ist das nicht der Fall. Da kann es passieren, dass das neue Sudoku keine Lösung mehr besitzt, oder mehrere, oder aber auch dass sich der Lösungsweg (und damit der Schwierigkeitsgrad) ändert.
Die erste Antwort von Uvo bezog sich, soweit ich das sehen kann, genau auf diesen Fall. Da gibt es meiner Meinung nach auch keine weiteren Operationen mehr, die man noch verwenden kann.
RE: Gibt es ein Ur-Sudoku? - Statistica - 26.11.2008
(26.11.2008, 09:20)berni schrieb: Was ich viel spannender finde, ist, ...
Was auch spannend wäre, mal DAS tatsächliche Ur-Sudoku zu finden, also jenes, was zuerst unter diesem (westlichen) Namen in einer Zeitung abgedruckt wurde. Laut Wikipedia: "Im September 2004 veröffentlichte Gould sein erstes Sudoku in der Conway Daily Sun." Bin mal gespannt, ob man das noch auftreiben kann. Wäre ja eine kleine Ikone der Sudoku-Freunde
. Könnte man bestimmt ins Mathematikum stellen.Nachtrag: Das Rätsel gab es sicherlich schon früher. Aber wann wurde es (außerhalb Japans) "Sudoku" genannt und auch unter diesem Namen abgedruckt??
Historisch interessiert: Jörg