Permutationen und Freiheitsgrade bei Sudoku

23/08/2013 - 06:37 von Marcus Glöder | Report spam
Hallo alle zusammen,

in meiner Freizeit spiele ich gerne Sudoku und mir ist ein kleines
Problem eingefallen, mit dem ich mich gerade beschàftige. Eigentlich
geht es dabei um zwei verschiedene Fragestellungen:

1.
Wieviele verschiedene gelöste Sudokus sind bei einer gegebenen
Sudoku-Größe (Anzahl der Zeilen, Spalten und Quadranten) möglich (Anzahl
der Permutationen,[1] die der Regel entsprechen, dass jede Ziffer pro
Zeile, Spalte und Quadrant genau einmal vorkommen muss)?

2.
Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
vorgegeben werden, damit alle anderen Zellen determiniert und das Sudoku
damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
Zusatzfrage: wie müssen die vorgegebenen Zellen verteilt sein, damit
möglichst wenig davon benötigt werden? Oder spielt das keine Rolle?

Das kleinste mögliche Sudoku hat 4x4 Felder. Die vier Quadranten
benenne ich jetzt mal so:

ab
cd

und die Felder so:

a1 a2 b1 b2
a3 a4 b3 b4

c1 c2 d1 d2
c3 c4 d3 d4

Die Felder habe ich also nach den Quadranten benannt, in denen sie
liegen. Bei anderen Sudoku-Größen, beispielsweise mit 6x6, 9x9
(Standard) oder 16x16 Feldern, erfolgt die Benennung dann entsprechend.[3]

Im kleinsten Fall, einem 4x4-Sudoku, sind beide Fragen ohne viel
Mathematik noch recht einfach zu bestimmen. Was die Freiheitsgrade
betrifft, so sind das 4, nàmlich 1 Freiheitsgrad in jedem Quadrant. Die
Anzahl der Permutationen làsst sich sukzessive bestimmen, sozusagen
Quadrant für Quadrant. Wenn ich bei Quadrant a anfange, dann hat dieser
Quadrant für sich genommen 1*2*3*4=4!$ Permutationen. In Quadrant b
gibt es jetzt in der oberen Zeile (Zellen b1 und b2) zwei Permutationen,
weil durch die Zellen a1 und a2 schon zwei Ziffern vergeben sind, und in
der unteren Zeile (Zellen b3 und b4) aus demselben Grund (durch die
Zellen a3 und a4 sind schon zwei Ziffern, nàmlich die beiden, die in den
Zellen a1 und a2 nicht stehen, vergeben) ebenfalls zwei, macht zusammen
also vier Permutationen in Quadrant b. Ganz entsprechend ist das bei
Quadrant c. Auch hier habe ich, aus demselben Grund, wie bei Quadrant b,
vier Permutationen. Wenn die Quadranten b und c festgelegt sind, ist
Quadrant d determiniert. Es gibt also (wenn ich das richtig sehe) in
einem 4x4-Sudoku

4!*(2*2!)*(2*2!)$*4*484

Permutationen. Soweit ist das alles ganz einfach. Wie sieht es aber bei
größeren Sudokus (wie 6x6, 9x9 oder 16x16) aus? Kann die demonstrierte
Vorgehensweise im Prinzip übertragen werden und was wàre ggf. zu beachten?

Viele Grüße
Marcus


–––>
Eine Randbemerkung sei mir gestattet. Mir ist aufgefallen, dass es in
dieser NG offenbar seit Jahren gut gepflegte Feindschaften, mit
ellenlangen Flamewars und einem etwas ruppigen Ton (um das mal so zu
sagen) gibt. Deshalb möchte ich vorsichtshalber sagen, dass Diskussionen
über »binàre Bàume« oder »Matheologie« hier wirklich /off topic/ sind
und bitte in andere Threads verlagert werden sollten.
<–––


Anmerkungen

[1]
Vgl. http://de.wikipedia.org/wiki/Permut...ederholung

[2]
Das Wort »Freiheitsgrade« habe ich aus einem anderen Zusammenhang
geklaut, nàmlich dem Chi-Quadrat-Test. Dabei geht es um die Anzahl von
Zellen in einer Kreuztabelle, die bei gegebenen Randverteilungen relativ
(in den Grenzen, die die Randverteilungen vorgeben) frei festgelegt
werden können, bevor alle anderen Zellen determiniert sind.
Vierfeldertafeln haben 1 Freiheitsgrad, 3x3-Tabellen 4 Freiheitsgrade
usw. Allgemein ist in diesem Zusammenhang (Chi-Quadrat-Test) die Anzahl
der Freiheitsgrade df = (r-1)*(c-1), wenn r die Anzahl der Zeilen und c
die Anzahl der Spalten ist. Vgl. dazu beispielsweise Borz 2005:173,
Claus/Ebner 1968:239–240 oder Sahner 1982:135

[3]
6x6 ist eine Art Zwischengröße, die ich auf der Kinderseite der
Rheinischen Post gesehen habe. Dabei sind die Quadranten nicht
quadratisch, sondern haben zwei Zeilen und drei Spalten. Es liegen zwei
Quadranten nebeneinander und drei Quadranten untereinander. Das Ganze
sieht also so aus:

a1 a2 a3 b1 b2 b3
a4 a5 a6 b4 b5 b6

c1 c2 c3 d1 d2 d3
c4 c5 c6 d4 d5 d6

e1 e2 e3 f1 f2 f3
e4 e5 e6 f4 f5 f6


Literatur

Bortz, Jürgen, (6)2005: Statistik für Human- und Sozialwissenschaftler.
Heidelberg: Springer

Claus, Günter und Heinz Ebner, 1968: Grundlagen der Statistik für
Psychologen, Pàdagogen und Soziologen. Berlin: Volk und Wissen

Sahner, Heinz, (2)1982; Statistik für Soziologen 2. Schließende
Statistik. (= Teubner Studienskripten 23) Stuttgart: Teubner

PMs an: m.gloeder@gmx.de
 

Lesen sie die antworten

#1 Bergholt Stuttley Johnson
23/08/2013 - 11:27 | Warnen spam
Ein paar Antworten findest du in:
http://www.amazon.de/dp/0199756562


fix$(<$>)<$>(:)<*>((<$>((:[])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1

Ähnliche fragen