Wie viele mögliche 4x4-Sudokus gibt es?
Hallo,
Ich habe mir die Frage gestellt, wie viele 2x2-Sudokus es gibt, bin aber mit meinen Kombinatorikkenntnissen nicht weit gekommen.
Die Regel soll einfach sein: Man trage so die Zahlen 1 bis 4 in das Gitter, dass in jeder Zeile, jeder Spalte und jedem der 4 2*2-Quadrate jede Zahl genau einmal vorkommt.
Danke im Vorraus!
1 Antwort
Zugegeben, ich habe mir zuerst ein Rechnerprogramm geschrieben, damit ich weiß, was mich hier erwartet. Es gibt ja etwa 4 Milliarden Möglichkeiten, die Ziffern irgendwie einzutragen (ohne Berücksichtigung irgendwelcher Regeln).
In die erste Zeile können wir die 4 Ziffern in beliebiger Reihenfolge eintragen. Dafür gibt es 4! = 24 Möglichkeiten. Diese Möglichkeiten sind alle gleichwertig. Wir entscheiden uns für 1234, wohl wissend, dass es 24 mal so viele Möglichkeiten gibt.
In der zweiten Zeile müssen 3 und 4 in den linken und 1 und 2 in den rechten beiden Kästchen stehen. Also gibt es vier Möglichkeiten:
1 2 3 4 / 1 2 3 4 / 1 2 3 4 / 1 2 3 4 (erste Zeile)
3 4 1 2 / 3 4 2 1 / 4 3 1 2 / 4 3 2 1 (zweite Zeile)
Für jede dieser vier Fälle gibt es in der dritten Zeile wieder vier Möglichkeiten
2 1 4 3 / 2 1 4 3 / 3 1 X X / 2 1 4 3 (dritte Zeile, Variante 1)
4 1 2 3 / 4 1 X X / 2 1 4 3 / 3 1 4 2 (dritte Zeile, Variante 2)
2 3 4 1 / 2 3 X X / 3 4 2 1 / 2 4 1 3 (dritte Zeile, Variante 3)
4 3 2 1 / 4 3 1 2 / 2 4 X X / 3 4 1 2 (dritte Zeile, Variante 4)
Ein X bedeutet, dass es keine Lösung gab.
Die passenden vierten Zeilen sind
4 3 2 1 / 4 3 1 2 / X X X X / 3 4 1 2 (vierte Zeile, Variante 1)
2 3 4 1 / X X X X / 3 4 2 1 / 2 4 1 3 (vierte Zeile, Variante 2)
4 1 2 3 / X X X X / 2 1 4 3 / 3 1 4 2 (vierte Zeile, Variante 3)
2 1 4 3 / 2 1 4 3 / X X X X / 2 1 4 3 (vierte Zeile, Variante 4)
Man sieht, dass die Bedingungen für das Sudoku von allen diesen 12 Möglichkeiten erfüllt sind.
Es gibt also insgesamt 24 * 12 = 288 Möglichkeiten, das Sudoku auszufüllen.
Ich versuche es mal auch für ein 9x9-Sudoku, aber nicht mehr heute abend ;-)
Ich hab's versucht (Rechnerprogramm zum Ausprobieren), aber ich musste den Versuch abbrechen. Dann habe ich Google gefragt, es gibt etwa 6,7 Trilliarden (6,7 * 10^21) Möglichkeiten.
Also: Erst lesen, dann programmieren ;-)
Warum die Formel mit den Fakultäten für 4*4 funktioniert und für 9*9 nicht, ist mir auch unklar.
Und warum sie trotzdem für 9*9 zumindest die richtige Größenordnung liefert, ist mir erst recht unklar.
Vielen Dank @tunik123
Ich habe die Aufgabe mehrmals probiert und kam letzten Endes auf 21504 Lösungen.
Allerdings hatte ich in einem Versuch, den ich später verworf, auch das Ergebnis 288. Denn 288=4!*3!*2!*1!
Als ich jetzt Ihre Lösung gelesen hatte, dachte ich mir, es wäre schön, wenn dies auch für 9x9 gelten würde. Tatsächlich liegt das vermutete Ergebnis im Bereich um 10^21, es unterscheidet sich von der Realität nur um den Faktor 3,6355016969, was recht wenig ist.