Entwicklung eines brute force Algorithmus für das Damenproblem

Das Damenproblem, also die Aufgabe möglichst wenige Damen auf einem Schachbrett so aufzustellen, dass das gesamte Schachbrett beherrscht wird, wird in ein Problem der Graphentheorie übersetzt. Zu dessen Lösung wird ein brute-force-Algorithmus entwickelt, der darauf beruht, dass man das Schachbrett mit einer Adjazenz-Matrix beschreibt und diese geeignet auswertet.

walter
brute force Algorithmus Abzählprobleme Adjazenz-Matrix Damenproblem Graphentheorie domination number Schachbrett
Inhaltsverzeichnis

Einordnung des Artikels

Einführung

Im Folgenden wird ein Abzählproblem diskutiert, das sich nicht auf die einfachen Begriffe der Kombinatorik (also auf Variation, Permutation und Kombination) zurückführen lässt. Stattdessen wird gezeigt, dass das Problem umformuliert werden kann, so dass man es einem Teilgebiet der Mathematik zuordnen kann, das zunächst wenig mit Kombinatorik zu tun hat, nämlich die Graphentheorie. Aber gerade darin zeigt sich ein weiterer typischer Zug der Kombinatorik: Selbst einfach erscheinende Abzählprobleme führen in andere Gebiete der Mathematik, aus denen man sich Anregungen holen kann, wie ein Problem zu lösen ist.

Das hier behandelte Problem entspringt dem Schachspiel und benötigt nur minimale Kenntnisse der Schachregeln; im nächsten Abschnitt wird es so erklärt, dass es auch für Nicht-Schachspieler verständlich ist.

Das Damenproblem

Die Fragestellungen

Ein Schachbrett besteht aus 64 Feldern, die quadratisch angeordnet sind; sie sind üblicherweise abwechselnd weiß und schwarz. Für das Damenproblem werden nur die Figuren Läufer (bishop), Turm (rook) und Dame (queen) benötigt.

Ein Läufer kann sich nur auf den Diagonalen bewegen; er ist somit nur auf die Felder einer Farbe eingeschränkt. Den längsten Zug kann er von einer Ecke des Schachbrettes zur gegenüberliegenden Ecke ausführen. Durch Abzählen kann man leicht feststellen, dass ein Läufer, der im Zentrum des Schachbrettes steht (als Zentrum werden die 4 Felder bezeichnet, die dem Mittelpunkt des Schachbrettes angrenzen), mehr Felder bedroht als ein Läufer, der näher am Rand steht. Mit "ein Feld bedrohen" ist gemeint, dass der Läufer in einem Zug das Feld erreichen kann und dort etwa eine gegnerische Figur schlagen könnte.

Aufgabe:

Geben Sie für alle Felder 64 Felder des Schachbrettes an, wie viele Felder ein Läufer bedroht. Auf welchen Feldern bedroht der Läufer gleich viele Felder?

Ein Turm kann sich nur entlang von Geraden auf dem Schachbrett bewegen. Egal auf welchem Feld er steht, bedroht er immer 14 Felder.

Die Dame vereinigt die Zugmöglichkeiten von Läufer und Turm.

Über die Strategie des Schachspiels muss im Folgenden nichts bekannt sein, es soll nur darauf hingwiesen werden, dass es sinnvoll ist, seine Figuren so aufzustellen, dass sie möglichst viele Felder des Schachbrettes beherrschen. Für einen Schachspieler ist somit die folgende Fragestellung nicht abwegig:

1. Wie viele Damen benötigt man, um alle Felder des Schachbrettes zu beherrschen?

Zur Bezeichnungsweise: Man sagt eine Figur bedroht ein Feld, wenn sie im einem Zug erreichen kann. Und eine Figur beherrscht ein Feld, wenn sie sich entweder auf dem Feld befindet oder es in einem Zug erreichen kann.

Dabei werden auch die Felder eingerechnet, auf denen sich die Damen gerade befinden (wenn man das Feld nicht beherrscht, würde man seine Dame dort nicht hinstellen).

Die Lösung soll sofort genannt werden:

5 Damen reichen aus, um das 8 × 8-Schachbrett zu beherrschen.

Kennt man die Lösung, drängen sich sofort weitere Fragen auf:

2. Wie viele Möglichkeiten gibt es die 5 Damen auf dem Schachbrett aufzustellen, so dass sie alle Felder des Schachbrettes beherrschen?

3. Wie viele Damen benötigt man, um alle Felder eines n × n-Schachbrettes zu beherrschen?

Diese Anzahl wird oft als domination number bezeichnet und im Folgenden mit DN(n) abgekürzt.

4. Wie viele Möglichkeiten gibt es, DN(n) Damen auf einem n × n-Schachbrett aufzustellen, so dass sie alle Felder beherrschen?

Umformulierung in ein Problem der Graphentheorie

Ein Blick auf die Begriffsbildungen der Kombinatorik zeigt, dass sie wenig beitragen können, die geschilderten Fragestellungen zu bearbeiten. Es soll gezeigt werden, wie man das Damenproblem in ein Problem der Graphentheorie umwandelt – es wird nicht behauptet, dass die Fragen dadurch beantwortet werden!

Die Vorgehensweise ist in Abbildung 1 gezeigt, wo sie am Beispiel eines 3 × 3-Schachbrettes durchgespielt wird.

Abbildung 1: Die Numerierung des Schachbrettes für das Damenproblem für n = 3 sowie die Vorgehensweise, wie das Damenproblem in ein Problem der Graphentheorie umgewandelt werden kann: Die Felder des Schachbrettes werden als Knoten eines Graphen aufgefasst; sind zwei Felder x und y in dem Sinn benachbart, dass eine Dame von x nach y ziehen kann, werden die Knoten x und y durch eine Kante verbunden. Diese Nachbarschaft zwischen den Knoten kann mit der Adjazenz-Matrix ausgedrückt werden.Abbildung 1: Die Numerierung des Schachbrettes für das Damenproblem für n = 3 sowie die Vorgehensweise, wie das Damenproblem in ein Problem der Graphentheorie umgewandelt werden kann: Die Felder des Schachbrettes werden als Knoten eines Graphen aufgefasst; sind zwei Felder x und y in dem Sinn benachbart, dass eine Dame von x nach y ziehen kann, werden die Knoten x und y durch eine Kante verbunden. Diese Nachbarschaft zwischen den Knoten kann mit der Adjazenz-Matrix ausgedrückt werden.

Zunächst werden die Felder des Schachbrettes numeriert, hier von 1 bis 9 (siehe zweites Schachbrett). Die Reihenfolge ist allein schon aus Symmetriegründen unerheblich; hier wurde die Reihenfolge so gewählt, wie in R Matrizen aus Vektoren aufgebaut werden, also zuerst von oben nach unten und dann von links nach rechts.

Im dritten Schachbrett steht eine Dame auf dem Feld 1. Aus den Schachregeln kann man jetzt ableiten, dass diese Dame die Felder 2, 3, 4, 5, 7, 9 bedroht.

Im vierten Schachbrett steht eine Dame auf dem Feld 2 und bedroht die Felder 1, 3, 4, 5, 6, 8.

Unter den Schachbrettern sind zwei Graphen gezeichnet. Dabei wird jedes Feld des Schachbrettes als Knoten dargestellt. Im ersten Graphen ist nur das erste Feld mit 1 bezeichnet, die anderen Felder kann man leicht den Knoten zuordnen.

