Ist es möglich, eine Dame und mindestens 29 Springer auf einem 8x8-Schachbrett so zu platzieren, dass sich keine 2 Figuren gegenseitig angreifen?

Ist es möglich, eine Dame und mindestens 29 Springer in einer 8 zu platzieren? × 8 Schachbrett so, dass sich keine 2 Figuren gegenseitig angreifen?

Ich dachte, ich sollte versuchen, die Grenze zu benutzen ⌈ M N 2 ⌉ für die Anzahl der Ritter in a M × N Schachbrett so, dass sie sich nicht gegenseitig angreifen, aber das erfordert M , N > 2 , und für einige Damenstellungen gilt das nicht.

Ich dachte auch, wenn wir eine Dame hätten, gibt es höchstens 7 Reihen, um die Springer zu platzieren, also müssen es 5 Springer in einer Reihe sein. Ich bin mir aber nicht sicher, was das nützen könnte.

Häh? Ihre Antwort mag richtig sein, aber ich glaube nicht, dass Ihre Argumentation stimmt. Warum können nicht mehrere Ritter dasselbe leere Feld angreifen?
Du kannst Geben 32 Ritter auf ein 8 × 8 Schachbrett, wobei keiner von ihnen den anderen angreift, indem er einfach einen Springer auf jedes weiße (oder jedes schwarze) Feld setzt.
@justadumbguy: Bist du sicher, dass dein Problem keinen Tippfehler enthält? Ich finde 29 ist viel zu groß um zu arbeiten. Könnte die Frage stattdessen lauten 19 ? Das funktioniert.
@DavidG.Stork wie wandelt man dieses Problem überhaupt in ein kombinatorisches um, das mit algebraischer oder kombinatorischer Technik gelöst wird? Diese Rätsel widersetzen sich der Parametrisierung, soweit ich das beurteilen kann
@FShrike: In der Tat. Ich denke, der einzig praktikable Ansatz ist die Computersuche ... möglicherweise mit einer gewissen Effizienzsteigerung basierend auf den Symmetrien des Problems (z. B. müssen wir nur Positionen für die Dame in einem Quadranten berücksichtigen). Wie auch immer, meine aktuelle Antwort auf das OP lautet: "Nein".
@DavidG.Stork Wie platzierst du 24 Springer auf dem Brett, ohne dass einer von ihnen die Dame angreift? Ich kann es nicht besser als 22 .
@RobertShore: Vergib mir ... ich habe mich geirrt. Ich habe bemerkt, dass zwei meiner Springer tatsächlich die Dame angegriffen haben, also ja: 22. (Ich werde den alten Kommentar löschen.). Danke. Trotzdem denke ich, dass wir uns einig sind, dass die Antwort auf die Frage des OP "Nein" lautet.
Sind die Seiten wichtig (z. B. 14 weiße Springer und 15 schwarze)?
Wenn die Seiten wichtig sind, dann ist hier eine Lösung: chessvideos.tv/bimg/126omnfkdyz6.png Aber wenn die Seiten keine Rolle spielen, dann ist es keine Lösung ...

Antworten (2)

Zunächst einmal ist hier der Beweis, dass Sie nicht mehr als setzen können 32 nicht angreifende Springer auf einem Schachbrett. Sie können die Quadrate des Bretts paaren 32 Paare, wobei jedes Paar einen Springerzug voneinander entfernt ist, wie unten gezeigt. Da Sie in jedem Paar höchstens einen Springer platzieren können, können Sie höchstens platzieren 32 Ritter.

Stellen Sie sich nun vor, Sie platzieren eine Dame auf einem Feld in demselben Diagramm und platzieren dann ein X auf jedem Feld, das von der Dame angegriffen wird, sowie ein X auf den Feldern, die einen Springerzug von der Dame entfernt sind. Egal, wo Sie die Dame platzieren, zumindest 4 von diesen Paaren haben beide ihre Quadrate X'ed aus. Daher wird die Anzahl der Ritter, die Sie platzieren können, um mindestens vier reduziert, sodass Sie nicht mehr als platzieren können 28 Ritter.

Zum Beispiel, wenn die Dame bei platziert wird A 1 , die untere linke Ecke, dann die Paare A 1 − C 2 , A 2 − C 1 , B 2 − D 1 , Und A 4 − C 3 sind alle ausgekreuzt (der Buchstabe ist die Spalte und die Zahl ist die Zeile). Es ist nicht allzu schwer, von Fall zu Fall zu verifizieren, dass die Dame immer mindestens X ist 4 dieser Paare. Je näher die Dame der Mitte rückt, desto mehr Paare hat sie im Out.

Über die ganzzahlige lineare Programmierung habe ich herausgefunden, dass Sie höchstens platzieren können, wenn Sie mindestens eine Dame erzwingen 22 Ritter, und hier ist eine solche Lösung:

. N . N . N . . N . N . N . N . . N . N . N . . N . N . N . N . . N . N . N . . N . N . N . . . . N . N . . . . . . . . . . . Q

Wie in diesem Problem, wo die Dame durch einen Turm ersetzt wird , für jeden der 10 Im Wesentlichen unterschiedliche Platzierungen der Königin, die Dualität der linearen Programmierung liefert ein Zertifikat der Optimalität. Wenn zum Beispiel die Dame in die rechte untere Ecke gestellt wird, erfolgt die folgende Aufteilung der verbleibenden unangegriffenen Felder hinein 22 Sets zeigt das höchstens 22 Ritter können platziert werden:

. 19 1 20 2 3 4 . 1 . 2 5 4 6 21 . 7 8 . 9 10 5 3 . 11 12 7 . 13 9 6 . 8 14 15 12 . 10 16 . 17 11 18 13 16 . . . 14 15 17 22 18 . . . . . . . . . . .
Dies ist eine Verfeinerung des von @Mike Earnest gezeigten Ansatzes und ergibt ähnliche Zertifikate für den anderen 9 Fälle.

Ist es möglich, eine Dame und mindestens 29 Springer auf einem 8x8-Schachbrett so zu platzieren, dass sich keine 2 Figuren gegenseitig angreifen?
AntwortenHierDatenschutz-Bestimmungen1y, 1v