Ich habe mich vor einiger Zeit mal mit dem Thema beschäftigt und kam etwa zu den gleichen Ergebnissen wie uvo.
In der Tat gibt es 144 Möglichkeiten, eine Dame im Sudoku zu platzieren. Nach Positionen aufgeschlüsselt sieht das so aus:
08 15 24 | 14 22 14 | 24 15 08
15 12 18 | 17 20 17 | 18 12 15
24 18 10 | 15 10 15 | 10 18 24
-----------+------------+-----------
14 17 15 | 20 12 20 | 15 17 14
22 20 10 | 12 16 12 | 10 20 22
14 17 15 | 20 12 20 | 15 17 14
-----------+------------+-----------
24 18 10 | 15 10 15 | 10 18 24
15 12 18 | 17 20 17 | 18 12 15
08 15 24 | 14 22 14 | 24 15 08
Es gibt also z.B. nur 8 Möglichkeiten, die eine Dame in einer bestimmten Ecke haben, 16 mit einer zentralen Dame usw.
Nun ist natürlich interessant, welche der Konstellationen miteinander kompatibel sind, d.h. keine Dame an der gleichen Position haben. Man kann dafür einen Graph erstellen, wobei jeder Vertex eine der 144 Konstellationen ist und eine Kante dann existiert, wenn die entsprechenden Konstellationen kompatibel sind.
Wollen wir nun z.B. wissen, wie viele Damen maximal in ein Sudoku passen, so müssen wir die sog. maximalen Cliquen des Graphen bestimmen. Dies sind Mengen von Vertices, die alle miteinander verbunden sind und zu denen kein weiterer Vertex hinzugefügt werden kann, der auch noch mit allen anderen verbunden ist. Dafür gibt es Algorithmen, ich habe Bron-Kerbosch (mit pivoting) verwendet.
Die Zahl der maximalen Cliquen einer gewissen Größe sieht dann so aus:
2 -> 0
3 -> 52
4 -> 6918
5 -> 12000 (exakt)
6 -> 1652
7 -> 24
8 -> 0
Das ist so zu verstehen: Zu je zwei Damen kann immer eine Dritte hinzugefügt werden. Es gibt nur wenige (52) Möglichkeiten, drei Damen so anzuordnen, dass sie jegliche weitere Damen sperren. Das wird mit mehr Damen einfacher, bis bei 5 Damen ein sweet spot erreicht ist. Danach wird es jedoch schwierig, noch weitere Damen aufs Feld zu bringen.
Und tatsächlich gibt es 24 Möglichkeiten, 7 Damen zu platzieren. Von den 24 Möglichkeiten bleiben nur noch 6 übrig, wenn man Drehungen und Spiegelungen herausrechnet. Und Achtung: von diesen 6 erlauben 5 keine gültige Lösung für die restlichen beiden Ziffern.
Es gibt also (modulo Symmetrien und Permutationen der Ziffern) nur ein gültiges Sudoku mit 7 Damen und das sieht so aus:
2 0 5 | 4 7 3 | 6 1 0
0 7 3 | 6 1 2 | 4 0 5
6 1 4 | 5 0 0 | 3 7 2
-------+-------+-------
7 3 6 | 0 2 4 | 0 5 1
1 2 0 | 7 5 6 | 0 3 4
4 5 0 | 1 3 0 | 7 2 6
-------+-------+-------
3 6 2 | 0 0 5 | 1 4 7
5 0 1 | 3 4 7 | 2 6 0
0 4 7 | 2 6 1 | 5 0 3
Es hat allerdings 4 Lösungen, also müsste man noch zwei 8er/9er angeben um es eindeutig zu machen.
Was noch ganz interessant ist: Für manche Felder auf denen eine Dame ist, sind bestimmte andere Felder nichttrivial ausgeschlossen, z.B.
![[Bild: c9a7171344468776.jpg]](https://thumbs2.imagebam.com/62/34/33/c9a7171344468776.jpg)
Die Ziffern 1-0 geben dabei die 10 möglichen Konstellationen für die Dame in der "inneren Ecke" an. Alle roten Felder sind nichttrivial ausgeschlossen. Besonders an der Dame an dieser Position ist, dass immer eine weitere Dame einen Knightsmove nach außen weg sein muss, hier also in r1c4 oder r4c1. Das ist m.E. absolut nicht offensichtlich und ich habe auch keinen einfacheren Beweis dafür gefunden, als das Gegenteil nach ziemlich viel T/E zum Widerspruch zu führen.
In der Tat gibt es 144 Möglichkeiten, eine Dame im Sudoku zu platzieren. Nach Positionen aufgeschlüsselt sieht das so aus:
08 15 24 | 14 22 14 | 24 15 08
15 12 18 | 17 20 17 | 18 12 15
24 18 10 | 15 10 15 | 10 18 24
-----------+------------+-----------
14 17 15 | 20 12 20 | 15 17 14
22 20 10 | 12 16 12 | 10 20 22
14 17 15 | 20 12 20 | 15 17 14
-----------+------------+-----------
24 18 10 | 15 10 15 | 10 18 24
15 12 18 | 17 20 17 | 18 12 15
08 15 24 | 14 22 14 | 24 15 08
Es gibt also z.B. nur 8 Möglichkeiten, die eine Dame in einer bestimmten Ecke haben, 16 mit einer zentralen Dame usw.
Nun ist natürlich interessant, welche der Konstellationen miteinander kompatibel sind, d.h. keine Dame an der gleichen Position haben. Man kann dafür einen Graph erstellen, wobei jeder Vertex eine der 144 Konstellationen ist und eine Kante dann existiert, wenn die entsprechenden Konstellationen kompatibel sind.
Wollen wir nun z.B. wissen, wie viele Damen maximal in ein Sudoku passen, so müssen wir die sog. maximalen Cliquen des Graphen bestimmen. Dies sind Mengen von Vertices, die alle miteinander verbunden sind und zu denen kein weiterer Vertex hinzugefügt werden kann, der auch noch mit allen anderen verbunden ist. Dafür gibt es Algorithmen, ich habe Bron-Kerbosch (mit pivoting) verwendet.
Die Zahl der maximalen Cliquen einer gewissen Größe sieht dann so aus:
2 -> 0
3 -> 52
4 -> 6918
5 -> 12000 (exakt)
6 -> 1652
7 -> 24
8 -> 0
Das ist so zu verstehen: Zu je zwei Damen kann immer eine Dritte hinzugefügt werden. Es gibt nur wenige (52) Möglichkeiten, drei Damen so anzuordnen, dass sie jegliche weitere Damen sperren. Das wird mit mehr Damen einfacher, bis bei 5 Damen ein sweet spot erreicht ist. Danach wird es jedoch schwierig, noch weitere Damen aufs Feld zu bringen.
Und tatsächlich gibt es 24 Möglichkeiten, 7 Damen zu platzieren. Von den 24 Möglichkeiten bleiben nur noch 6 übrig, wenn man Drehungen und Spiegelungen herausrechnet. Und Achtung: von diesen 6 erlauben 5 keine gültige Lösung für die restlichen beiden Ziffern.
Es gibt also (modulo Symmetrien und Permutationen der Ziffern) nur ein gültiges Sudoku mit 7 Damen und das sieht so aus:
2 0 5 | 4 7 3 | 6 1 0
0 7 3 | 6 1 2 | 4 0 5
6 1 4 | 5 0 0 | 3 7 2
-------+-------+-------
7 3 6 | 0 2 4 | 0 5 1
1 2 0 | 7 5 6 | 0 3 4
4 5 0 | 1 3 0 | 7 2 6
-------+-------+-------
3 6 2 | 0 0 5 | 1 4 7
5 0 1 | 3 4 7 | 2 6 0
0 4 7 | 2 6 1 | 5 0 3
Es hat allerdings 4 Lösungen, also müsste man noch zwei 8er/9er angeben um es eindeutig zu machen.
Was noch ganz interessant ist: Für manche Felder auf denen eine Dame ist, sind bestimmte andere Felder nichttrivial ausgeschlossen, z.B.
Die Ziffern 1-0 geben dabei die 10 möglichen Konstellationen für die Dame in der "inneren Ecke" an. Alle roten Felder sind nichttrivial ausgeschlossen. Besonders an der Dame an dieser Position ist, dass immer eine weitere Dame einen Knightsmove nach außen weg sein muss, hier also in r1c4 oder r4c1. Das ist m.E. absolut nicht offensichtlich und ich habe auch keinen einfacheren Beweis dafür gefunden, als das Gegenteil nach ziemlich viel T/E zum Widerspruch zu führen.