Eigentlich sollten in einem Graphen alle benachbarten Felder mit einer Linie verbunden sein. Da dies schon für das 3 × 3-Schachbrett sehr unübersichtlich wird, sind lediglich die Nachbarn von 1 gekennzeichnet. Mit "Nachbar von 1" ist gemeint, dass eine Dame auf dem Feld 1 das entsprechende Feld bedroht. Die Linien, die benachbarte Felder verbinden, werden als Kanten bezeichnet.

Der zweite Graph zeigt entsprechend die benachbarten Felder einer Dame auf dem Feld 2.

Es ist wenig hilfreich, den kompletten Graphen zu einem 3 × 3-Schachbrett zu zeichnen. Aussagekräftiger ist hier die sogenannte Adjazenz-Matrix, die unterhalb der Graphen zu sehen ist. Sie gibt an, welche Knoten welche Nachbarn besitzen. Dazu ist sie zeilenweise zu lesen:

Aufgabe:

Welche Symmetrien sind in der Adjazenz-Matrix in Abbildung 1 zu erkennen? Welcher Zusammenhang besteht mit den Symmetrien des Damenproblems?

Die Fragestellungen, die oben für das Damenproblem formuliert wurden, können jetzt in Fragestellungen der Graphentheorie umformuliert werden:

1. Wie viele Knoten müssen in einem Graphen zu einem 8 × 8-Schachbrett ausgewählt werden, so dass diese zusammen mit ihren Nachbarn den kompletten Graphen überdecken? (Dabei sind in dem Graphen mit 64 Knoten alle möglichen Damenzüge als Kanten eingezeichnet.)

2. Wie viele Möglichkeiten gibt es 5 Knoten aus dem Graphen zm 8 × 8-Schachbrett auszuwählen, so dass diese zusammen mit ihren Nachbarn den kompletten Graphen überdecken?

3. Wie viele Knoten DN(n) benötigt man für den Graphen eines n × n-Schachbrett?

4. Wie viele Möglichkeiten gibt es, die DN(n) Knoten auszuwählen, so dass der komplette Graph überdeckt wird?

Im Rahmen der Graphentheorie wird die dritte Frage als Knoten-Überdeckungsproblem bezeichnet.

Für n = 3 lassen sich diese Fragen leicht beantworten – der Ausflug in die Graphentheorie ist hier eigentlich überflüssig. Stellt man eine Dame in die Mitte des Schachbrettes, werden alle anderen Felder bedroht; somit hat man eine Lösung gefunden und es ist DN(3) = 1. Stellt man die Dame auf ein anderes Feld, werden nicht alle anderen Felder des Schachbrettes bedroht, das heißt es gibt nur eine Möglichkeit, das Damenproblem zu lösen.

An der Adjazenz-Matrix sieht man diese Lösung daran, dass ihre 5. Zeile nur eine 0 enthält – nämlich in der 5. Spalte (Hauptdiagonale). Jede andere Zeile enthält 3 Nullen und liefert keine Lösung.

Ergebnisse für kleine n

Unten wird ein brute-force-Algorithmus entwickelt, mit dem die oben gestellten Fragen zumindest für kleine n (hier bis n = 10) in zumutbarer Zeit beantwortet werden können. Die folgende Tabelle zeigt die Übersicht. Zu den Bezeichnungen:

n n × n DN(n) S(n) DN(n) aus n2
3 3 × 3 = 9 1 1 9
4 4 × 4 = 16 2 12 120
5 5 × 5 = 25 3 186 2300
6 6 × 6 = 36 3 4 7140
7 7 × 7 = 49 4 86 211876
8 8 × 8 = 64 5 4860 7624512
9 9 × 9 = 81 5 114 25621596
10 10 × 10 = 100 5 8 75287520
11 11 × 11 = 121 5 2 198792594

Entwicklung eines brute-force-Algorithmus zum Auffinden der Lösungen

Umgangssprachliche Formulierung des Algorithmus

Die Diskussion des Damenproblems im 3 × 3-Schachbrett ist lediglich dazu geeignet, die passenden Begriffe einzuführen; eine Vorgehensweise zum Auffinden der Lösungen lässt sich daraus nur schwer ableiten. Die entscheidenden Hinweise, wie diese Vorgehensweise aussehen könnte, liefert aber schon das 4 × 4-Schachbrett. Es ist in Abbildung 2 dargestellt; unterhalb des ersten Schachbrettes sieht man nochmals wie hier die Felder bezeichnet werden.

Die nächsten 4 Schachbretter zeigen Lösungen des Damenproblems (durch Abstreichen der bedrohten Felder kann man sich leicht davon überzeugen). Unterhalb dieser 4 Schachbretter ist jeweils angegeben:

Abbildung 2: Die Bezeichnungen für das Schachbrett zum Damenproblem mit n = 4. Gezeigt sind 4 spezielle Lösungen sowie die Liste der Felder, die doppelt bedroht werden. Die Adjazenz-Matrix besteht jetzt aus 16 Zeilen und 16 Spalten. Ganz unten sind zwei Zeilen der Adjazenz-Matrix angegeben, an denen man leicht ablesen kann, dass (1, 11) eine Lösung des Damenproblems ist.Abbildung 2: Die Bezeichnungen für das Schachbrett zum Damenproblem mit n = 4. Gezeigt sind 4 spezielle Lösungen sowie die Liste der Felder, die doppelt bedroht werden. Die Adjazenz-Matrix besteht jetzt aus 16 Zeilen und 16 Spalten. Ganz unten sind zwei Zeilen der Adjazenz-Matrix angegeben, an denen man leicht ablesen kann, dass (1, 11) eine Lösung des Damenproblems ist.

Vergleicht man die erste und die zweite Lösung, fällt sofort auf, dass sie nur die Symmetrie des Problems wiederspiegeln. Man kann noch zwei weitere Lösungen angeben, die durch Drehung entstehen. Dagegen sind auf dem 4. und 5. Schachbrett Lösungen zu sehen, die zu keiner anderen der gezeigten Lösungen symmetrisch sind.

Da die Anzahl der von einer Dame bedrohten Felder nimmt von innen nach außen ab; daher gibt es für die 3 qualitativ unterschiedlichen Lösungen andere Anzahlen an Feldern, die doppelt bedroht werden.

Aufgabe:

Zeigen Sie:

  1. Eine Dame kann auf einem Schachbrett beliebiger Größe in maximal 2 Zügen jedes Feld erreichen.
  2. Stellt man 2 Damen auf eine Schachbrett (mit einer gewissen minimalen Seitenlänge), so gibt es mindestens 4 Felder, die doppelt bedroht werden.
  3. Wie groß muss die Seitenlänge des Schachbrettes aus der letzten Aufgabe sein, damit die Aussage richtig ist?
  4. Einige der in Abbildung 2 gezeigten Lösungen für das 4 × 4-Schachbrett kann man direkt aus der Lösung für das 3 × 3-Schachbrett gewinnen. Welche Lösungen sind dies? Wie kann man zu einer gegebenen Lösung des Damenproblems für ein n × n-Schachbrett immer eine Konstellation von n+1 Damen konstruieren, die das (n+1) × (n+1)-Schachbrett beherrschen?

♦ ♦ ♦ ♦

In Abbildung 2 ist wieder die Adjazenz-Matrix für die Felder des 4 × 4-Schachbrettes gezeigt. Es ist natürlich mühsam, diese Matrix zu erzeugen und auszuwerten – weiter unten werden für beide Aufgaben Skripte vorgestellt.

Der richtige Blick auf die dargestellten Lösungen und die Adjazenz-Matrix zeigen, wie man einen brute-force-Algorithmus entwickeln kann, der sämtliche Möglichkeiten durchprobiert, k Damen auf ein n × n-Schachbrett zu stellen und zu prüfen, ob alle Felder bedroht werden.

