27.01.2009, 13:10
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
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
