Möglichkeitenberechnung

[reyman]

Hallöchen liebe User, 

ich habe eine Aufgabe welche, so wie ich sie momentan mache, sehr langwierig ist. Nun dachte ich mir dass dies Per Excel gehen könnte. Da ich aber nicht der super gute Excel Programmierer bin, richte ich die Frage an euch. 

Und zwar geht es um Schach. Es ist die Aufgabe die Menge an Zügen zu zählen welche ein Turm zu einer bestimmten Position gehen kann. Damit sind die Kürzesten Wege gemeint.

Beispiel: Der Turm steht unten Links auf H8. Der weiße König auf F6 und der schwarze König auf E3. Diese dienen als Blockade. ( Bilder Original sind angehängt)
Ich habe das für eine Position schon manuell machen können, die Endposition ist mit dem Buchstaben Z bezeichnet. (Bild: Ziel1) Hier gibt es insgesamt 13 möglichkeiten mit den wenigsten schritten (8) ans Ziel zu kommen.

Beispiel 2: Spielfiguren stehen an gleicher stelle. Dieses mal soll der Turm zur Position E1 (die wenigsten schritte sind 10) gehen. (Bild: Ziel 2) Ich weiß nicht mehr ob ich alle Wege korrekt gezeichnet habe und komme da durcheinander. 

Für die Endposition A2 gibt es aber schon weit aus mehr. Und das schaffe ich wohl nicht mehr mit zeichnen. Und somit zu euch. Könnt Ihr mir helfen dies zu vereinfachen?

LG

[Zwenn]

Hallo reyman

irgend etwas fehlt an Deiner Aufgabenstellung bzw. Problembeschreibung, wenn ich nix übersehen habe. Denn wenn es um alle Möglichkeiten mit den wenigsten Zügen geht, um mit einem Turm von H8 auf F2 (Ziel 1) bzw. auf E1 (Ziel 2) zu gelangen, sind das in beiden Fällen 2 Züge, die für Ziel 1 zweimal und für Ziel 2 nur einmal möglich sind, weil hier einmal ein König im Weg steht.

Habe jetzt verstanden, dass ein Schritt immer die Bewegung zu einem Nachbarfeld ist.

Das Problem ansich gehört zur Gruppe der Backtracking Algorithmen. Aus dem Bereich Schach kennt man da vor allem das Acht Damen Problem. (Stelle 8 Damen so auf ein Schachbrett, dass keine eine andere schlagen kann). Hier ein Verweis auf Wikipedia, wo Du Dich einleitend belesen kannst, was Backtracking ist:
https://de.wikipedia.org/wiki/Backtracking

Wie das in Excel funktioniert, kannst Du Dir in einem Beispiel für den kürzesten Weg durch ein Labyrinth ansehen, das onur im Januar 2018 im Herber Forum veröffentlicht hat. Solltest Du gar nicht programmieren können, wird das aber zäh, da es nicht selbsterklärend ist. Das ist Stoff aus dem 2. Semester Informatik.
https://www.herber.de/forum/cgi-bin/call...ex=1603219

Sieh dieses Posting bitte nur als Hinweis an. Denn ich habe nicht vor das zu programmieren.


Viele Grüße,

Zwenn

[reyman]

Okay vielen Dank für deine Antwort. 
Ja so richtig programmieren kann ich nicht. Wenn ich etwas halbwegs verstehe versuche ich es meist umzubauen. Bei dem Thema stoße ich in jedem Fall an meine Granzen, weshalb ich auf Hilfe angewiesen bin. 

Deine Antwort hilft mir allerdings mit anderen Schlagwörtern das netz zu durchsuchen

[Ego]

Hallo r...,

du hast nicht geschrieben auf welcher Art du die möglichen Wege angezeigt bekommen möchtest. In der Anlage erst einmal eine Datei, in der alle Wege, die mit den wenigsten Schritten das Ziel erreichen, in jeweils einer Zelle ausgewiesen werden. Die Zellen des Brettes, die durchlaufen werden, werden mit der Zeilen- und Spaltennummer getrennt mit ":" ausgewiesen und die einzelnen Schritte durch ">" getrennt.

Das "Brett" (benannter Bereich) muss rechteckig sein. Es können auch mehrere "T" und "Z" eingetragen werden. Das Makro sucht die kürzesten Wege von einem "T" zu einem "Z" und berücksichtigt hierbei nicht die Zellen mit einem "K".
Ausgegeben werden die Wege unter der benannten Zelle "Ausgabe".

[Zwenn]

Jou,

ich komme für die erste Konstellation auch auf 13 Wege mit je 8 Schritten. Habe es aber manuell als Baum aufgebaut und erkläre mal das System dahinter.

Gegeben:

• Ein Feld mit 3x7 Feldern (H8 bis F2 auf einem Schachbrett)
  
• Spielfigur ist ein Turm
  
• Start ist H8
  