Dazu betrachte man zunächst die ersten beiden Zeilen der Adjazenz-Matrix in Abbildung 4. Dass auf der Hauptdiagonale der Adjazenz-Matrix Nullen stehen müssen, wurde schon diskutiert. Weiter sieht man sofort, dass es zwei Spalten gibt, wo in beiden Zeilen eine 0 steht: Spalte 8 und 15. Und man kann leicht überprüfen, dass zwei Damen auf den Feldern 1 und 2 die Felder 8 und 15 nicht bedrohen. Folglich ist (1, 2) keine Lösung des Damenproblems für ein 4 × 4-Schachbrett. Eine Lösung würde man daran erkennen, dass in jeder Spalte mindestens eine 1 steht; dabei muss man aber voraussetzen, dass die Nullen auf der Hauptdiagonale zuvor durch Einsen ersetzt werden.

Als Beispiel für eine Lösung sind unter der Adjazenz-Matrix ausdrücklich ihre 1. und 11. Zeile gezeigt (entspricht der Lösung auf dem zweiten Schachbrett). Hier gibt es keine Spalte mit zwei Nullen.

Man kann daher folgenden Algorithmus zum Auffinden der Lösungen formulieren:

  1. Bilde die Adjazenz-Matrix zur Seitenlänge n des Schachbrettes.
  2. Ersetze die Nullen auf der Hauptdiagonale durch Einsen; anschließend wird diese Matrix untersucht.
  3. Bilde alle möglichen Kombinationen von k Zeilen der Matrix. Dies entspricht k Damen auf Feldern a1, ..., ak.
  4. Ist in diesen k Zeilen in jeder Spalte mindestens eine 1 enthalten, dann ist a1, ..., ak eine Lösung des Damenproblems.
  5. Gibt es keine Lösung des Damenproblems, war k zu klein gewählt und der Algorithmus wird mit k + 1 wiederholt.

An der Tabelle oben mit den vorweggenommenen Ergebnissen kann man schon ablesen, wie aufwendig die Suche nach den Lösungen ist: Die Anzahl der zu untersuchenden Kombinationen ist "k aus n2" und beträgt bei n = 9 und k = 5 schon über 25 Millionen.

Umsetzung des Algorithmus in R

Betrachtet man den umgangssprachlich formulierten Algorithmus oben, kann man mehrere Teilprobleme identifizieren, die sich leicht implementieren lassen:

  1. Zu einer gegebenen Seitenlänge n des Schachbrettes muss die Adjazenz-Matrix berechnet werden; dazu wird die Bezeichnungs-Konvention für die Felder wie in den Abbildungen 1 und 2 verwendet.
  2. Man muss alle möglichen Kombinationen durchspielen, k Damen auf die n2 Felder des Schachbrettes zu stellen.
  3. Für jede Kombination muss mit Hilfe der Adjazenz-Matrix festgestellt werden, ob alle Felder des Brettes bedroht werden.

Berechnung der Adjazenz-Matrix

Es gibt natürlich zahllose Möglichkeiten, wie man hier die Adjazenz-Matrix berechnen kann. Da es einmalig geschieht und im eigentlichen brute-force-Algorithmus immer auf diese eine Matrix zugegriffen wird, muss man bei der Implementierung nicht darauf achten, dass die Berechnung wenig Rechenzeit beansprucht.

Die Lösung, die hier vorgestellt wird, arbeitet mit den Indizes der Felder des Schachbrettes. Dazu denkt man sich die n2 Felder in einer n × n Matrix angeordnet und jedes Feld besitzt einen Zeilen-Index i und einen Spalten-Index j. Führt eine Figur einen Zug aus, gilt:

  1. Beim Zug eines Läufers bleibt entweder die Summe i + j oder die Differenz i - j konstant. Ersteres entspricht einer Bewegung parallel zur Nebendiagonale der Matrix, Letzteres einer Bewegung parallel zur Hauptdiagonale der Matrix.
  2. Beim Zug eines Turmes bleibt entweder der Zeilen-Index i oder der Spalten-Index j konstant. Dies sind entweder Bewegungen nach rechts und links beziehungsweise nach oben oder unten.
  3. Eine Dame kann sich wie ein Läufer oder ein Turm bewegen, es gibt also 4 Möglichkeiten, welche Größe beim Zug einer Dame konstant bleibt.

Damit kann man die Berechnung der Adjazenz-Matrix wieder in Teilprobleme zerlegen:

  1. Berechnung der Felder, die eine Figur bedroht, wenn sie auf einem bestimmten Feld steht, nämlich für
    1. Läufer,
    2. Turm,
    3. Dame.
  2. Vorbereiten der Adjazenz-Matrix als Matrix geeigneter Größe.
  3. Setzen der Zeilen der Adjazenz-Matrix mit Hilfe der oben berechneten Felder, die eine Dame bedroht.

Diese Vorgehensweise mag etwas umständlich erscheinen, sie hat den Vorteil, dass sie später leicht ergänzt werden kann, wenn man mit anderen Figuren experimentieren möchte (etwa Springer oder eine Figur, die die Zugmöglichkeiten von Turm und Springer vereinigt und so weiter).

Den ersten Punkt aus der Liste kann man auch so verstehen: Zu einem gegebenen Feld, wird die zugehörige Zeile in der Adjazenz-Matrix berechnet (zusätzlich abhängig von der Art der Figur).

Es bietet sich daher folgende Aufteilung der Aufgaben an:

Die Implementierung dieser beiden Funktionen sind in den folgenden Skripten gezeigt:

# Erzeugen der Adjazenz-Matrix
# Eingabewerte:
# piece: Queen, Rook, Bishop
# n = 3; Anzahl der Felder pro Reihe. n2 <- n*n: Anzahl der Felder des Schachbretts
# Rückgabewert: Matrix mit Einträgen 0 oder 1
# 1: steht eine Figur auf dem Feld x und beherrscht das Feld y, dann ist ADJ[x, y] = 1
# 0: falls das Feld nicht beherrscht wird. 
# BEACHTE: auch das Feld auf dem die Figur steht, erhält Eintrag 0, also ADJ[x, x] = 0

ADJ <- function(piece = c('q', 'r', 'b'), n = 3){
  n2 <- n*n
  fields <- seq_len(length.out = n2)
  ADJ <- matrix(data = vector(mode = "integer", length = n2*n2), nrow = n2)
  
  if(identical(piece, 'b')){    # Bishop
    for(i in fields){
      ADJ[i, ] <- dominatedFields(piece = 'b', n = n, field = i)
    }
  }
  if(identical(piece, 'r')){    # Rook
    for(i in fields){
      ADJ[i, ] <- dominatedFields(piece = 'r', n = n, field = i)
    }
  }
  if(identical(piece, 'q')){    # Queen
    for(i in fields){
      ADJ[i, ] <- dominatedFields(piece = 'q', n = n, field = i)
    }  
  }
  return(ADJ - diag(nrow = n2, ncol = n2))
}

Zeile 11 bis 13: Da hier immer n2 und nicht n benötigt wird, wird die Variable n2 gesetzt. Mit fields wird ein Vektor der Länge n2 vorbereitet; damit wird später über das Schachbrett iteriert, um alle Zeilen der Adjazenz-Matrix zu erzeugen. Ebenso wird die Adjazenz-Matrix vorbereitet.

Zeile 15 bis 29: Hier wird abgefragt, welche Figur gegeben ist. Abhängig davon wird über das Schachbrett mittels fields iteriert. In der Schleife wird jeweils eine Zeile der Adjazenz-Matrix gesetzt, wobei die eigentliche Arbeit von der Funktion dominatedFields() erledigt wird (siehe unten).

