Ähnliche Sudokus und Isomorphie
Wenn man bei einem Sudoku jede 1 durch 2 ersetzt und umgekehrt, ändert sich an der Logik des Spiels nicht.
Zwei Sudokus, die der gleichen Logik folgen, nennt man "ähnlich" oder, wenn man gebildet klingen will, "isomorph".
Anzahl
Zu jedem Sudoku gibt es 2*9!*68 = 1218998108160 ähnliche Sudokus, das ursprüngliche Sudoku mitgezählt.
Im folgenden ist beschrieben, wie man auf diese Zahl kommt, und was man einem Sudoku antun kann, ohne die Logik dahinter zu verändern.
Transposition
-
- Beim Transponieren werden die Zahlen oben rechts mit den unten links vertauscht, es wird also an der Mitteldiagonalen gespiegelt. Dabei bleibt die Logik des Spiels erhalten.
Der Vorgang, bei dem die Zahlen Rechts oben und links unten vertauscht werden, heißt Transposition. In der Grafik oben ist dies für die ersten paar Zahlen angedeutet.
Wenn man ein Sudoku zweimal transponiert, kommt wieder das ursprüngliche Feld heraus. Daher verdoppelt die Transposition die Anzahl der möglichen Sudoku: eine originale und eine transponierte Version.
Man sollte beachten, dass man auch Zahlen mit leeren Zellen vertauschen kann und muss.
Vertauschen von Zeilen und Spalten
Wenn man innerhalb eines Blocks die Spalten vertauscht, so verändert man damit die Logik des Spiels nicht.
-
- Beim Vertauschen von Zeilen oder Spalten innerhalb eines 3x3-Blocks bleibt die Logik des Spiel unverändert.
Innerhalb eines Blocks kann man die erste Spalte an drei möglichen Orten positionieren, die zweite an zwei möglichen Orten (alle außer dort, wo die erste Spalte hingesetzt wurde), und der Ort für die dritte Spalte ist dann vorgegeben. Man hat also pro Block sechs Möglichkeiten.
Da man pro Zeile und pro Spalte je drei Blöcke hat, erzeugt man durch das Vertauschen von Zeilen und Spalten 66 Möglichkeiten.
Vertauschen von Blöcken
Man kann Blöcke aus drei aneinanderliegenden Zeilen oder Spalten miteinander vertauschen, wie oben abgebildet.
Aus den gleichen Überlegungen wie oben folgt, dass man für das Zeilen- und spaltenweise Vertauschen der Blöcke jeweils Sechs Möglichkeiten hat, insgesamt also 6*6.
Permutationen
Man kann einzelne Buchstaben mit anderen Zahlen vertauschen. Dabei kann man jedoch nicht wie bisher Zahlen mit leeren Zellen vertauschen.
Man kann z.B. jede Acht durch eine Drei ersetzen, jede Drei durch eine Fünf, und jede Fünf durch eine Acht.
Aus der Eins kann eine der Neun Zahlen werden, für die Zwei gibt es noch die acht verbleibenden Möglichkeiten usw. Insgesamt gibt es also 9*8*7*6*5*4*3*2*1 = 9! Möglichkeiten.
Durch permutieren kann man übrigens jedes voll besetzte Sudoku in die Form bringen, dass der Erste Block die Zahlen von 1 bis 9 in aufsteigender Reihenfolge hat:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Oder man kann es so umformen, dass die erste Zeile die Zahlen 1 bis 9 in aufsteigender Reihenfolge enthält.
Zusammenfassung
Es gibt 2 Möglichkeiten aus der Transposition, 66 Möglichkeiten aus dem Vertauschen von Zeilen und Spalten, 6*6 Möglichkeiten aus dem blockweise Vertauschen von Zeilen und Spalten sowie 9! Möglichkeiten aus dem Permutieren der Zahlen.
Alles zusammen sind das 2*68*9! = 1218998108160 Ähnliche Sudoku, also Sudoku, die der gleichen Logik folgen.
top