Orthogonales Sudoku/Lateinisches Quadrat

[Naphthalin]

Hallo ihr,

auf Bitte von Statistica eröffne ich einfach mal einen Thread zum Thema "Orthogonale Sudoku" bzw. "Orthogonale lateinische Quadrate".

Zuerst einmal: Was sind das für Quadrate?
Orthogonale Lateinische (bzw. Griechisch-Lateinische) Quadrate sind ein Paar von nxn-Quadraten, sodass jeweils in jeder Zeile/Spalte die Zahlen 1 bis n vorkommen. Die Orthogonalität fordert darüber hinaus, dass beim Übereinanderlegen der beiden Quadrate jede Paarung (11,12,13,...,1n,21,...,n1,...,nn) genau einmal vorkommt. Euler stellte dies mit griechischen und lateinischen Buchstaben dar, daher auch der Name. Für die SuDoKu gilt natürlich für beide Quadrate noch die Gebietsregel.

Man sieht leicht ein, dass es für n=2 kein solches Paar gibt, auch für n=6 gibt es keins (darauf hat uvo angespielt, im Internet findet man zum Beispiel unter dem Stichwort "Problem der 36 Offiziere" näheres). Alle anderen n sind möglich.

Zu deiner Frage: Das mit "n-1 orthogonale lateinische quadrate" kann nicht stimmen, die zahl wird ziemlich schnell groß.

Nun zu den SuDoKu: In der Tat ist es mE sehr schwer, allein durch Zufall auf ein orthogonales Paar zu kommen. Für 4x4 existiert abgesehen von Isomorphie nur ein einziges, 6x6 existiert natürlich nicht. Für 5x5 und 7x7 hab ich mit verschiedenen symmetrischen Mustern experimentiert, da gibt es aber auch nichts. jetzt hab ich mir einfach per Programm (danke nochmal an pwahs) angefangen, alle orthogonalen 7x7-Quadrate ausgeben zu lassen und mir dann manuell ein Muster zu überlegen. Mal schauen^^
Bei 9x9 hab ich einfach auf gut Glück ein paar (vielleicht 10 oder 20) ausgefüllte Sudoku probiert, und nicht zu einem einzigen gab es ein orthogonales. Auch mit ein paar auf gut Glück eingetragenen Ziffern (knapp 20) hatte ich kein Glück und hab ein paar Versuche gebraucht, bis ich überhaupt ein komplett ausgefülltes orthogonales Sudoku hatte - für einfache Sudoku ja kein Ding.

Allerdings sollte ich vorher warnen: das eine Teilsudoku hat 300.000 Lösungen, das andere 1.500.000^^ aber allein durch die Orthogonalität reduziert sich das insgesamt auf 1

Naphthalin

[Statistica]

Zu deiner Frage: Das mit "n-1 orthogonale lateinische quadrate" kann nicht stimmen, die zahl wird ziemlich schnell groß.

Hi,

das ist richtig. Beim weiteren Nachforschen habe ich dann Folgendes gefunden:

"Ein lateinisches Quadrat für eine beliebige Ordnung n lässt sich leicht konstruieren. Die Frage der Existenz von griechisch-lateinischen Quadraten (=orthogonale lateinische Quadrate) der Ordnung n ist viel komplexer. Es ist bewiesen worden, dass es höchstens n - 1 paarweise orthogonale lateinische Quadrate der Ordnung n gibt. Die Existenz dieser maximalen Anzahl ist äquivalent zur Existenz einer endlichen projektiven Ebene der Ordnung n."

Also gibt es höchstens acht lateinische Quadrate der Ordnung 9, von denen jeweils zwei orthogonal zueinander sind. Ob man acht SUDOKUS mit dieser Eigenschaft findet, bezweifele ich...

Bei den Anzahlen der orthogonalen lateinischen Quadraten habe ich bisher nur Zahlen für n=3 (36) und n=4 (3456) gefunden.

Interessante Details zu den lateinischen Quadraten und anderen gibt es unter der mehrsprachigen Seite http://www.multimagie.com/indexdeut.htm

Ob ich mich noch mal an das orthogonale Sudoku mache, weiß ich nicht (in einem dreiwöchigen Urlaub auf einer einsamen Insel...? )

Gruß: Jörg

[lupo]

Hallo,

auch ich habe ich schon daran versucht, die besondere Struktur hier auszunutzen. Was vielleicht auch klappen könnte, wenn die Sudokus von Hand konstruiert wurden. Wenn sie aber mit Freund Computer gemacht wurden (und so haber ich Naphtalin jetzt verstanden), hat man so wahrscheinlich keine Chance.