Zeile 30: Die Rückgabewerte von dominatedFields() sind so gemacht, dass auf der Hauptdiagonale der Adjazenz-Matrix Einsen stehen würden. Um eine echte Adjazenz-Matrix zu erzeugen, werden auf der Hauptdiagonale Nullen gesetzt (indem die Einheits-Matrix abgezogen wird.)

Das eigentliche Arbeitstier ist die Funktion dominatedFields():

# Erzeugen eines Vektors der zu einem gegebenen Feld field 
# die zugehörige Zeile in der Adjazenzmatrix erzeugt
# Beachte: für das Feld, auf dem die Figur steht, wird eine 1 erzeugt 
# (in der ADJ soll dort aber eine 0 stehen)

dominatedFields <- function(piece = c('q', 'r', 'b'), n = 3, field = 1){
  # Vorbereitungen: n^2; Schachbrett als Matrix
  n2 <- n*n
  board <- matrix(data = seq_len(length.out = n2), nrow = n, byrow = FALSE)
  
  # Vorbereitung des Rückgabewertes: Zeile der Adjazenz-Matrix zum Feld field
  # als Vektor der Länge n2
  ADJ.row <- vector(mode = "integer", length = n2)
  
  # lokale Funktionen dominatedByBishop() und dominatedByRook():
  # Rückgabewert: Vektor der Felder, die von einem Läufer bzw. Turm auf field bedroht werden
  # (field ist im Vektor enthalten)
  
  dominatedByBishop <- function(){    # Bishop
    # field enthalten in 1, 2, ..., n2
    idx.row <- field %% n
    if(idx.row == 0) idx.row <- n 
    idx.col <- ((field - 1) %/% n) + 1
    
    # Schablonen für die Läuferzüge
    # Schablone für Parallelen zur Hauptdiagonale:
    matrix.idx.leading <- outer(X = (1:n), Y = (1:n), FUN = "-")
    # Schablone für Parallelen zur Nebendiagonale:
    matrix.idx.secondary <- outer(X = (1:n), Y = (1:n), FUN = "+")
    
    # Haupt-Diagonalindex: Zeilenindex - Spaltenindex
    idx <- idx.row - idx.col
    # Auswahl der Indizes:
    dgl.selected.leading <- which(matrix.idx.leading == idx)
    
    # Neben-Diagonalindex: Zeilenindex + Spaltenindex
    idx <- idx.row + idx.col
    dgl.selected.secondary <- which(matrix.idx.secondary == idx)
    
    # Zugriff auf das eigentliche Schchbrett board mit Hilfe der Indizes:
    return( board[ union(dgl.selected.leading, dgl.selected.secondary) ] )
  }
  
  dominatedByRook <- function(){    # Rook
    idx.row <- field %% n
    if(idx.row == 0) idx.row <- n 
    idx.col <- ((field - 1) %/% n) + 1
    
    return( union( board[idx.row, ], board[ , idx.col] ) )
  }
  
  if(identical(piece, 'b')){    # Bishop
    # Aus bedrohten Feldern die Zeile der ADJ-matrix berechnen
    for(i in dominatedByBishop()){
      ADJ.row[i] <- 1L
    }
  }
  
  if(identical(piece, 'r')){      # Rook 
    for(i in dominatedByRook()){
      ADJ.row[i] <- 1L
    }
  }  
  if(identical(piece, 'q')){   # Queen
    br <- union(dominatedByBishop(), dominatedByRook())    # Bishop OR Rook
    for( i in br ){
      ADJ.row[i] <- 1L
    }
  }    # Ende der Abfrage Bishop, Rook, Queen
  
  return(ADJ.row)
}

Die beiden lokalen Funktionen dominatedByBishop() und dominatedByRook() berechnen zum gegebenen field alle Felder auf dem Schachbrett, die ein Läufer beziehungsweise Turm bedroht (oder schon besetzt; dieses Feld wird hier eingeschlossen). Insbesondere die Funktion dominatedByBishop() muss näher erklärt werden.

Die Berechnung über die Indizes wirkt zunächst sehr kompliziert. Sie beruht darauf, dass i + j oder i - j bei einem Läuferzug beziehungsweise i oder j bei einem Turm-Zug konstant bleiben

Die Berechnung wird besser verständlich, wenn man sich die Matrizen matrix.idx.leading <- outer(X = (1:n), Y = (1:n), FUN = "-") (Zeile 27) und matrix.idx.secondary <- outer(X = (1:n), Y = (1:n), FUN = "+") (Zeile 29) ansieht; hier im Beispiel mit n = 4:

n <- 4
matrix.idx.leading <- outer(X = (1:n), Y = (1:n), FUN = "-")
matrix.idx.leading
#      [,1] [,2] [,3] [,4]
# [1,]    0   -1   -2   -3
# [2,]    1    0   -1   -2
# [3,]    2    1    0   -1
# [4,]    3    2    1    0

matrix.idx.secondary <- outer(X = (1:n), Y = (1:n), FUN = "+")
matrix.idx.secondary
#      [,1] [,2] [,3] [,4]
# [1,]    2    3    4    5
# [2,]    3    4    5    6
# [3,]    4    5    6    7
# [4,]    5    6    7    8

Man erkennt, dass die Matrizen als Schablone für die Läufer-Züge verwendet werden können: Alle Einträge mit gleichen Werten entsprechen Läufer-Zügen parallel zur Hauptdiagonale (leading diagonal) beziehungsweise Neben-Diagonale (secondary diagonal). Mit Hilfe dieser Schablone werden die Felder auf dem Schachbrett bestimmt, die ein Läufer mit einem Zug erreichen kann (oder auf dem er gerade steht). Dies geschieht in Zeile 34 und 38. Für den eigentlichen Rückgabewert werden sie zu einem Vektor zusammengefasst (Zeile 41)

Für den Turm ist die entsprechende Rechnung einfacher, da man nur die Zeile und Spalte des vorbereiteten Schachbrettes board auswählen muss. Da in R die Zeilen und Spalten der Matrix von 1 bis n durchnumeriert sind, erscheint die Berechnung der Indizes kompliziert (siehe Zeile 45 bis 47). Man kann sich aber leicht davon überzeugen, dass field (mit Werten in 1, 2, ..., n2) in die richtigen Indizes umgerechnet wird.

Mit den Kommentaren im Quelltext, sollte der Rest der Implementierung verständlich sein.

Bildung aller möglichen Kombinationen, k Damen auf ein n x n-Schachbrett zu stellen

Hat man die Adjazenz-Matrix zu einer gegebenen Seitenlänge n des Schachbrettes gegeben, kann es nicht mehr schwer sein, über alle möglichen Kombinationen zu iterieren, k Damen auf dem Feld aufzustellen. Dabei muss für jede Kombination festgestellt werden, ob das gesamte Schachbrett beherrscht wird. Realisiert wird dies mit der Funktion combn(), womit alle Kombinationen von k (den K Damen) aus n2 (den Feldern des Schachbrettes) gebildet werden. Der schwierige Teil der Aufgabe besteht darin, eine geeignete Funktion zu finden, die eine Kombination auswertet – schwierig deswegen, weil diese Funktion sehr oft aufgerufen wird und daher maßgeblich die Rechenzeit beeinflusst.

Sämtliche Aufgaben werden in einer Funktion solutions() zusammengefasst:

  1. Adjazenz-Matrix berechnen (Zeile 3).
  2. Implementierung einer lokalen Funktion isSolution(), die prüft, ob eine Lösung vorliegt und sie ausgibt (Zeile 13 bis 23).
  3. Konfiguration und Aufruf von combn() (Zeile 25).
  4. Der Rückgabewert ist die Anzahl der untersuchten Kombinationen, nicht der Anzahl der Lösungen (Zeile 27).

