Liebe Perl-Community,

ich habe immer mit Interesse Euere Rätsel der Woche verfolgt. Leider in der letzten Zeit nichts neues dazugekommen.
Nun suche ich eine Lösung auf das folgenden Problem, angelegt an das das Damenproblem (das Damenproblem: es sollen jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass sich keine zwei Damen nach den Schachregeln schlagen können. Anders ausgedrückt, sollte immer nur eine Dame in der gleichen Reihe, Linie oder Diagonale stehen).

Problem:
Also es sollen 10, oder 12, 14, 16 ... n Steine auf einem Schachbrett so aufgestellt werden, das in der gleichen Reihe, Linie oder Diagonale immer nur 2, oder 3, 4 ...n stehen.
Gibt es dazu eine Lösung in Perl?

Viele Liebe grüße aus Buxtehude

Das kann man wahrscheinlich direkt mathematisch lösen, du solltest aber dazusagen wie groß das Schachbrett ist, man kann nicht 10 Damen auf einem normalen Schachbrett aufstellen.

Ist n immer gerade? ist das "zwote" n immer exakt oder eine obere Schranke? Soll eine Lösung oder alle Lösungen gefunden werden?

Hier mal ne Lösung mit 16 Damen auf nem 8er Brett wo jede Dame jeweils 3 mal geschlagen werden kann, genau einmal horizontal, vertikal und diagonal!

sauber =)
hast du das selbst erknobelt oder die lösung irgendwo gefunden?

Hingeschrieben, zu irgendwas muss ein Mathestudium ja taugen! ;)

Neben den 4 hier bekannten Richtungen kennt nämlich dieser affine Raum noch andere Unterräume für die gilt dass sie sich jeweils nur an einem Punkt schneiden.

Tatsächlich ist es doch mathematisch nicht trivial, weil das 8er-Schachbrett kein richtiger affiner Raum ist.
Der Unterschied ist hier auch das die Diagonalen nicht "wrappen", sprich du kannst nicht am anderen Ende des Brettes weitermachen, die Kanten sind nicht "verklebt".

Der affine Raum kennt nämlich nur 7 Parallelen zu einer Diagonalen, hier sinds aber 14, die Damen können nicht "um die Ecke schlagen".

Und wegen dieser Einschränkung des Mathematischen Modells kann Perl durch Backtracking noch besondere Lösungen finden...

Liebe Perl-Community,

vielen Dank für die Beiträge.
Nun werde ich versuchen das Problem geneuer beschreiben.

Das Damenproblem: es sollen jeweils acht Damen auf einem Schachbrett (8X8) so aufgestellt werden, dass sich keine zwei Damen nach den Schachregeln schlagen können. Anders ausgedrückt, sollte immer nur eine Dame in jeder Reihe, jeder Spalte oder jeder Diagonale ( nicht nur die Hauptdiagonale) stehen.

Soweit in Ordnung, es gibt mehrere Lösungen mit Backtracking im Perl dazu.

Nun ist die Frage:

Wieviele Lösungen gibt, wenn auf einem Brett (8X8) 10 Steine so aufgestellt werden, dass immer nur 2 Steine in jeder Reihe, jeder Spalte oder jeder Diagonale ( nicht nur die Hauptdiagonale) stehen dürfen.

Oder allgemein formuliert:

Es sollen 10, oder 12, 14, 16 ... n Steine auf einem Brett (8X8) so aufgestellt werden, das in jeder Reihe, in jeder Spalte und in jeder Diagonale ( nicht nur die Hauptdiagonale) immer nur 2, oder 3, 4 ...n Steine stehen können.


Gibt es dazu eine Lösung in Perl?

Viele Liebe grüße aus Buxtehude

Ich ergänze es mal so dass es Sinn ergibt:

Gast+2009-02-05 13:52:06--

Wieviele Lösungen gibt, wenn auf einem Brett (8X8) 10 Steine so aufgestellt werden, dass immer nur 2 Steine in jeder Reihe, jeder Spalte oder jeder Diagonale ( nicht nur die Hauptdiagonale) stehen dürfen.

... das immer höchstens(!) 2 Steine ...

Gast+2009-02-05 13:52:06--

Oder allgemein formuliert:

Es sollen 10, oder 12, 14, 16 ... n Steine auf einem Brett (8X8) so aufgestellt werden, das in jeder Reihe, in jeder Spalte und in jeder Diagonale ( nicht nur die Hauptdiagonale) immer nur 2, oder 3, 4 ...n Steine stehen können.

das zweite n ist ein m mit m=int(n/8)

Hier mal ne Lösung mit 27 Damen auf nem 9er Brett wo jede Dame jeweils höchsten 8 mal geschlagen werden kann (< 3 Damen pro Richtung¹).

Schneidet man ein 8x8 Schachfeld aus erhält man 21 (oder 22) Damen mit höchstens 3 Damen pro Richtung!



Interessanter ist ob auf dem Schachfeld das Maximum für 3er Besetzungen erreichbar ist, also 24 Damen!

EDIT:
(¹) eigentlich sinds genau 3 Pro Richtung wenn man die Diagonalen hinter den Kanten fortsetzen darf.

so wird das Konstruktionsprinzip vielleicht klarer

geht 24 Damen , <3 pro Richtung



Ansatz über modifiziertes Steiner Triple System: http://en.wikipedia.org/wiki/Steiner_system

32 Damen, <4 pro Richtung


ergibt sich aus Spiegelsymmetrien, alles mathematisch nicht so spannend, dass man es per Programm lösen müsste.

Das Damenproblem ist IMHO nur schwer (und interessant) wenn sie sich nicht schlagen dürfen, die Verallgemeinerung machts nur einfacher. Ein ein Programm fürs einfache Damenproblem so zu schreiben, dass die Schlagmöglichkeiten nicht Null sondern kleiner m sind ist auch kein bedeutender Schritt!