Lateinische Quadrate zu konstruieren, ist in der Tat nicht schwer (d.h., wenn man weiß wies geht): Man setze in das Feld (x,y) die Zahl x+y (wenn die größer als die Größe des Quadrats wird, fängt man entsprechend von vorne an). Alle gleichen Zahlen liegen dann auf einer (versetzten) Diagonale, die aus dem Quadrat rausläuft und auf der anderen Seite wieder rein.

Um ein dazu orthogonales Quadrat zu bekommen, setzt man nach (x,y) die Zahl x+2y (entsprechend wie oben korrigiert). Gleiche Zahlen liegen dann auf Rösselsprung-Linien. Das klappt allerdings nur, wenn das Quadrat ungerade ist.

Sudokus bekommt man so allerdings nicht. Für Experten: Wenn man die Geraden nicht aus Z/9 wählt wie oben, sondern aus F9 (der Körper mit 9 Elementen), entstehen daraus Sudokus. Und zwar, wenn man will, 6 paarweise orthogonale.

Es ist bewiesen worden, dass es höchstens n - 1 paarweise orthogonale lateinische Quadrate der Ordnung n gibt.

Das ist auch relativ leicht einzusehen. Wählen wir die Quadrate so, dass links unten eine 1 steht (notfalls werden die Ziffern umbenannt!). Dann habi ich noch n-1 Stellen, an denen die 1 in der zweiten Zeile stehen kann. Aber die müssen alle verschieden sein, sonst ist die Orthogonalität dahin. Also gibt es höchstens n-1 oQs.

Also gibt es höchstens acht lateinische Quadrate der Ordnung 9, von denen jeweils zwei orthogonal zueinander sind. Ob man acht SUDOKUS mit dieser Eigenschaft findet, bezweifele ich...

Gleiches Argument wie oben, aber nur 6 mögliche Stellen, wegen der Gebietsregel. Also höchstens 6. Und die sind auch möglich, s.o. (es sei denn ich hätte mal wieder einen kapitalen Fehler gemacht: soll ja schon mal vorkommen!)

Was mir nicht klar ist:

Hat jedes lateinische Quadrat ein orthogonales?
Gibt es strukturelle Einschränkungen, oder wirkt sich die Struktur irgendwie auf das orthogonale "Double" aus?
Wie passt die Gebietsregel da rein?
Wenn man n-2 poQs hat, bekommt man dann automatisch auch das letzte?
Kann man irgendwelche Kombinationen bilden?
Ist das x-te orthogonale Q durch n-x Zeilen festgelegt? Und wenn ja: kann man die frei wählen?

Und noch eine Frage an Naphtalin: kannst du dein orthogonales Sudoku selber lösen?

Gruß Jürgen

[Naphthalin]

so viele fragen auf einmal^^

wenn du auf die art und weise lateinische quadrate konstruierst, könnte das für den löser langweilig werden

den beweis hab ich mir noch nicht angeschaut. das n-1 te lateinische quadrat ist (abgesehen von zahlenvertauschungen) eindeutig bestimmt.

es hat nicht jedes lateinische quadrat ein orthogonales (zB n=6).

und natürlich die interessante frage am schluss: ich glaube nicht, dass ich das sudoku selbst lösen könnte. allerdings war ich bei der DSM platz 28 oder so, insofern gibt es da eine ganze menge von leuten, die besser sind als ich - und wenn ich das per hand lösen kann, dann ist es für sie zu einfach^^ aber offensichtlich hab ich wie gesagt die schwierigkeit und komplexität unterschätzt.

ich hoffe, die antworten helfen dir weiter

Naphthalin

[Statistica]

und natürlich die interessante frage am schluss: ich glaube nicht, dass ich das sudoku selbst lösen könnte. allerdings war ich bei der DSM platz 28 oder so, insofern gibt es da eine ganze menge von leuten, die besser sind als ich - und wenn ich das per hand lösen kann, dann ist es für sie zu einfach^^ aber offensichtlich hab ich wie gesagt die schwierigkeit und komplexität unterschätzt.
Naphthalin

Ich denke, eine Sudoku-Meisterschaft ist immer auch ein sportlicher Wettkampf und macht keine Aussage darüber, wie GUT jemand Rätsel lösen kann. Ich denke, es gibt genug bessere Rätsler als ich, aber wenn es darum geht, ein Sudoku SCHNELL zu lösen, sind einige davon langsamer als ich. Kommt immer darauf an, wie man Rätsel rangeht.