Eine mögliche Implementierung von solutions() zeigt das folgende Skript:

solutions <- function(piece = c('q', 'r', 'b'), n = 3, k = 1, file = ""){
  
  adj <- ADJ(piece = piece, n = n)
  n2 <- n*n
  
  # v: Vektor der mit Damen besetzten Felder, der jeweils von combn() ausgewählt wurde
  # mit sapply() werden für jede Komponente von v dessen Nachbarn aus der ADJ bestimmt
  # sapply() verpackt die Ergebnisse in eine Liste, da später deren Vereinigungsmenge gebildet wird,
  # kann man unlist() anwenden und so einen Vektor erzeugen (hier sind manche Elemente noch mehrfach enthalten)
  # Vereinigungsmenge mit v bilden (besetzte Felder) und als Menge interpretieren (mit unique())
  # Feststellen, ob es eine Lösung ist; falls ja: Ausgabe und return(TRUE)
  
  isSolution <- function(v){
    fields <- unlist(sapply(X = v, FUN = function(x){  which(adj[x, ] == 1) }) )
    domFields <- union(v, fields)
    
    if(length(domFields) == n2){
      cat(v, "\n", file =  file, append =  TRUE)
      return(TRUE)
    }
    return(FALSE)
    # return()
  }
  
  solutions <- combn(x = n2, m = k, FUN = isSolution)
  # Rückgabewert: Anzahl der untersuchten Kombinationen; NICHT der Lösungen
  return(length(solutions))
}

Herzstück des Skriptes ist die Funktion combn(); sie wählt aus den n2 Feldern des Schachbrettes jeweils k Felder aus (Zeile 25). Dieser Vektor v mit k Komponenten wird dann an die Funktion FUN = isSolution übergeben, die dafür sorgen muss, dass er geeignet ausgewertet wird.

Diese Auswertung ist hier durch die lokale Funktion isSolution() realisiert (Zeile 13 bis 23):

Zusätzlich wird gezählt, wie viele Kombinationen insgesamt untersucht wurden (diese Anzahl kann man auch über einen Binomialkoeffizienten berechnen), siehe Zeile 27.

Einige Ergebnisse

Schachbrett mit Seitenlänge 3

Für n = 3 (siehe Abbildung 1) sieht man sofort, dass eine Dame auf dem Feld 5 ausreicht, um das Damenproblem zu lösen. Dazu müssen insgesamt 9 Möglichkeiten untersucht werden:

solutions(piece = 'q', n = 3, k = 1)
# 5 
# [1] 9

Zeile 1: Aufruf von solutions() für eine Dame und n = 3.

Zeile 2: Die Ausgabe der Lösung – die Dame muss auf dem Feld 5 stehen.

Zeile 3: Die Anzahl der untersuchten Möglichkeiten (Rückgabewert von solutions()).

Schachbrett mit Seitenlänge 4

Auch die Lösungen zu n = 4 wurden bereits identifiziert, siehe Abbildung 2. Hier ihre Berechnung:

solutions(piece = 'q', n = 4, k = 2)
# 1 11 
# 2 14 
# 3 15 
# 4 10 
# 5 8 
# 6 7 
# 6 10 
# 6 16 
# 7 11 
# 7 13 
# 9 12 
# 10 11 
# [1] 120

Man erhält 12 Lösungen, wobei jeweils 4 aufgrund ihrer Symmetrie gleichwertig sind. Die 3 qualitativ unterschiedlichen Lösungen wurden bereits in Abbildung 2 gezeigt.

Schachbrett mit Seitenlänge 5

Man kann sich leicht überlegen, dass bei n = 5 erst mit 3 Damen eine Lösung des Damenproblems konstruiert werden kann; die Überlegung wir weiter unten vorgestellt, wenn einige Eigenschaften der Adjazenz-Matrix untersucht werden.

Für 3 Damen gibt es 2300 Möglichkeiten, die im brute-force-Algorithmus abgearbeitet werden müssen und 186 davon lösen das Damenproblem. Einige Lösungen sind unten gezeigt. Um eine simple Darstellung der Lösungen zu erzeugen, wird die lokale Funktion isSolution() ein wenig erweitert. Falls eine Lösung vorliegt, wird ein rudimentäres Schachbrett mit den 3 Damen auf der Konsole gezeichnet:

board <- matrix(data = "__|", nrow = n, ncol = n)
        board[v] <- "Q |"
        options(quote = FALSE)
        apply(X = board, MARGIN = 1, FUN =  function(x){cat(x, "\n", file = file, append = TRUE)})
        cat("\n", file = file, append = TRUE)

Für die erste Lösung bei n = 5, also Damen auf 1 3 18 , wird dann folgende Ausgabe erzeugt:

1 3 18 
Q | __| __| __| __| 
__| __| __| __| __| 
Q | __| __| Q | __| 
__| __| __| __| __| 
__| __| __| __| __|

Die nächsten 4 Lösungen mit einer Dame auf dem Feld 1 lauten (mit "nächste Lösung" ist die Reihenfolge gemeint, die von combn() erzeugt wird):

1 5 18 
Q | __| __| __| __| 
__| __| __| __| __| 
__| __| __| Q | __| 
__| __| __| __| __| 
Q | __| __| __| __| 

1 7 19 
Q | __| __| __| __| 
__| Q | __| __| __| 
__| __| __| __| __| 
__| __| __| Q | __| 
__| __| __| __| __| 

1 8 12 
Q | __| __| __| __| 
__| __| Q | __| __| 
__| Q | __| __| __| 
__| __| __| __| __| 
__| __| __| __| __| 

1 8 23 
Q | __| __| __| __| 
__| __| __| __| __| 
__| Q | __| __| Q | 
__| __| __| __| __| 
__| __| __| __| __|

Schachbrett mit Seitenlänge 6

Bei n = 6 ist DN(6) = 3 und im brute-force-Algorithmus werden 7140 Möglichkeit untersucht; daruter sind aber nur 4 Lösungen (wegen der Symmetrie sind sie untereinander gleichwertig):

1 17 27 
Q | __| __| __| __| __| 
__| __| __| __| __| __| 
__| __| __| __| Q | __| 
__| __| __| __| __| __| 
__| __| Q | __| __| __| 
__| __| __| __| __| __| 

6 14 28 
__| __| __| __| __| __| 
__| __| Q | __| __| __| 
__| __| __| __| __| __| 
__| __| __| __| Q | __| 
__| __| __| __| __| __| 
Q | __| __| __| __| __| 

9 23 31 
__| __| __| __| __| Q | 
__| __| __| __| __| __| 
__| Q | __| __| __| __| 
__| __| __| __| __| __| 
__| __| __| Q | __| __| 
__| __| __| __| __| __| 

10 20 36 
__| __| __| __| __| __| 
__| __| __| Q | __| __| 
__| __| __| __| __| __| 
__| Q | __| __| __| __| 
__| __| __| __| __| __| 
__| __| __| __| __| Q |

Erscheinen die Lösungen bei n = 5 noch recht unregelmäßig angeordnet, sind bei n = 6 einige Besonderheiten erkennbar:

Die beiden letzten Punkte scheinen etwas überraschend: Wenn es schon sehr wenige Lösungen gibt, wird man eine gewisse "Außergewöhnlichkeit" erwarten. Damit ist gemeint, dass etwa ein Zentralfeld besetzt ist, weil von dort die meisten Felder bedroht werden oder dass die Damen so aufgestellt werden, dass sie möglichst wenige Felder gleichzeitig bedrohen – beides ist hier nicht der Fall. Und folglich würde ein greedy-Algorithmus, der versucht, die Damen auf Feldern zu postieren, wo sie möglichst viele Felder bedrohen und möglichst wenige Felder gleichzeitig bedrohen, diese Lösungen womöglich nicht berücksichtigen.

Schachbrett mit Seitenlänge 7

Bei n = 7 ist DN(7) = 4. Es werden 211876 Möglichkeiten untersucht, wobei es 86 Lösungen gibt. Auch hier gibt es sowohl Lösungen, bei denen die Damen unregelmäßig verstreut angeordnet oder eigenartig gruppiert erscheinen. Hier eine Auswahl:

1 14 24 40 
Q | __| __| __| __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| 
__| Q | __| __| __| __| __| 

2 13 22 33 
__| __| __| Q | __| __| __| 
Q | __| __| __| __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| __| Q | __| __| 
__| Q | __| __| __| __| __| 
__| __| __| __| __| __| __| 

20 29 37 45 
__| __| __| __| Q | __| __| 
__| __| __| __| __| Q | __| 
__| __| __| __| __| __| Q | 
__| __| __| __| __| __| __| 
__| __| __| __| __| __| __| 
__| __| Q | __| __| __| __| 
__| __| __| __| __| __| __| 

22 25 26 27 
__| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| 
__| __| __| Q | __| __| __| 
__| __| __| Q | __| __| __| 
__| __| __| __| __| __| __|

Schachbrett mit Seitenlänge 8

Der Fall n = 8 ist derjenige Fall, für den das Damenproblem ursprünglich formuliert wurde. Hier ist DN(8) = 5 und der brute-force-Algorithmus untersucht 7 624 512 Möglichkeiten; es gibt 4860 Lösungen.

Wie schon bei den kleineren Schachbrettern gibt es einige ungewöhnliche Konstellationen:

1 19 28 37 55 
Q | __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| Q | __| __| __| __| __| 
__| __| __| Q | __| __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| __| 

9 27 36 45 63 
__| Q | __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| Q | __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| Q | 
__| __| __| __| __| __| __| __| 

9 28 29 30 38 
__| Q | __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| 
__| __| __| Q | __| __| __| __| 
__| __| __| Q | Q | __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 

9 31 32 34 35 
__| Q | __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| 
__| __| __| Q | __| __| __| __| 

33 36 37 38 39 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __|

Schachbrett mit Seitenlänge 9

Für n = 9 gilt wieder DN(9) = 5 und es gibt 114 Lösungen; einige davon werden dargestellt:

11 19 44 68 
__| __| Q | __| __| __| __| __| __| 
__| Q | __| __| __| __| __| __| __| 
Q | __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| __| 
__| __| __| __| __| __| __| __| __|

4 12 20 28 61 
__| __| __| Q | __| __| __| __| __| 
__| __| Q | __| __| __| __| __| __| 
__| Q | __| __| __| __| __| __| __| 
Q | __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| Q | __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 

11 31 41 51 71 
__| __| __| __| __| __| __| __| __| 
__| Q | __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| __| 
__| __| __| __| Q | __| __| __| __| 
__| __| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| __| __| 

15 29 41 53 67 
__| __| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| Q | __| 
__| __| __| __| Q | __| __| __| __| 
__| Q | __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| __| 

22 34 41 48 60 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| Q | __| __| __| 
__| __| Q | __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| __| 
__| __| __| __| __| __| Q | __| __| 
__| __| __| Q | __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __|

Bemerkenswert ist vor allem die letzte gezeigte Lösung: Hier sind 4 Damen um die Dame auf dem Zentralfeld 41 gruppiert. Die Anordnung der 4 Damen ist nicht nur symmetrisch, sie sind gerade einen "Springer-Zug" vom Zentralfeld entfernt, also "1 Feld geradeaus und 1 Feld diagonal". Der Springer-Zug wird noch öfters vorkommen.

Bei der zuvor gezeigten Lösung 15 29 41 53 67 ist anstelle des Springer-Zuges der Zug "2 Felder geradeaus und 1 Feld diagonal" viermal enthalten.

Schachbrett mit Seitenlänge 10

Für n = 10 gilt (wie für n = 9) immer noch DN(10) = 5. Aber es gibt nur 8 Lösungen, die symmetrisch sind. Eine der Lösungen lautet:

3 29 45 61 87
__| __| __| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| __| __| 
Q | __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| __| __| __| 
__| __| Q | __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __|

Die 8 Lösungen lauten:

3 29 45 61 87 
4 30 46 62 88 
7 21 45 69 83 
8 22 46 70 84 
13 39 55 71 97 
14 40 56 72 98 
17 31 55 79 93 
18 32 56 80 94

Auch hier besetzen bei jeder Lösung alle 5 Damen Felder gleicher Farbe.

Schachbrett mit Seitenlänge 11

Man kann aus den 8 Lösungen für das 10 × 10-Schachbrett leicht die Lösungen für das 11 × 11-Schachbrett konstruieren. Die Vorgehensweise ist in Abbildung 3 dargestellt.

Abbildung 3: Konstruktion einer Lösung des Damenproblems für das 11 × 11-Schachbrett aus einer Lösung für das 10 × 10-Schachbrett. Genauere Erklärung im Text.Abbildung 3: Konstruktion einer Lösung des Damenproblems für das 11 × 11-Schachbrett aus einer Lösung für das 10 × 10-Schachbrett. Genauere Erklärung im Text.

Links ist eine der Lösungen für das 10 × 10-Schachbrett gezeigt. Wie jede der 8 Lösungen, enthält sie eine Dame auf einem Zentralfeld (das sind die 4 gekennzeichneten Felder 45, 46, 55, 56). Das 10 × 10-Schachbrett wird jetzt so zu einem 11 × 11-Schachbrett ergänzt, dass die Dame auf dem einzigen Zentralfeld steht (Nummer 61); die anderen Damen behalten ihre Lage relativ zur zentralen Dame. Man kann sich leicht davon überzeugen, dass die so entstandene Konfiguration das Damenproblem für das 11 × 11-Schachbrett löst.

Aufgabe: Warum entstehen mit dieser Konstruktion nur 2 Lösungen für das 11 × 11-Schachbrett aus den ursprünglich 8 Lösungen für das 10 × 10-Schachbrett? (Die zweite nicht in Abbildung 3 dargestellte Lösung lautet: 15 43 61 79 107.)

Um zu sehen, dass dies die einzigen Lösungen für das 11 × 11-Schachbrett sind, muss man den brute-force-Algorithmus laufen lassen – was einige Zeit beansprucht.

Die Konstellation, wie bei n = 11 benachbarte Damen zueinander stehen, mag überraschen (siehe rechtes Schachbrett in Abbildung 3, etwa die Damen auf den Feldern 19 und 61). Denn wie man in Abbildung 4 erkennt, gibt es auf einem 5 × 5-Schachbrett 4 Felder, die von einer Dame auf dem Zentralfeld nicht bedroht werden: dies sind gerade die Felder, die ein Springer bedrohen würde. Man könnte daher erwarten, dass benachbarte Damen so stehen, dass dazwischen kein "Springerfeld" liegt. Aber genau diese Erwartung wird nicht erfüllt: die benachbarten Damen sind genau 2 Springer-Züge voneinander entfernt und das "Springerfeld" wird von einer entfernten Dame bedroht.

