Sodoku-Möglichkeiten < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wie viele Möglichkeiten gibt es, ein Sodoku-Feld - in dem in der ersten Zeile bereits die Ziffern 1 bis 9 fortlaufend eingetragen sind - so zu füllen, dass ein "Sodoku" daraus entsteht?
Erläuterung:
Die Einschränkung hinsichtlich der ersten Zeile habe ich deswegen vorgenommen, damit man nicht einfach die Ziffern gegenseitig austauscht. Dadurch würde ja kein "neues" Sudoku entstehen. |
Obwohl es beim Schach - im Gegensatz zum Fußball (siehe frühere Diskussion) eine endliche Anzahl an Spielmöglichkeiten gibt, hat aber wohl noch niemand diese Anzahl auch nur näherungsweise ermittelt.
Beim Sodoku dürfte die Anzahl möglichen Kominationen jedoch noch wesentlich kleiner sein. Selbst wenn es überhaupt keine Regeln gäbe, könnte man ein Neun-mal-neun-Feld ja nur auf maximal [mm] 9^{81} [/mm] Arten füllen.
Die Einschränkungen (jede Ziffer darf pro Block / Zeile / Spalte jeweils nur ein einziges Mal vorkommen) dürfte die Anzahl der Möglichkeiten radikal reduzieren.
Aber wie viele sind das annähernd?
|
|
| |
|
> Wie viele Möglichkeiten gibt es, ein Sodoku-Feld - in dem
> in der ersten Zeile bereits die Ziffern 1 bis 9 fortlaufend
> eingetragen sind - so zu füllen, dass ein "Sodoku" daraus
> entsteht?
Interessanterweise kann man dir auf diese Frage eine
präzise Antwort geben. Nach ![[]](/images/popup.gif) Wikipedia/Sudoku
gibt es 6.670.903.752.021.072.936.960 verschiedene
(vollständig ausgefüllte) Standard-Sudokus.
Diese Berechnung stammt von einem gewissen
Bertram Felgenhauer (2005). Wenn du die erste
Zeile vorgibst, müsste man die Anzahl durch 9!
dividieren. Es bleiben immer noch etwa [mm] 1.84*10^{16} [/mm]
fertige Sudokus übrig. Je nach der Auswahl der zu
löschenden Felder erhöht sich aber die Anzahl der
möglichen unterschiedlichen Sudoku-Spiele aber
wieder ganz, ganz gewaltig.
> Beim Sodoku dürfte die Anzahl möglichen Kombinationen jedoch
> noch wesentlich kleiner sein. Selbst wenn es überhaupt
> keine Regeln gäbe, könnte man ein Neun-mal-neun-Feld ja nur
> auf maximal [mm]9^{81}[/mm] Arten füllen.
Die Ausdrucksweise "nur" [mm]9^{81}[/mm] zeugt davon, dass du
aber auch gar keinen Respekt vor astronomischen
Zahlen hast ... 
Die Anzahl der Atome im gesamten sichtbaren Universum
liegt etwa in der Grössenordnung [mm] 10^{80}.
[/mm]
Über die Komplexität von Schach hat sich Claude Shannon
schon vor etwa 60 Jahren Gedanken gemacht:
http://en.wikipedia.org/wiki/Shannon_number
Gruß al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:40 Fr 02.01.2009 | | Autor: | rabilein1 |
Danke, dass du dir die Mühe gemacht hast, das auszurechnen - äähh rauszusuchen.
Ich hätte nicht gedacht, dass es dermaßen viele Kombinations-Möglichkeiten beim Sudoku geben würde (für mich sehen die alle irgendwie gleich aus).
Andererseits sind [mm] 10^{16} [/mm] Sudokus im Vergleich zu [mm] 9^{72} [/mm] willkürliche Zahlen etwa so wie ein Atom im Vergleich zur Erde.
(Neun Felder waren ja bereits fest vorgegeben)
P.S.
Vor großen Zahlen habe ich schon Respekt. Andererseits erscheinen auch diese wiederum klein im Vergleich zur Unendlichkeit.
|
|
|
|