Das Rätsel ist theoretisch sehr interessant, jedoch bleibt ein Nachgeschmack zurück, wenn es (bisher) niemanden gibt, der auch nur ansatzweise einen logischen Weg kennt (außer einer Latte von Fallunterscheidungen..), es zu lösen. Ich würde sagen, Ulrich zeigt uns die Lösung (und den Lösungsweg) beim Rätselwochenende

Damit es nicht allzu frustrierend wird: ich habe noch ein orthogonales Sudoku im Internet gefunden (von H.D.-Gronau, Seite 63)

http://www.iuk-verbund.uni-rostock.de/do...Sudoku.pdf

Apropos, wollte ich schon immer mal fragen: "Naphthalin" ??? Bist Du Micky-Maus-Fan ?

Gruß: Jörg

[Naphthalin]

genau dieses sudoku hat mich darauf gebracht, hier selbst eins einzustellen, allerdings ist mir das zu einfach und symmetrisch (ich glaub ihr wisst, was ich meine, wenn ihr es gelöst hab). übrigens ist dieses sudoku auch gar nicht von HDG selbst

Naphthalin

[uvo]

Ich würde sagen, Ulrich zeigt uns die Lösung (und den Lösungsweg) beim Rätselwochenende

Ich glaube, jetzt wäre der richtige Zeitpunkt, um zu erwähnen, daß ich nach zwei Stunden noch keine einzige Ziffer hatte und dann erstmal aufgegeben habe...

Grüße,
uvo

[Naphthalin]

Ich würde sagen, Ulrich zeigt uns die Lösung (und den Lösungsweg) beim Rätselwochenende

Ich glaube, jetzt wäre der richtige Zeitpunkt, um zu erwähnen, daß ich nach zwei Stunden noch keine einzige Ziffer hatte und dann erstmal aufgegeben habe...

Grüße,
uvo

Oje^^ dann wird das wohl so nichts.

Zu meiner Erstellungsweise: Ich bin von einem komplett ausgefüllten ausgegangen und habe solang Zahlen entfernt wie es noch eindeutig war. Ich vermute, das nächste Mal sollte ich so vorgehen, dass ich per Hand logische Zahlen rausschmeiße und dann vielleicht 4 oder 5 noch per Computer...

Naphthalin

[berni]

Zu meiner Erstellungsweise: Ich bin von einem komplett ausgefüllten ausgegangen und habe solang Zahlen entfernt wie es noch eindeutig war. Ich vermute, das nächste Mal sollte ich so vorgehen, dass ich per Hand logische Zahlen rausschmeiße und dann vielleicht 4 oder 5 noch per Computer...

Vorschlag: Du hast doch sicherlich noch die komplette Lösung. Wie wäre es, wenn du einfach mal versuchst, dein eigenes Rätsel von Hand zu lösen, und immer, wenn du nicht weiterkommst (z.B. ganz am Anfang), aus der Lösung eine Ziffer raussuchst, die dir weiterhilft?

Wir können dann das Rätsel im Portal durch das so entstandene ersetzen - ich denke, das dürfte das Rätsel deutlich interessanter machen.

[Statistica]

Ich glaube, jetzt wäre der richtige Zeitpunkt, um zu erwähnen, daß ich nach zwei Stunden noch keine einzige Ziffer hatte und dann erstmal aufgegeben habe...

Hi ulrich,

interessiert mich schon: suchst Du nach Ziffern oder checkst Du Kombinationen, also Zifferpaare? Letzeres erschien mir sinnvoller, wenn es auch dazu führen könnte, dass man nur Ziffern findet

Es ist bewiesen worden, dass es höchstens n - 1 paarweise orthogonale lateinische Quadrate der Ordnung n gibt.

Das ist auch relativ leicht einzusehen. Wählen wir die Quadrate so, dass links unten eine 1 steht (notfalls werden die Ziffern umbenannt!). Dann habi ich noch n-1 Stellen, an denen die 1 in der zweiten Zeile stehen kann. Aber die müssen alle verschieden sein, sonst ist die Orthogonalität dahin. Also gibt es höchstens n-1 oQs.

Mmmh. D.h. aber, dass es auch NEUN paarweise oLQs geben könnte, so wie es in der dritten Dimension auch drei Ebenen geben kann, die paarweise orthogonal sind. Das mit den n-1 ist ein Satz aus der projektiven Geometrie für diskrete Strukturen und wohl einfach zu beweisen. Muss mal sehen, ob ich es finde.
Und dass man sechs paarweise orthogonales 9x9-Sudokus konstruieren kann... Muss ich mal checken. Hoffentlich ist es so einfach wie von Dir beschrieben.

Gruß: Jörg