Abbildung 4: Links: das 5 × 5-Schachbrett, in dem die Felder grau gekennzeichnet sind, die eine Dame nicht erreichen kann, wenn sie auf dem Zentralfeld steht; es sind gerade die Felder, die ein Springer erreichen könnte. Rechts: Ein Ausschnitt aus dem 11 × 11-Schachbrett mit zwei benachbarten Damen. Sie stehen gerade so, dass beide einen Springer-Zug von dem &quot;dazwischenliegenden&quot; Feld entfernt sind.Abbildung 4: Links: das 5 × 5-Schachbrett, in dem die Felder grau gekennzeichnet sind, die eine Dame nicht erreichen kann, wenn sie auf dem Zentralfeld steht; es sind gerade die Felder, die ein Springer erreichen könnte. Rechts: Ein Ausschnitt aus dem 11 × 11-Schachbrett mit zwei benachbarten Damen. Sie stehen gerade so, dass beide einen Springer-Zug von dem "dazwischenliegenden" Feld entfernt sind.

Weitere Eigenschaften der Adjazenz-Matrix

Die Adjazenz-Matrix erweckt nicht gerade den Eindruck als könnte man mit ihr leicht arbeiten und aus ihr Eigenschaften über Figuren-Konstellationen ablesen. Aber zumindest hat die Entwicklung des brute-force-Algorithmus gezeigt, wie man mit der Adjazenz-Matrix die Lösung des Damenproblems auf Abzählen, Projektionen (Zeilen der Matrix extrahieren) und Mengenoperationen zurückführen kann. In diesem Abschnitt sollen einige weitere Eigenschaften der Adjazenz-Matrix diskutiert werden.

Da die Adjazenz-Matrix für das 8 × 8-Schachbrett schon 64 Zeilen und Spalten besitzt, werden die meisten Eigenschaften nur mit dem 4 × 4-Schachbrett diskutiert. Die Skripte werden aber stets so geschrieben, dass man leicht eine andere Seitenlänge einsetzen kann.

Die Anzahl der bedrohten Felder

Die Zeilen-Nummer der Adjazenz-Matrix gibt das Feld auf dem Schachbrett an – wenn man sich an die Konvention hält, die in Abbildung 1 eingeführt wurde. Die i-te Zeile der Adjazenz-Matrix beschreibt dann, welche Felder eine Dame auf dem Feld i in einem Zug erreichen kann (Einträge 1) oder welche Felder sie nicht erreichen kann (Einträge 0). Bildet man daher die Zeilensumme, erhält man für jedes Feld die Anzahl der bedrohten Felder; in der Sprache der Graphentheorie sind es die benachbarten Knoten. Ordnet man die Felder wieder quadratisch an, erkennt man mit einem Blick, von welchem Feld aus wie viele andere Felder bedroht werden. Das folgende Skript führt die für das 4 × 4- und das 8 × 8-Schachbrett aus:

n <- 4

x <- (1:n)
adj <- ADJ(piece = 'q', n = n)
m <- matrix(data = rowSums(adj), nrow = n, ncol = n)
m
#      [,1] [,2] [,3] [,4]
# [1,]    9    9    9    9
# [2,]    9   11   11    9
# [3,]    9   11   11    9
# [4,]    9    9    9    9

n <- 8
# weitere Anweisungen wie oben
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
# [1,]   21   21   21   21   21   21   21   21
# [2,]   21   23   23   23   23   23   23   21
# [3,]   21   23   25   25   25   25   23   21
# [4,]   21   23   25   27   27   25   23   21
# [5,]   21   23   25   27   27   25   23   21
# [6,]   21   23   25   25   25   25   23   21
# [7,]   21   23   23   23   23   23   23   21
# [8,]   21   21   21   21   21   21   21   21

Möchte man die entsprechenden Zahlen für Turm oder Läufer sehen, muss man nur beim Bilden der Adjazenz-Matrix in Zeile 4 setzen: piece = 'r' oder piece = 'b' .

Die Potenzen der Adjazenz-Matrix

Bisher wurde die Adjazenz-Matrix lediglich als andere Darstellung des Graphen verwendet, insbesondere können aus ihren Zeilen sofort die benachbarten Felder abgelesen werden. Ausser diesen Projektionen wurden keine Operationen mit der Adjazenz-Matrix ausgeführt. Was passiert, wenn man die Adjazenz-Matrix mit sich selbst multipliziert – oder höhere Potenzen der Adjazenz-Matrix bildet?

Im folgenden Skript wird die Adjazenz-Matrix für das 4 × 4-Schachbrett mit sich selbst multipliziert (im Sinne der Matrizen-Multiplikation):

n <- 4
adj <- ADJ(piece = 'q', n = n)
adj %*% adj
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,]    9    4    5    4    4    6    7    6    5     7     4     5     4     6     5     4
# [2,]    4    9    4    5    4    6    6    7    7     6     7     3     6     2     6     5
# [3,]    5    4    9    4    7    6    6    4    3     7     6     7     5     6     2     6
# [4,]    4    5    4    9    6    7    6    4    5     4     7     5     4     5     6     4
# [5,]    4    4    7    6    9    6    6    2    4     6     7     6     5     7     3     5
# [6,]    6    6    6    7    6   11    6    6    6     6     8     7     7     6     7     4
# [7,]    7    6    6    6    6    6   11    6    7     8     6     6     4     7     6     7
# [8,]    6    7    4    4    2    6    6    9    6     7     6     4     5     3     7     5
# [9,]    5    7    3    5    4    6    7    6    9     6     6     2     4     4     7     6
# [10,]    7    6    7    4    6    6    8    7    6    11     6     6     6     6     6     7
# [11,]    4    7    6    7    7    8    6    6    6     6    11     6     7     6     6     6
# [12,]    5    3    7    5    6    7    6    4    2     6     6     9     6     7     4     4
# [13,]    4    6    5    4    5    7    4    5    4     6     7     6     9     4     5     4
# [14,]    6    2    6    5    7    6    7    3    4     6     6     7     4     9     4     5
# [15,]    5    6    2    6    3    7    6    7    7     6     6     4     5     4     9     4
# [16,]    4    5    6    4    5    4    7    5    6     7     6     4     4     5     4     9

Die Zahlen erscheinen zunächst nichtssagend, auffällig ist nur, dass alle größer oder gleich 2 sind. Vergegenwärtigt man sich aber, welche Bedeutung die Einträge in der Adjazenz-Matrix haben und welche Skalarprodukte hinter einen Matrizen-Multiplikation stecken, erschließt sich ihre Bedeutung.

Zum Beispiel steht in der ersten Zeile und ersten Spalte von adj %*% adj die Zahl 9. Multipliziert wurden dabei die erste Zeile und die erste Spalte von adj (im Sinne des Skalarproduktes). Die einzelnen Summanden im Skalarprodukt sind nur dann ungleich 0, wenn beide Faktoren gleich 1 sind. Dies ist gerade bei den 9 Nachbarn von 1 der Fall. Man kann die 9 daher so interpretieren: Es gibt 9 Wege, wie man in 2 Schritten von Feld 1 zu Feld 1 gelangen kann, nämlich indem man zuerst einen der 9 Nachbarn aufsucht und wieder zur 1 zurückkehrt.

Spielt man das etwa für die 2. Zeile und 14. Spalte von adj %*% adj durch, so müsste es 2 Pfade von 2 nach 14 geben. Betrachtet man Abbildung 2, so erkennt man, dass man nur über die beiden Nachbarn 6 und 10 in 2 Schritten von 2 zu 14 gelangen kann. Und genau diese Einträge werden im entsprechenden Skalarprodukt multipliziert.

