Zurückverfolgen: N Bishops Problem

Question

Dieses Problem macht mich verrückt... Platzieren Sie N Läufer auf dem NxN-Brett so, dass alle Felder mit mindestens einem von ihnen besetzt oder angegriffen werden.

Kann mir jemand mit einem Algorithmus zur Lösung dieses Problems helfen?

Answer 1

\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_
\_ \_ \_ \_  \_ \_ \_ \_

Answer 2

Es gibt eine Minimal- und eine Maximallösung für dieses Problem, das nicht so trivial ist.

Prüfen Sie dies BishopsProblem oder mehr detailliert

Ich bin sicher, Sie werden leicht ein Beispiel in C finden.

Answer 3

Ich gehe davon aus, dass Sie nach einigen Optimierungen fragen, da der Backtracking-Algorithmus so ist, wie er ist.

Als Erstes ist zu bemerken, dass man Schwarz und Weiß trennen kann - man nimmt die Summe der B_i * W_j wobei i + j = N . Sie können die Diagonalen auch als einfaches Gitter (mit Beschränkungen) darstellen, da dies den Code wahrscheinlich straffer macht und vielleicht leichter zu verstehen ist. Eine weitere Optimierung besteht darin, zu bemerken, dass die Farbe nicht unbedingt eine Rolle spielt - die Ergebnisse für einige Schwarze können für einige Weiße verwendet werden. Finden Sie heraus, wann dies der Fall ist und wann nicht.

Ich hoffe, dass dies eine ausreichende Unterstützung ist - es sollte für einige kleinere N's ausreichend sein.

Answer 4

Warum zurückverfolgen? Nutzen Sie die geringe Anzahl von Lösungen, um einen Beweis zu erhalten.

Selbst ein gieriger Algorithmus reicht aus: Zähle die Anzahl der Quadrate, die von jedem Quadrat aus erreichbar sind. Wähle ein Feld mit der größten Reichweite, das sich nicht mit einem zuvor gewählten Feld überschneidet. Wiederholen Sie dies.

Mehrdeutigkeit erzeugt horizontale, vertikale und seitliche Abweichungen.

N Läufer reichen nur aus, um jedes Feld mit genau einem Läufer zu erreichen. Wenn man Felder mit überlappender Reichweite auswählt, wäre die endgültige Zahl der erreichbaren Felder niedriger. Hmm, vielleicht muss man quantifizieren, um wie viel niedriger die Zahl für ein bestimmtes schlechtes Feld ist. Klingt machbar.

Bei einem so riesigen Problemraum ist ein Brute-Force-Backtracking nicht vielversprechend.