• Ziel ist F2
  
• Es steht ein Hindernis auf G6
  

Aufgabe:
Es sollen alle Wege aufgezeigt werden, die die wenigsten Schritte von H8 bis F2 abbilden. Dabei ist ein Schritt eine Bewegung um 1 Feld. Es gelten die Schachregeln für das Ziehen eines Turms. Es sind also nur vertikale und horizontale Züge erlaubt, wobei das Hindernis nicht übersprungen werden darf.

Lösungsweg:
Es handelt sich um ein Backtracking Problem. Diese Art von Problemen können in einer Baumstruktur abgebildet werden. Typischerweise werden Backtracking Probleme rekursiv gelöst. Die Startkonstellation kann aber ausgenutzt werden, um ausschließlich die kürzesten Wege zu verfolgen. Das liegt an den Positionen von Start und Ziel.

Für die Lösung gelten folgende Regeln, um nur die kürzesten Wege in einem Baum abzubilden:

• Der Turm darf nur nach oben und nach rechts gezogen werden
  
• Am Hindernis endet der Weg, ohne das Ziel zu erreichen
  
• Ist das Ziel erreicht, endet der Weg
  

Erklärung zu den erlaubten Zugrichtungen:
Da das Ziel oben und rechts vom Startfeld liegt, verlängert jeder Zug nach unten und links den Weg in jedem Fall. (Spoiler für Aufgabenstellung 2: Spalte E im 4x8 Feld, braucht unterhalb des 2. Hindernisses gar nicht berücksichtigt werden, weil auf jeden Fall ein Zug zurück auf Spalte F erfolgen muss. Also eine Bewegung nach links.)

Aufbau des Baumes:

• Als Wurzel wird H8 eingetragen
  
• Ebene 2: Ausgehend von H8 kann nur auf die beiden Felder H7 und G8 gezogen werden. Diese beiden Einträge werden eine Ebene unter dem Wurzelknoten H8 eingetragen und jeweils von H8 aus verbunden
  
• Ebene 3-1: Von H7 kann auf H6 und G7 gezogen werden. Diese beiden Knoten werden in Ebene 3 von H7 aus verbunden
  
• Ebene 3-2: Von G8 kann auf G7 und F8 gezogen werden. Diese beiden Knoten werden in Ebene 3 von G8 aus verbunden
  
• Ebene 4-1: Von H6 kann auf H5 gezogen werden. G6 ist verboten, da dieses Feld das Hindernis enthält
  
• Ebene 4-2: Von G7 kann auf F7 gezogen werden.G6 ist verboten, da dieses Feld das Hindernis enthält
  
• Ebene 4-3: Hier ist ebenfalls G7 der Elternknoten. Das bedeutet, ab hier ergibt sich der gleiche Teilbaum, wie unter dem Knoten 4.2
  
• ...
  

Das System sollte klar sein. Wird so ein Baum manuell aufgebaut oder als Liste aufgeschrieben, kann man sich die Arbeit für gleiche Teilbäume sparen. Sobald ein Eintrag mehr als einmal auftaucht, können die Teilbäume darunterzum Schluß kopiert und an die Zwillige verbunden werden. Wie gesagt erhält man auf diese Weise ausschließlich alle kürzesten Wege. Die Anzahl der Ebenen nach der Wurzel ergeben die notwendigen Schritte.

Grafisch als Baum sieht das dann so aus:
(Die roten Knoten sind das Feld mit dem Hindernis und gehören da eigentlich nicht rein, veranschaulichen aber, warum es da nicht weiter geht)
[Beim Verfassen eines Beitrages kann man ein Bild direkt einfügen. In der Vorschau wird dann aber nur der Hinweis gegeben, wie man Dateien anhängt. Deshalb als Anhang hochgeladen]

Erstellt habe ich den Baum mit dem yEd - Graph Editor (kostenlos):
https://www.yworks.com/products/yed

Ich hoffe diese Erklärung bringt etwas Licht ins Dunkel. Für Aufgabenstellung 2 müsstest Du das selber machen. Aber da Ego so nett war sich die Mühe zu machen das Problem allgemein mit einem Makro zu lösen, wirst Du Dir das wohl sparen ;)

Viele Grüße,

Zwenn

[reyman]

Oh man vielen Dank an euch für die Hilfe. An Ego das du dir die riesen Mühe gemacht hast und Zwenn für eine sehr gute Erklärung zu dem Ganzen. (Ja ich habe es mir in dem Fall gespart, aber werde mich in Zukunft damit auseinandersetzen. 
Ein Tipp eines Freundes war das Pascalsches Dreieck. Damit sollte es wohl auch gehen. Aber nun habe ich erstmal die richtigen antworten. 

Nochmal Vielen dank. :)

[Ego]

Hallo r...,

spätestens wenn Turm und Ziel in einer Reihe sind und dazwischen ein König, reicht ein binärer Baum nicht mehr aus.