Damensudoku

[glum_hippo]

Hat sich jemand schon mit 'Damensudoku' beschäftigt? Damit meine ich mitnichten Sudoku for Ladies, sondern Sudoku mit der weiteren Einschränkung, daß eine gewisse Ziffer (oft die 9?) über den normalen Sudoku-Einschränkungen hinaus auch nicht auf derselben Diagonale liegen darf, wie andere 9er. Da sagt man, die 9 sei eine 'Dame' (vgl. Schach)

Meine Frage: Ich vermute, dass es ausgeschlossen ist, daß alle 9 Ziffern diese Einschränkung einhalten können. Ich finde zwar Lösungen, wo zwei Ziffern Damen sind, aber können es auch mehr als 2 Ziffern sein? Gibt es hierzu bereits Forschungsliteratur?!

[Realshaggy]

Jessica6 hat in einem Kommentar zu einem Portalrätsel geschrieben, dass es 144 Möglichkeiten gibt, eine Ziffer entsprechend der Regeln auf einem leeren Sudokugitter zu platzieren. Inklusive Symmetrien, d.h. davon können viele durch Drehung und Spiegelung ineinander überführt werden.

In einem anderen Portalrätsel

https://logic-masters.de/Raetselportal/R...?id=0003A3

sind alle ungeraden Ziffern Damen. Für alle wird das vermutlich nicht gehen, dafür müßtest du aus den 144 Lösungen neun auswählen können, die das ganze Gitter bedecken.

[glum_hippo]

Vergebens habe ich jessica6s Kommentar (mit der Suchfunktion) gesucht. Hat sie damals auch zufällig ihre Quelle zitiert?

[Realshaggy]

Das war ein versteckter Kommentar, den du nur siehst, wenn du das Rätsel gelöst hast. Ich glaube, Kommentare kann man auch nicht durchsuchen. Quelle war ein eigenes Computerprogramm. Ohne es nachgeprüft zu haben, halte ich das für eine realistische Größenordnung. Ich habe gestern ein Rätsel gesehen, bei dem 6 der Ziffern als Damen gelten. Weiß nicht, ob man das noch verbessern kann.

[glum_hippo]

Mit Google kann man evtl Kommentare finden mit site:forum.logic-masters.de, aber wenn sie versteckt sind, dann sind sie sehr wohl in ihrer Auffindbarkeit eingeschränkt! :-D

@jessica6 kann man hier wohl nicht beizitieren. Tja, dann werde ich selber forschen müssen. Danke trotzdem für die Hinweise! Und wenn Du jenes 6-Damen puzzle nochmal finden kannst, dann würde es mich sehr interessieren.

[uvo]

Zunächst mal nur das 9-Damen-Problem ohne die 3x3-Blöcke des Sudoku:

Es gibt 352 Möglichkeiten, 9 Damen auf einem 9x9-Brett aufzustellen, so dass sie einander nicht bedrohen.

Es gibt 1552 Möglichkeiten, sieben disjunkte Lösungen auszuwählen. Es ist nicht möglich, acht oder neun disjunkte Lösungen auszuwählen.

Mit der zusätzlichen Sudoku-Bedingung (in jedem 3x3-Block steht genau eine Dame) verbleiben noch 144 von 352 Lösungen, und es gibt nur noch 24 Möglichkeiten, sieben disjunkte Lösungen auszuwählen:

[0, 4, 6, 8, 3, 1, 7, 5, 2]/[1, 8, 5, 2, 4, 7, 0, 3, 6]/[2, 5, 7, 4, 0, 8, 6, 1, 3]/[3, 0, 8, 5, 2, 6, 1, 7, 4]/[4, 7, 0, 3, 6, 2, 5, 8, 1]/[6, 3, 1, 7, 5, 0, 2, 4, 8]/[7, 2, 4, 1, 8, 5, 3, 6, 0]/
[0, 4, 6, 8, 3, 1, 7, 5, 2]/[2, 5, 8, 1, 4, 6, 3, 0, 7]/[4, 1, 7, 2, 6, 3, 0, 8, 5]/[5, 7, 2, 0, 8, 4, 1, 3, 6]/[6, 3, 1, 7, 5, 0, 2, 4, 8]/[7, 0, 3, 6, 2, 5, 8, 1, 4]/[8, 2, 5, 3, 0, 7, 4, 6, 1]/
[0, 4, 6, 8, 3, 1, 7, 5, 2]/[2, 6, 3, 1, 8, 4, 0, 7, 5]/[3, 1, 8, 4, 0, 7, 5, 2, 6]/[4, 2, 7, 5, 1, 8, 6, 0, 3]/[5, 8, 2, 0, 7, 3, 1, 6, 4]/[6, 3, 1, 7, 5, 0, 2, 4, 8]/[7, 5, 0, 2, 4, 6, 8, 3, 1]/
[0, 5, 7, 2, 6, 3, 1, 8, 4]/[2, 8, 5, 1, 4, 6, 0, 3, 7]/[3, 6, 2, 7, 1, 4, 8, 5, 0]/[4, 1, 8, 0, 5, 7, 2, 6, 3]/[6, 0, 3, 5, 8, 2, 4, 7, 1]/[7, 2, 4, 8, 0, 5, 3, 1, 6]/[8, 3, 0, 4, 7, 1, 6, 2, 5]/
[0, 5, 8, 4, 1, 7, 2, 6, 3]/[1, 6, 4, 0, 8, 3, 5, 7, 2]/[2, 8, 5, 3, 0, 6, 4, 1, 7]/[4, 7, 0, 8, 3, 1, 6, 2, 5]/[5, 2, 6, 1, 7, 4, 0, 3, 8]/[6, 0, 3, 7, 4, 2, 8, 5, 1]/[8, 3, 1, 6, 2, 5, 7, 0, 4]/
[0, 5, 8, 4, 1, 7, 2, 6, 3]/[1, 7, 4, 2, 8, 5, 3, 0, 6]/[3, 6, 2, 7, 5, 0, 8, 1, 4]/[4, 8, 1, 3, 6, 2, 7, 5, 0]/[5, 2, 6, 1, 7, 4, 0, 3, 8]/[6, 1, 3, 5, 0, 8, 4, 2, 7]/[7, 3, 0, 6, 4, 1, 5, 8, 2]/
[0, 5, 8, 4, 1, 7, 2, 6, 3]/[2, 8, 3, 7, 4, 1, 5, 0, 6]/[3, 6, 2, 5, 8, 0, 7, 4, 1]/[4, 1, 7, 0, 3, 6, 8, 5, 2]/[5, 2, 6, 1, 7, 4, 0, 3, 8]/[6, 3, 0, 2, 5, 8, 1, 7, 4]/[7, 4, 1, 8, 0, 3, 6, 2, 5]/
[0, 6, 3, 5, 8, 1, 4, 2, 7]/[1, 8, 5, 2, 6, 3, 0, 7, 4]/[2, 5, 7, 1, 3, 8, 6, 4, 0]/[3, 1, 6, 8, 0, 4, 7, 5, 2]/[4, 7, 1, 6, 2, 5, 8, 0, 3]/[6, 3, 0, 7, 4, 2, 5, 8, 1]/[8, 4, 2, 0, 5, 7, 1, 3, 6]/
[0, 6, 3, 7, 2, 4, 8, 1, 5]/[1, 4, 7, 0, 8, 5, 2, 6, 3]/[2, 5, 8, 6, 1, 3, 7, 0, 4]/[3, 7, 0, 4, 6, 1, 5, 2, 8]/[4, 8, 1, 5, 7, 2, 0, 3, 6]/[5, 2, 6, 3, 0, 8, 1, 4, 7]/[6, 0, 5, 1, 4, 7, 3, 8, 2]/
[0, 6, 3, 7, 2, 4, 8, 1, 5]/[1, 4, 7, 0, 8, 5, 2, 6, 3]/[2, 8, 5, 1, 4, 6, 0, 3, 7]/[3, 7, 0, 4, 6, 1, 5, 2, 8]/[5, 2, 8, 3, 0, 7, 1, 4, 6]/[6, 3, 1, 8, 5, 2, 4, 7, 0]/[8, 1, 4, 6, 3, 0, 7, 5, 2]/
[0, 6, 3, 7, 2, 4, 8, 1, 5]/[1, 5, 8, 2, 4, 7, 3, 0, 6]/[2, 4, 7, 1, 8, 5, 0, 6, 3]/[3, 7, 0, 4, 6, 1, 5, 2, 8]/[5, 2, 6, 3, 0, 8, 1, 4, 7]/[6, 3, 1, 8, 5, 2, 4, 7, 0]/[8, 1, 4, 6, 3, 0, 7, 5, 2]/
[0, 6, 3, 7, 2, 4, 8, 1, 5]/[1, 8, 5, 2, 4, 7, 0, 3, 6]/[2, 5, 8, 0, 7, 3, 1, 6, 4]/[3, 7, 0, 4, 6, 1, 5, 2, 8]/[4, 2, 7, 5, 1, 8, 6, 0, 3]/[6, 3, 1, 8, 5, 2, 4, 7, 0]/[8, 1, 4, 6, 3, 0, 7, 5, 2]/
[0, 6, 3, 7, 2, 4, 8, 1, 5]/[2, 5, 8, 1, 4, 6, 3, 0, 7]/[3, 7, 0, 4, 6, 1, 5, 2, 8]/[4, 2, 7, 5, 1, 8, 0, 3, 6]/[5, 8, 2, 0, 7, 3, 1, 6, 4]/[6, 3, 1, 8, 5, 2, 4, 7, 0]/[8, 1, 4, 6, 3, 0, 7, 5, 2]/
[0, 7, 4, 2, 5, 8, 1, 3, 6]/[1, 3, 8, 6, 4, 2, 0, 5, 7]/[2, 5, 7, 0, 3, 6, 4, 1, 8]/[3, 0, 6, 8, 1, 5, 7, 2, 4]/[4, 6, 1, 3, 7, 0, 2, 8, 5]/[6, 2, 5, 7, 0, 3, 8, 4, 1]/[7, 4, 0, 5, 8, 1, 3, 6, 2]/
[0, 7, 4, 2, 5, 8, 1, 3, 6]/[2, 5, 7, 0, 3, 6, 4, 1, 8]/[3, 0, 6, 8, 1, 5, 7, 2, 4]/[4, 6, 1, 3, 7, 0, 8, 5, 2]/[5, 1, 8, 4, 2, 7, 3, 6, 0]/[6, 3, 0, 7, 4, 2, 5, 8, 1]/[8, 2, 5, 1, 6, 4, 0, 7, 3]/
[0, 7, 4, 2, 5, 8, 1, 3, 6]/[2, 5, 7, 0, 3, 6, 4, 1, 8]/[3, 6, 0, 5, 8, 1, 7, 4, 2]/[5, 1, 8, 4, 2, 7, 3, 6, 0]/[6, 0, 3, 7, 4, 2, 8, 5, 1]/[7, 4, 1, 8, 0, 3, 6, 2, 5]/[8, 2, 5, 1, 6, 4, 0, 7, 3]/
[0, 7, 4, 2, 5, 8, 1, 3, 6]/[2, 5, 7, 0, 3, 6, 4, 1, 8]/[3, 6, 2, 5, 8, 0, 7, 4, 1]/[5, 1, 8, 4, 2, 7, 3, 6, 0]/[6, 4, 1, 7, 0, 3, 8, 2, 5]/[7, 3, 0, 6, 4, 1, 5, 8, 2]/[8, 2, 5, 1, 6, 4, 0, 7, 3]/
[0, 7, 4, 2, 5, 8, 1, 3, 6]/[2, 5, 7, 0, 3, 6, 4, 1, 8]/[4, 6, 1, 3, 7, 0, 2, 8, 5]/[5, 1, 8, 4, 2, 7, 3, 6, 0]/[6, 3, 0, 8, 1, 5, 7, 2, 4]/[7, 0, 3, 6, 4, 1, 8, 5, 2]/[8, 2, 5, 1, 6, 4, 0, 7, 3]/
[1, 3, 8, 6, 4, 2, 0, 5, 7]/[2, 5, 7, 1, 3, 8, 6, 4, 0]/[3, 0, 6, 8, 1, 5, 7, 2, 4]/[4, 6, 1, 3, 7, 0, 2, 8, 5]/[5, 7, 0, 4, 8, 1, 3, 6, 2]/[6, 2, 5, 7, 0, 4, 8, 1, 3]/[8, 4, 2, 0, 5, 7, 1, 3, 6]/
[1, 4, 7, 0, 8, 5, 2, 6, 3]/[2, 5, 8, 6, 3, 0, 7, 1, 4]/[3, 6, 2, 7, 1, 4, 8, 5, 0]/[4, 7, 1, 8, 5, 2, 0, 3, 6]/[5, 2, 6, 3, 0, 8, 1, 4, 7]/[6, 0, 5, 1, 4, 7, 3, 8, 2]/[8, 3, 0, 4, 7, 1, 6, 2, 5]/
[1, 4, 8, 3, 0, 7, 5, 2, 6]/[2, 6, 3, 1, 8, 5, 0, 4, 7]/[4, 2, 7, 5, 1, 8, 6, 0, 3]/[5, 8, 2, 0, 7, 3, 1, 6, 4]/[6, 3, 1, 8, 5, 2, 4, 7, 0]/[7, 5, 0, 2, 4, 6, 8, 3, 1]/[8, 1, 4, 6, 3, 0, 7, 5, 2]/
[1, 5, 8, 2, 4, 7, 3, 0, 6]/[2, 7, 5, 3, 8, 0, 4, 6, 1]/[3, 6, 2, 7, 1, 4, 8, 5, 0]/[4, 0, 7, 5, 2, 6, 1, 3, 8]/[5, 2, 6, 1, 3, 8, 0, 7, 4]/[7, 1, 4, 6, 0, 3, 5, 8, 2]/[8, 3, 0, 4, 7, 1, 6, 2, 5]/
[1, 6, 4, 7, 0, 3, 5, 2, 8]/[2, 5, 7, 1, 3, 8, 6, 4, 0]/[4, 1, 8, 5, 2, 6, 3, 0, 7]/[5, 8, 0, 3, 6, 2, 7, 1, 4]/[6, 3, 1, 4, 8, 0, 2, 7, 5]/[7, 0, 3, 6, 4, 1, 8, 5, 2]/[8, 4, 2, 0, 5, 7, 1, 3, 6]/
[2, 8, 3, 7, 4, 1, 5, 0, 6]/[3, 6, 2, 5, 8, 0, 7, 4, 1]/[4, 0, 7, 3, 1, 6, 8, 5, 2]/[5, 1, 8, 4, 2, 7, 3, 6, 0]/[6, 3, 0, 2, 7, 5, 1, 8, 4]/[7, 4, 1, 8, 0, 3, 6, 2, 5]/[8, 2, 5, 1, 6, 4, 0, 7, 3]/