Führt man das Skript für verschiedene Seitenlängen n aus, sieht man, dass erst ab n = 6 jedes Feld auf 4 Pfaden in 2 Schritten erreicht werden kann. (Siehe die entsprechende Aufgabe oben.)

Man kann die Interpretation auch umdrehen: Stellt man je eine Dame auf das Feld 2 und auf das Feld 14, so gibt es 2 Felder, die sie gleichzeitig bedrohen (genau die 2 Felder, über die man von 2 nach 14 in 2 Zügen ziehen könnte). Die Zahlen auf der Hauptdiagonale sind gerade die Anzahl an Feldern, die eine Dame auf dem Feld entsprechenden Feld bedroht (etwa 9 Felder von 1 aus).

Bildet man die 3. Potenz der Adjazenz-Matrix, so kann die zuletzt genannte Interpretation nicht übertragen werden; in der 3. Potenz kann man die Anzahl der Pfade ablesen, wie man in 3 Zügen von i nach j gelangt, indem man das Element in der i-ten Zeile und j-ten Spalte aufsucht. Hier wieder das Beispiel für n = 4:

n <- 4
adj <- ADJ(piece = 'q', n = n)
adj %*% (adj %*% adj)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,]   40   53   50   51   53   61   54   45   50    54    65    46    51    45    46    49
# [2,]   53   40   57   50   57   61   63   42   42    61    56    58    45    59    43    46
# [3,]   50   57   40   53   42   63   61   57   58    56    61    42    46    43    59    45
# [4,]   51   50   53   40   45   54   61   53   46    65    54    50    49    46    45    51
# [5,]   53   57   42   45   40   61   61   59   57    63    56    43    50    42    58    46
# [6,]   61   61   63   54   61   66   77   61   63    77    71    56    54    61    56    65
# [7,]   54   63   61   61   61   77   66   61   56    71    77    63    65    56    61    54
# [8,]   45   42   57   53   59   61   61   40   43    56    63    57    46    58    42    50
# [9,]   50   42   58   46   57   63   56   43   40    61    61    59    53    57    42    45
# [10,]   54   61   56   65   63   77   71   56   61    66    77    61    61    61    63    54
# [11,]   65   56   61   54   56   71   77   63   61    77    66    61    54    63    61    61
# [12,]   46   58   42   50   43   56   63   57   59    61    61    40    45    42    57    53
# [13,]   51   45   46   49   50   54   65   46   53    61    54    45    40    53    50    51
# [14,]   45   59   43   46   42   61   56   58   57    61    63    42    53    40    57    50
# [15,]   46   43   59   45   58   56   61   42   42    63    61    57    50    57    40    53
# [16,]   49   46   45   51   46   65   54   50   45    54    61    53    51    50    53    40

Wie oft wird ein Feld bedroht beziehungsweise beherrscht?

Ausgehend von einer gegebenen Lösung des Damenproblems kann man die Frage stellen: Wie oft werden die Felder 1, 2, ..., n2 bedroht? Oder wenn man die Positionen der Damen einbezieht: Wie oft werden die Felder 1, 2, ..., n2 beherrscht? Und wie kann man diese Zahlen aus der Adjazenz-Matrix berechnen?

Das folgende Skript zeigt die Funktion boardDomination(), die genau diese Berechnung durchführt:

boardDomination <- function(solution, n){
  # volle ADJ
  adj.n <- ADJ(piece = 'q', n = n)
  # Zeilen der ADJ für Figuren aus solution:
  adj.n.k <- adj.n[solution, ]
  # Spaltensummen bilden -> ergibt einen Vektor der Länge n * n
  sum.k <- colSums(adj.n.k)
  
  # Damen hinzufügen
  for(i in solution){
    sum.k[i] <- sum.k[i] + 1
  }
  return( matrix(data = sum.k, nrow = n, ncol = n) )
}

Es wird zuerst die Adjazenz-Matrix zur Seitenlänge n berechnet (Zeile 3). Anschließend werden diejenigen Zeilen ausgewählt, die duch die Lösung solution des Damenproblems gegeben sind (Zeile 5). Dies ist eine Matrix adj.n.k mit so vielen Zeile wie solution und n2 Spalten. Bildet man von dieser Matrix die Spalten-Summen (Zeile 7), so erhält man einen Vektor sum.k der Länge n2. Er beschreibt, wie oft ein Feld von den Damen aus solution bedroht wird. Fügt man jetzt noch jeweils 1 für eine Dame auf ihrer Position hinzu, erhält man die Zahlen, wie oft ein Feld beherrscht wird.

Im return-statement (Zeile 13) werden die n2 Zahlen wieder als Schachbrett angeordnet.

Im folgenden Skript werden damit einige Lösungen untersucht, die früher schon gezeigt wurden:

# 8x8-Schachbrett:

33 36 37 38 39 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| 

boardDomination(solution = c(33, 36, 37, 38, 39), n = 8)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
# [1,]    2    2    1    1    5    1    1    2
# [2,]    1    1    1    1    5    1    1    1
# [3,]    1    1    2    1    5    1    2    1
# [4,]    1    3    2    2    5    2    2    3
# [5,]    2    1    2    3    5    3    2    1
# [6,]    1    1    2    3    5    3    2    1
# [7,]    1    2    2    2    5    2    2    2
# [8,]    1    1    1    1    5    1    1    1

# 11x11-Schachbrett:

19 35 61 87 103
__| __| __| __| __| __| __| __| __| __| __| 
__| __| __| Q | __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| Q | __| 
__| __| __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| Q | __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __| __| 
__| Q | __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| __| __| __| __| 
__| __| __| __| __| __| __| Q | __| __| __| 
__| __| __| __| __| __| __| __| __| __| __| 

boardDomination(solution = c(19, 35, 61, 87, 103), n = 11)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
# [1,]    1    1    1    1    1    1    1    1    1     1     1
# [2,]    1    3    1    1    1    2    1    4    1     3     1
# [3,]    1    1    2    1    1    1    1    1    2     1     1
# [4,]    1    4    1    3    1    4    1    3    1     1     1
# [5,]    1    1    1    1    2    1    2    1    1     1     1
# [6,]    1    2    1    4    1    1    1    4    1     2     1
# [7,]    1    1    1    1    2    1    2    1    1     1     1
# [8,]    1    1    1    3    1    4    1    3    1     4     1
# [9,]    1    1    2    1    1    1    1    1    2     1     1
# [10,]    1    3    1    4    1    2    1    1    1     3     1
# [11,]    1    1    1    1    1    1    1    1    1     1     1

Man kann jetzt folgende Kontrollrechnung durchführen: Aus den Positionen der Damen einer Lösung kann man berechnen, wie viele Felder sie zusammen bedrohen (dies wurde im ersten Unterabschnitt Die Anzahl der bedrohten Felder berechnet. Addiert man alle Einträge aus der Matrix, die von boardDomination() erzeugt wird, muss dieselbe Anzahl herauskommen – bis auf die Anzahl der Damen.

Für das letzte Beispiel wird dies durchgespielt:

sum(boardDomination(solution = c(19, 35, 61, 87, 103), n = 11))
# [1] 173

# zum Vergleich:
m <- matrix(data = rowSums(ADJ(piece = 'q', n = 11)), nrow = 11, ncol = 11)
sum(m[c(19, 35, 61, 87, 103)])
# [1] 168

Die Differenz 5 entsteht dadurch, dass in der zweiten Berechnung die Anzahlen der bedrohten Felder addiert werden; addiert man die 5 Damen, ergibt sich die behauptete Gleichheit.

Aufgabe: Versuchen Sie aus der letzten Überlegung eine Abschätzung für DN(n) herzuleiten! (Leider ist sie nicht besonders gut.)