Damensudoku

[glum_hippo]

Ich habe die 24 Resultate durch den Computer gejagt (ohne selber zu prüfen, dass sie alle Möglichkeiten erschöpfen) — und es ist eine weitere Einschränkung aufgetaucht, die 20 von den 24 als Sudoku-Gitter verbieten: die für die 8. und 9. Ziffer übrigbleibenden Felder können nicht ohne Widerspruch auf zwei Zahlen verteilt werden. Zum Beispiel die zweite Lösung in uvos Aufreihung:

102|034|567
637|512|040
054|607|132
-----------
423|700|651
706|125|304
510|346|270
-----------
345|270|016
260|451|703
071|063|425
-----------

Setzt man eine 8 in R1S2, dann hat man bald folgende Situation:

182|934|567
637|512|948
954|687|132
-----------
423|798|651
796|125|384
518|346|279
-----------
345|279|816
269|451|793
871|X63|425
----------- 

Beim 'X' kann man keine Zahl mehr platzieren. Die einzigen Lösungen, die noch gehen sind die 3. 7. 19. und 20.
Sie weisen alle dasselbe Null-Muster auf, und ich habe noch nicht untersucht, ob sie Spiegelungen/Transpositionen voneinander sind.

Grid 3.

102|345|670
034|617|205
765|200|143
-----------
527|034|061
340|176|052
610|520|734
-----------
256|003|417
403|761|520
071|452|306
-----------

Grid 7.

102|345|670
045|671|302
673|200|541
-----------
456|013|027
710|426|053
320|750|416
-----------
561|002|734
207|534|160
034|167|205
-----------

Grid 19.

012|345|607
306|172|450
547|006|321
-----------
720|450|163
630|217|045
451|063|072
-----------
174|500|236
063|721|504
205|634|710
-----------

Grid 20.

012|345|607
605|712|340
743|006|512
-----------
160|570|234
530|264|071
274|031|065
-----------
451|600|723
027|453|106
306|127|450
-----------

[uvo]

Die Lösungen sind isomorph - müssen sie ja, wenn wir keine Fehler einprogrammiert haben. Beispielsweise lässt sich Grid 3 in Grid 7 transformieren durch eine Spiegelung an einer der beiden Diagonalen (und Permutation der Ziffern natürlich).

Dass es nur vier und nicht acht Lösungen sind, liegt daran, dass jede Lösung symmetrisch bezüglich 180°-Drehung ist.

[glum_hippo]

Gestern habe ich ein neues Damen-Sudoku eingereicht, daß von diesen Informationen gebrauch macht (man muß sie allerdings nicht wissen, um das Puzzle zu lösen)
https://logic-masters.de/Raetselportal/R...?id=0003HY

Es sind 5 Damen dabei statt 7. Auch mit 6 konnte ich nichts basteln, was spannend war... das kann vielleicht jemand anders hinkriegen.

[SlowLarry]

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.



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.

[glum_hippo]

Spannendes Thema, auf jeden Fall! Danke für diese Ausführung, SlowLarry