Alle Angaben ohne Gewähr.

[glum_hippo]

Vielen Dank für diesen Stoff! Sehr spannend. Haben wir's hier auch mit Originalforschung zu tun? Alle Achtung!

[uvo]

Würde mich wundern, wenn das noch niemand genauer untersucht hat.

Siehe zum Beispiel hier:  A survey of known results and research areas for n-queens

Es geht allerdings nur um das Damenproblem, nicht um Sudoku.

[Realshaggy]

Ich weiß nicht, was du mit Originalforschung meinst. Wenn man der Wikipedia glaubt, ist das 8 Damenproblem schon um 1850 in der Schachliteratur aufgetaucht und von Hand vollständig gelöst worden. Spätestens mit allgemeiner Verfügbarkeit von Computern ist es sicher von tausenden Interessierten inklusive naheliegender Varianten (wie hier der zusätzlichen Sudokbedingung) gelöst worden, ohne dass die erzielten Ergebnisse so spektakulär sind, dass man sie ernsthaft veröffentlichen könnte. Für Programmieranfänger ist das Problem ein sehr gutes einfaches Beispiel für Backtracking-Algorithmen. Man merkt dabei auch gut, dass das in der Grundversion mit steigendem n ziemlich schnell nicht mehr geht. Nachzuschauen wieviele disjunkte Lösungen maximal möglich sind, ist dann etwas kniffliger aber sicher auch noch keine wissenschaftliche Glanztat.

[glum_hippo]

Es muß auch nicht unbedingt glänzen, um eine Quelle zu sein. Aber auch für diese Hinweise sei herzlich bedankt.