Königswege

Wir betrachten folgende Problemstellung:
Auf einem Schachbrett der Größe (n,n) steht in der linken, unteren Ecke ein König.Wieviele verschieden Wege kann dieser König gehen, um das rechte obere Feld zu erreichen, wenn sich bei jedem Zug den Abstand zum Ziel nicht vergrößert?

Grundsätzlich erhalten wir die Lösug aus folgender Überlegung:

Ausgehend von der Startposition werden die möglichen Züge bestimmt. Jeder mögliche Zug wird dann an die bis dahin ermittelten Wege bis zum aktuellen Feld angehängt.

Wir zerlegen das Problem in Teilprobleme die wir getrennt lösen und am Ende zu einer Funktion zusammensetzen,die alle möglichen Königswege bestimmt.

Defintion des Spielfeldes (Schachbrett)

Definition der Abstandsfunktion, die den Abstand von der aktuellen Position zum Ziel berechnet

Bestimmung der möglichen Züge, die vom Feld (i,j) aus gemacht werden können

Anhängen der möglichen Züge an eine Liste von bereitsw getätigten Zügen

Definition des Spielfeldes

Dieser Schritt ist einfach, wir definieren wir für jedes n das Spielfeld der Größe (n,n) als quadratische Matrix:

brett[n_]:=Table[{i,j},{i,1,n},{j,1,n}]

b4=brett[4]

Die aktuelle Position des Königs wird dann durch das Zahlenpaar (i,j) repräsentiert.

Bestimmung des Abstands zum Ziel

Die Bestimung des Abstands zwischen zwei Feldern auf dem Spielbrett wird einfach durch die Addition der Abstände in jeder Koordinatenachse ("x-Richtung" und "y-Richtung") vorgenommen. Sie läßt sich einfach durch

abstand[x_,y_]:=Plus @@ (Abs @ (x-y))

realisieren. Für ein Spielfeld der Größe 4 erhalten wir:

start={1,1}; ziel={4,4};

abstand[start,ziel]

oder den Abstandt zum Feld (1,3)

abstand[start,{1,3}]

Bestimmung der möglichen Züge

Auf dem Weg zur Lösung implementieren wir nun einen "Zuggenerator", der, ausgehend von der aktuellen Posotion, hier (a,b) diejenigen Zellen bestimmt auf die der König ziehen, kann, ohne den Abstand von der Zielzelle zu vergrößern. Dazu werden zunächst alle Nachbarzellen der Zelle (a,b) bestimmt:

nachbarn[{a_,b_}]:=Flatten[Table[{a-i,b-j},{i,-1,1,1},{j,-1,1,1}],1];

temp=nachbarn[{3,4}]

Unter diesen, so bestimmte Zellen können (und werden in der Regel auch) Zellen sein, die nicht auf dem Spielfeld liegen. Diese werden  wie folgt ausgefiltert:

Select[temp,((#[[1]]>0))&&(#[[2]]>0)&&(#[[1]]≤4)&&((#[[2]]≤4))&]

Die aktuelle Position wird ebenfalls aus der Liste der möglichen Züg entfernt, da der König ja schließlich ziehen soll. Damit erhält man die Kandidaten für neue Züge:

cands=Complement[Select[temp,((#[[1]]>0))&&(#[[2]]>0)&],{start}]

Als mögliche Kandidaten kommen alle Züge in Betracht, die den Abstand zum Ziel verringern. Da beim Verlassen des Spielfeldes sich der Abstand zum Ziel auf jeden Fall vergrößert, ist die zuvor getroffene Überlegung des Zuggenerators im Grunde nicht nötig. Es genügt, diejenigen Züge auszuwählen, die den Abstand verringern. Diese wählen wir wie folgt aus:

kandidaten[position_,brett_,ziel_]:=Module[{cands=nachbarn[position],dist},
dist=abstand[position,ziel];                       (* Abstnad bestimmen *)
Select[cands,(abstand[#,ziel]<dist)&] (* zulässige Züge *)
]

Beispielsweise erhält man für die ersten Zugmöglichkeiten:

cands=kandidaten[start,b4,ziel]

Generieren der möglichen Wege

Im letzten Schritt der Lösung werden, ausgehend von der Starposition, die hier als Weg mit nur einem Feld, dem Startfeld, verwendet wird, die neuen, möglichen Wege generiert. Dazu wird als erstes für alle bereits bestimmten Wege die möglichen nächsten Felder berechnet und diese dann an den jeweiligen Weg angehängt. Die Aufgabe übernimmt die Funktion zuganhaengen. Sie fügt an einen gegebenen Weg alle möglichen Züge an und gibt eine Liste neuer Wege aus.

zuganhaengen[wegliste_,brett_,ziel_]:= Module[{temp,aktuelleListe=wegliste,aktuellerWeg,workList={},wegListetemp,zuege},
Do[aktuellerWeg=aktuelleListe[[i]]; (* Für jeden Weg der aktuellen Liste*)
temp = aktuellerWeg[[Length[aktuellerWeg]]];
zuege=kandidaten[temp,brett,ziel]; (* mögliche neue Felder *)
wegListetemp=Append[aktuellerWeg,#]&/@zuege; (*neue Zuege an aktuellen Weg dranhaengen*)
AppendTo[workList,wegListetemp] (*neue Wege an die workList anhängen *)                                                          
,{i,1,Length[aktuelleListe]}];
Flatten[workList,1]
]

Beispielswiese für den Startpunkt und ein Brett der Größe 3

zuganhaengen[{{{1,1}}},brett[3],{3,3}]

Nun kann die Lösung implementiert werden. Ausgehend vom Startweg, der nur die Startposition enthält, werden für jeden Weg die jeweiligen möglichen Züge bestimmt und mit der Funktion zuganhaengen an den jeweils aktuellen Weg angehängt. Anschließend werden alle Wege die bereits das Zielfeld enthalten aus den aktuellen Wegen entfernt und in die Liste der gefundenen Lösungen aufgenommen.

koenigswege[wegliste_,brett_,ziel_]:=Module[{Loesungen={},aktuelleListe=wegliste,workList={},aktuellerWeg, zuege,wegListetemp},
While[Length[aktuelleListe]>0, (*Solange noch Wege unvollständig, d.h. vorhanden, sind*)
workList:=zuganhaengen[aktuelleListe,brett,ziel];
(* gefundene Lösungen herausfiltern*)
If[Or @@ (MemberQ[#,ziel]& /@ workList),
wegListetemp=Select[workList,MemberQ[#,ziel]&]; (* Ziel erreicht *)
AppendTo[Loesungen,wegListetemp];
aktuelleListe=Complement[workList,wegListetemp]
,aktuelleListe=workList;
]  (* Ziel noch nicht erreicht*)
];
Loesungen= Flatten[Loesungen,1];
{Length[Loesungen],Loesungen}
]

koenigswege[{{start}},brett[3],{3,3}]

Rekursive Lösung:

GraphicsGrid[{{Graphics[{Rectangle[],Inset[Style["i, j-1",Red, Bold,24],{0.5,0.5}]}],Graphics[{Blue,Rectangle[],Inset[Style["i, j",Black,Bold,24],{0.5,0.5}]}]},{Graphics[{Rectangle[],Inset[Style["i-1, j-1",Red, Bold,24],{0.5,0.5}]}],Graphics[{Rectangle[],Inset[Style["i-1, j",Red, Bold,24],{0.5,0.5}]}]}}]

Die Anzahl der Wege zur Position (i,j) ergibt sich einfach als Summe der Anzahl der Wege zu den Positionen (i,j-1), (i-1,j-1) und (i-1,j). Wir können daher eine Funktion wege(i,j) rekursic definieren, derart, daß wege(n,n) die Anzahl der Wege ausgibt, die es für den König auf einem n×n gibt.

wege[1,1]:=1;

wege[1,_]:=1;

wege[_,1]:=1;

wege[i_,j_]:=wege[i-1,j-1]+wege[i,j-1]+wege[i-1,j]/;((i>1)&&(j>1));

Für ein Brett der Größe 5 erhalten wir, wie bereits mit der obigen, expliziten, Lösung erhalten

wege[5,5]

Für ein 8×8 Schachbrett erhält man:

wege[8,8]