Spiel in minimaler Anzahl Zügen erreichen

Hallo Liebe Community,

Ich steh gerade ziemlich auf dem Schlauch.
Ich habe eine Aufgabe in der folgende Aufgabenstellung gegeben ist:

Gegeben ist das folgende Spiel:
Gestartet wird ganz links, man kann mit der Figur entweder die in dem Feld angegebene Zahl nach rechts springen oder die ganzzahlige Hälfte nach links. Schafft man es, das Zielfeld zu erreichen? (Züge neben das Spielfeld sind nicht erlaubt!)

Zurückgegeben werden soll die Länge des kürzesten Weges (Im Beispiel 4).

So sieht mein Spielfeld aus. Das Zielfeld ist in diesem Beispiel die letze Zahl, also die 0.

----------------------------------------------------------------------------------------------
| 5 | 3 | 2 | 1 | 7 | 5 | 1 | 2 | 3 | 4 | 5  | 1  | 3  | 7  | 1  | 5  | 1  | 9  | 0  | 1  | 0  |
----------------------------------------------------------------------------------------------

So und nun hier noch die Klassen die ich dazu geschrieben habe:

Die Feld Klasse

public class Feld
    {
        private static int _zähler;
        private int _id;
        private int _wert;

        public Feld(int wert)
        {
            _id = _zähler;
            _zähler++;
            _wert = wert;
        }

        public int ID
        {
            get { return _id; }
        }

        public int Wert
        {
            get { return _wert; }
        }

        public bool Bekannt { get; set; }

        public bool LinksGelaufen { get; set; }

        public override string ToString()
        {
            return String.Format("ID: {0} Wert: {1}", _id, _wert);
        }
    }

Die Spielfeld Klasse:

public class Spielfeld
    {
        private List<Feld> _felder = new List<Feld>();

        public Spielfeld(string werteString)
        {
            if (string.IsNullOrEmpty(werteString)) throw new ArgumentNullException(nameof(werteString));

            string[] ReineZahlen = werteString.Split(',');

            foreach (var item in ReineZahlen)
            {
                int temp = 0;
                if (int.TryParse(item, out temp) == false) throw new FormatException("Keine Numerischen Werte");

                _felder.Add(new Feld(temp));

            }
        }

        public Feld Feld(int index)
        {
            return _felder[index];
        }

        public List<Feld> Felder { get { return _felder; } }

        public override string ToString()
        {
            var @string = new StringBuilder();
            foreach (var item in _felder)
            {
                @string.AppendLine(item.ToString());
            }
            return @string.ToString();
        }
    }

Die Spielfigur Klasse:

public class Spielfigur
    {
        private Spielfeld _spielfeld;
        private int _position;

        public Spielfigur(Spielfeld spielfeld, int startposition)
        {
            if (spielfeld == null) throw new ArgumentNullException(nameof(spielfeld));
            _spielfeld = spielfeld;

            if (startposition < 0 || startposition > _spielfeld.Felder.Count - 1) throw new IndexOutOfRangeException("Ungültige Startposition");
            _position = startposition;
        }

        public Feld AktuellesFeld
        {
            get { return _spielfeld.Feld(_position); }
        }
        public int AnzahlZüge { get;  set; }

        public void SetzePosition(int position)
        {
            _position = position;
        }
    }

die Grafik Klasse:

public class Grafik
    {
        private StringBuilder _feldGui = new StringBuilder();
        private Spielfeld _spielfeld;
        private Spielfigur _spielfigur;
        private int _zeile = 5;

        public Grafik(Spielfeld spielfeld, Spielfigur spielfigur)
        {
            if (spielfeld == null) throw new ArgumentNullException(nameof(spielfeld));
            _spielfeld = spielfeld;
            if (spielfigur == null) throw new ArgumentNullException(nameof(spielfigur));
            _spielfigur = spielfigur;
        }

        public void SchreibeLog()
        {
            Console.SetCursorPosition(0, _zeile);
            Console.WriteLine(_spielfigur.AktuellesFeld + " | Züge: " + _spielfigur.AnzahlZüge.ToString());
            _zeile++;
        }

        public void SageZielErreicht()
        {
            Console.SetCursorPosition(0, _zeile);
            Console.WriteLine("Ziel wurde erreicht");
            _zeile++;
        }

        public void SetzeFigur()
        {
            int position = _spielfigur.AktuellesFeld.ID * 4 + 2;

            Console.SetCursorPosition(position, 1);
        }

        public void ZeichneSpielfeld()
        {
            /* Beispiel:
             * ---------------------
             * | X | X | X | X | X |
             * --------------------- 
             * | 0 | 1 | 2 | 3 | 4 |
             * ---------------------
            */

            var leerzeichen = new StringBuilder();
            leerzeichen.Append(" ");

            //oberer Rahmen
            ZeichneRahmen();

            //Feldwerte zeichnen
            _feldGui.Append("| ");
            foreach (var item in _spielfeld.Felder)
            {
                if (item.ID < 10)
                    _feldGui.Append(item.Wert);
                else
                {
                    //leerzeichen.Append(" ");
                    _feldGui.Append(item.Wert + leerzeichen.ToString());
                }
                _feldGui.Append(" | ");
            }

            _feldGui.AppendLine();

            // Rahmen
            ZeichneRahmen();

            // ID's Zeichnen
            _feldGui.Append("| ");
            foreach (var item in _spielfeld.Felder)
            {
                _feldGui.Append(item.ID);
                _feldGui.Append(" | ");
            }
            _feldGui.AppendLine();

            //Rahmen
            ZeichneRahmen();

            Console.WriteLine(_feldGui);
        }

        private void ZeichneRahmen()
        {
            foreach (var item in _spielfeld.Felder)
            {
                _feldGui.Append("----");
                if (item.ID > 9)
                    _feldGui.Append("-");
            }
            _feldGui.Append("-");
            _feldGui.AppendLine();
        }
    }

Und die Spiellogik Klasse:

public class Spiellogik
    {
        private Spielfeld _spielfeld;
        private Spielfigur _spielfigur;
        private Grafik _grafik;

        public Spiellogik(Spielfeld spielfeld, Spielfigur spielfigur, Grafik grafik)
        {
            if (spielfeld == null) throw new ArgumentNullException(nameof(spielfeld));
            _spielfeld = spielfeld;
            if (spielfigur == null) throw new ArgumentNullException(nameof(spielfigur));
            _spielfigur = spielfigur;
            if (grafik == null) throw new ArgumentNullException(nameof(grafik));
            _grafik = grafik;

            _grafik.ZeichneSpielfeld();
            _grafik.SetzeFigur();
        }

        public void Start()
        {
            //Suchalorythmus
            var AktuellesFeld = _spielfigur.AktuellesFeld;

            _grafik.SchreibeLog();

            if (BinAmZiel() == false)
            {
                if (AktuellesFeld.LinksGelaufen == false)
                {
                    if (GeheNachLinks())
                    {
                        _spielfigur.AnzahlZüge++;
                        var gemerktesFeld = AktuellesFeld;
                        Start();
                        //Nachdem alle Wege erfolglos waren
                        _spielfigur.SetzePosition(gemerktesFeld.ID);
                    }
                }

                if (GeheNachRechts())
                {
                    _spielfigur.AnzahlZüge++;
                    Start();
                }
                //Wenn beide Wege nicht gehen
                _spielfigur.AnzahlZüge--;
            }
            else
            {
                _grafik.SageZielErreicht();
            }
        }

        private bool GeheNachRechts()
        {
            if (BinAmZiel() == false)
            {
                //Setzt die Eigenschaft des Aktuellen Feldes
                _spielfigur.AktuellesFeld.Bekannt = true;

                //Lese Feld aus auf dem die Figur gerade steht
                var aktuellesFeld = _spielfigur.AktuellesFeld;

                //Überprüfen ob der Zug möglich ist und auf keine bereits bekannte Position springt
                var neuePosition = aktuellesFeld.ID + aktuellesFeld.Wert;
                if (ZugGültig(true))
                {
                    var neuesFeld = _spielfeld.Feld(neuePosition);
                    if (neuesFeld.Bekannt == false)
                    {

                        //Spielfigur um Feldwert nach rechts verschieben
                        _spielfigur.SetzePosition(neuePosition);
                        _grafik.SetzeFigur();
                        //_spielfigur.AnzahlZüge++;
                        return true;
                    }
                }
            }
            return false;
        }


        private bool GeheNachLinks()
        {
            //Lese Feld aus auf dem die Figur gerade steht
            var aktuellesFeld = _spielfigur.AktuellesFeld;

            //Setzt die Eigenschaft des Aktuellen Feldes
            _spielfigur.AktuellesFeld.LinksGelaufen = true;
            _spielfigur.AktuellesFeld.Bekannt = true;

            //Überprüfen ob der Zug möglich ist und auf keine bereits bekannte Position springt
            var neuePosition = aktuellesFeld.ID - (aktuellesFeld.Wert / 2);
;
            if (ZugGültig(false))
            {
                var neuesFeld = _spielfeld.Feld(neuePosition);
                if (neuesFeld.Bekannt == false)
                {
                    //Spielfigur um Feldwert nach rechts verschieben
                    _spielfigur.SetzePosition(neuePosition);
                    _grafik.SetzeFigur();
                    //_spielfigur.AnzahlZüge++;
                    return true;
                }
            }
            return false;
        }

        private bool ZugGültig(bool istRechts)
        {
            var aktuellesFeld = _spielfigur.AktuellesFeld;

            if (istRechts)
            {
                var neuePosition = aktuellesFeld.ID + aktuellesFeld.Wert;
                if (neuePosition < _spielfeld.Felder.Count)
                    return true;
            }
            else
            {
                var neuePosition = aktuellesFeld.ID - (aktuellesFeld.Wert / 2);
                if (neuePosition >= 0)
                    return true;
            }
            //Console.WriteLine("Zug ist ungültig!");
            return false;
        }

        private bool BinAmZiel()
        {
            var aktuellesFeld = _spielfigur.AktuellesFeld;

            if (aktuellesFeld.ID == _spielfeld.Felder.Count - 1)
                return true;

            return false;
        }
    }

Meine Console schreibt dann dieses Log:

ID: 0 Wert: 5 | Züge: 0
ID: 5 Wert: 5 | Züge: 1
ID: 3 Wert: 1 | Züge: 2
ID: 4 Wert: 7 | Züge: 3
ID: 1 Wert: 3 | Züge: 4
ID: 11 Wert: 1 | Züge: 4
ID: 12 Wert: 3 | Züge: 5
ID: 15 Wert: 5 | Züge: 6
ID: 13 Wert: 7 | Züge: 7
ID: 10 Wert: 5 | Züge: 8
ID: 8 Wert: 3 | Züge: 9
ID: 7 Wert: 2 | Züge: 10
ID: 6 Wert: 1 | Züge: 11
ID: 9 Wert: 4 | Züge: 11
ID: 20 Wert: 0 | Züge: 8
Ziel wurde erreicht
ID: 20 Wert: 0 | Züge: 8
Ziel wurde erreicht

Die 8 Züge passen auch zu einem möglichen Weg um das Zielfeld zu erreichen allerdings ist das eben nicht der Kürzeste.

Wie kann ich es jetzt realisieren das ich am Ende die für den kürzesten Weg erforderlichen Züge angezeigt bekomme?

Ich hoffe Ihr könnt mir etwas auf die Sprünge helfen

Mit freundlichen Grüßen,
trex0113

Nach meinem Verständnis müsste das optimale Ergebnis so bestimmt werden können:

1. starte beim Ziel
   2.1 Solange du nicht am Start bist:
   2.2 ermittle die am weitesten links stehende Zahl, die so viele Schritte vom aktuellen Feld entfernt ist, wie ihr Zahlenwert ist.
   2.2.1 wenn es eine gibt, ist die das neue aktuelle Feld
   2.2.2 wenn es keine gibt, mach dasselbe nach rechts, aber mit dem ganzzahligen Anteil der Hälfte. des Zahlenwerts des Feldes, und nimm das am weitesten links stehende Feld.
2. drehe die Reihenfolge der gefundenen Felder um.

Ergebnis für dein Beispiel:
(Zahlenangabe: 8[4] ist die vierte 8 von links)
0[2]-7[2]-5[4]-5[3]-5[2]-5[1], also 6 Schritte.

EDIT: bei genauerem Nachdenken bin ich nicht mehr so sicher, dass man so die optimale Lösung findet, insb. weil man ebenso wie bei der Vorwärtssuche, die du machst, teilweise einige Schritte zurückgehen muss. Also mit Vorsicht genießen.

Grüße,

LaTino

Moin,
letztendlich ist es ein Baum, der hier aufgebaut werden muss und man sucht nach dem kuerzesten Weg. Dazu faellt mir der A* (A-Stern) Algorithmus ein:

A* Algorithm

Vielleicht hilft Dir das weiter.

Gruss,
DaMoe

Hm also das bringt mich doch schon mal etwas weiter. Allerdings weis ich nicht genau welche Werte ich auf g(n) und h(n) einsetzen soll.

Für g(n) vielleicht auf 1 weil die Kosten zum nächsten Feld sind ja quasi immer 1 Schritt
und für h(n) den Feldwert als Entfernung zum nächsten Feld?

aber das macht glaub wenig sinn weil h(n) ja eigentlich ein Schätzwert für den kleinsten Pfad von meinem Aktuellen Feld zum Ziel sein soll (Also quasi Luftlinie) aber was ist jetzt ein geeigneter Schätzwert für meine Konstellation? Was setze ich für g(n) und h(n) für werte ein?

Mit freundlichen Grüßen,
trex0113

Ich hatte gerade mal Langeweile

class Program
{
    static void Main( string[] args )
    {
        List<Field> fields = new List<Field> {
            new Field( 5 ),
            new Field( 3 ),
            new Field( 2 ),
            new Field( 1 ),
            new Field( 7 ),
            new Field( 5 ),
            new Field( 1 ),
            new Field( 2 ),
            new Field( 3 ),
            new Field( 4 ),
            new Field( 5 ),
            new Field( 1 ),
            new Field( 3 ),
            new Field( 7 ),
            new Field( 1 ),
            new Field( 5 ),
            new Field( 1 ),
            new Field( 9 ),
            new Field( 0 ),
            new Field( 1 ),
            new Field( 0 ),
            };

        ISearchAlgorithm<Field> searcher = new ASearchAlgorithm<Field>(
            getNeighbours: v => fields.Where( ( f, idx ) => idx == fields.IndexOf( v ) - v.Value / 2 || idx == fields.IndexOf( v ) + v.Value ).Where( f => f != v ),
            distBetween: ( a, b ) => 1,
            heuristicCostEstimate: ( a, b ) => Math.Abs( fields.IndexOf( a ) - fields.IndexOf( b ) )
            );

        for ( int i = 0; i < 10; i++ )
        {
            Console.Write( "Start von Feld {0}: ", i );
            try
            {
                var result = searcher.FindNearestPath( fields[ i ], fields.Last( ) ).ToList( );
                Console.WriteLine( "{0} ({1} Schritte)", string.Join( " -> ", result.Select( f => string.Format( "{0} ({1})", f.Value, fields.IndexOf( f ) ) ) ), result.Count );
            }
            catch ( Exception ex )
            {
                Console.WriteLine( ex.Message );
            }
        }
    }
}

public class Field
{
    public Field( int value )
    {
        if ( value < 0 )
            throw new ArgumentOutOfRangeException( nameof( value ) );

        Value = value;
    }

    public int Value { get; }

    public override string ToString()
    {
        return Value.ToString( );
    }
}

public interface ISearchAlgorithm<T>
    where T : class
{
    IEnumerable<T> FindNearestPath( T start, T goal );
}

public class ASearchAlgorithm<T> : ISearchAlgorithm<T>
    where T : class
{
    private readonly Func<T, IEnumerable<T>> _getNeighbours;
    private readonly Func<T, T, int> _distBetween;
    private readonly Func<T, T, int> _heuristicCostEstimate;

    public ASearchAlgorithm( Func<T, IEnumerable<T>> getNeighbours, Func<T, T, int> distBetween, Func<T, T, int> heuristicCostEstimate )
    {
        if ( getNeighbours == null )
            throw new ArgumentNullException( nameof( getNeighbours ) );
        if ( distBetween == null )
            throw new ArgumentNullException( nameof( distBetween ) );
        if ( heuristicCostEstimate == null )
            throw new ArgumentNullException( nameof( heuristicCostEstimate ) );
        _getNeighbours = getNeighbours;
        _distBetween = distBetween;
        _heuristicCostEstimate = heuristicCostEstimate;
    }

    public IEnumerable<T> FindNearestPath( T start, T goal )
    {
        HashSet<T> closedSet = new HashSet<T>( );
        HashSet<T> openSet = new HashSet<T>( ) { start };

        Dictionary<T, T> cameFrom = new Dictionary<T, T>( );
        Dictionary<T, int> gScore = new Dictionary<T, int>( ) { [ start ] = 0 };
        Dictionary<T, int> fScore = new Dictionary<T, int>( ) { [ start ] = _heuristicCostEstimate( start, goal ) };

        T current;
        while ( openSet.Any( ) )
        {
            current = openSet.OrderBy( v => fScore[ v ] ).First( );
            if ( current == goal )
                return ReconstructPath( cameFrom, current );

            openSet.Remove( current );
            closedSet.Add( current );

            foreach ( var neighbour in _getNeighbours( current ) )
            {
                if ( closedSet.Contains( neighbour ) )
                    continue;

                var tentative_gScore = gScore[ current ] + _distBetween( current, neighbour );
                if ( !openSet.Contains( neighbour ) )
                    openSet.Add( neighbour );
                else if ( tentative_gScore >= gScore[ neighbour ] )
                    continue;

                cameFrom[ neighbour ] = current;
                gScore[ neighbour ] = tentative_gScore;
                fScore[ neighbour ] = gScore[ neighbour ] + _heuristicCostEstimate( neighbour, goal );
            }
        }

        throw new InvalidOperationException( "No path found" );
    }

    private IEnumerable<T> ReconstructPath( Dictionary<T, T> cameFrom, T current )
    {
        List<T> totalPath = new List<T>( ) { current };
        while ( cameFrom.ContainsKey( current ) )
        {
            current = cameFrom[ current ];
            totalPath.Add( current );
        }

        totalPath.Reverse( );

        return totalPath;
    }
}

Als Ergebnis kommt

Start von Feld 0: 5 (0) -> 5 (5) -> 5 (10) -> 5 (15) -> 0 (20) (5 Schritte)
Start von Feld 1: 3 (1) -> 7 (4) -> 1 (11) -> 3 (12) -> 5 (15) -> 0 (20) (6 Schritte)
Start von Feld 2: 2 (2) -> 7 (4) -> 1 (11) -> 3 (12) -> 5 (15) -> 0 (20) (6 Schritte)
Start von Feld 3: 1 (3) -> 7 (4) -> 1 (11) -> 3 (12) -> 5 (15) -> 0 (20) (6 Schritte)
Start von Feld 4: 7 (4) -> 1 (11) -> 3 (12) -> 5 (15) -> 0 (20) (5 Schritte)
Start von Feld 5: 5 (5) -> 5 (10) -> 5 (15) -> 0 (20) (4 Schritte)
Start von Feld 6: 1 (6) -> 2 (7) -> 4 (9) -> 7 (13) -> 0 (20) (5 Schritte)
Start von Feld 7: 2 (7) -> 4 (9) -> 7 (13) -> 0 (20) (4 Schritte)
Start von Feld 8: 3 (8) -> 1 (11) -> 3 (12) -> 5 (15) -> 0 (20) (5 Schritte)
Start von Feld 9: 4 (9) -> 7 (13) -> 0 (20) (3 Schritte)

Die heuristische Funktion ist bestimmt noch verbesserungswürdig ...

Gute Implementierung!
Nur die Anzahl der ausgegebenen Schritte ist wohl jeweils um 1 zu groß - und dann kommt man bei dem Beispiel (Start von Feld mit Index 0) auch auf minimal 4 Schritte (ist ja einfach immer 5 vorwärts).

Stimmt, das mit der Schrittanzahl ist ein Anzeigefehler 😁

Die Implementierung ist 1:1 der Pseudocode von Wikipedia (also nicht wirklich mein Verdienst) 😉

Okay das übersteigt nun so ziemlich mein Wissen. Bisher habe ich mich weder mit Interface noch mit Func beschäftigt.
Aber seh ich das richtig das der Code auch nur in eine Richtung (nach rechts) geht und schritte nach links gar nicht beachtet?
z.B. bei diesem Feld ist es zwingend nötig auch schritte nach links zu gehn um zum Ziel zu kommen:

-----------------------------------------
| 4 | 1 | 4 | 2 | 3 | 7 | 3 | 5 | 6 | 1 |
-----------------------------------------

was genau macht den dieser Code hier:

ISearchAlgorithm<Field> searcher = new ASearchAlgorithm<Field>(
            getNeighbours: v => fields.Where( ( f, idx ) => idx == fields.IndexOf( v ) - v.Value / 2 || idx == fields.IndexOf( v ) + v.Value ).Where( f => f != v ),
            distBetween: ( a, b ) => 1,
            heuristicCostEstimate: ( a, b ) => Math.Abs( fields.IndexOf( a ) - fields.IndexOf( b ) )
            );

Ich bin noch ein ziemlicher Anfänger im Programmieren. Wäre schön wenn mir einer das ganze erklären kann was genau jetzt da passiert.

Mit freundlichen Grüßen,
trex0113

z.B. bei diesem Feld ist es zwingend nötig auch schritte nach links zu gehn um zum Ziel zu kommen:

  
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |  
-----------------------------------------  
| 4 | 1 | 4 | 2 | 3 | 7 | 3 | 5 | 6 | 1 |  
-----------------------------------------  
  

Computer sagt

Start von Feld 0: 4 (0) -> 3 (4) -> 2 (3) -> 4 (2) -> 3 (6) -> 1 (9) (5 Schritte)
Start von Feld 1: 1 (1) -> 4 (2) -> 3 (6) -> 1 (9) (3 Schritte)
Start von Feld 2: 4 (2) -> 3 (6) -> 1 (9) (2 Schritte)
Start von Feld 3: 2 (3) -> 4 (2) -> 3 (6) -> 1 (9) (3 Schritte)
Start von Feld 4: 3 (4) -> 2 (3) -> 4 (2) -> 3 (6) -> 1 (9) (4 Schritte)
Start von Feld 5: 7 (5) -> 4 (2) -> 3 (6) -> 1 (9) (3 Schritte)
Start von Feld 6: 3 (6) -> 1 (9) (1 Schritte)
Start von Feld 7: 5 (7) -> 7 (5) -> 4 (2) -> 3 (6) -> 1 (9) (4 Schritte)
Start von Feld 8: 6 (8) -> 7 (5) -> 4 (2) -> 3 (6) -> 1 (9) (4 Schritte)
Start von Feld 9: 1 (9) (0 Schritte)

Wie man sieht, geht der auch mal links 😉

was genau macht den dieser Code hier:

Der Code erstellt eine Instanz von ASearchAlgorithm. Der Algorithmus ist allgemeingültig und braucht nur diese drei Methoden/Closures um die möglichen Züge (getNeighbours), die Distanzen und heuristische Distanzwerte zu ermitteln.

Ich teile also dem Algorithmus darüber die Logik des Spiels mit und der kann dann nach dieser Logik den kürzesten Weg ermitteln.

Hallo trex0113,

falls dir die Syntax "v => ..." oder "( a, b ) => ..." nichts sagt, dies sind Lambda-Ausdrücke (d.h. verkürzte Schreibweise von anonymen [namenlosen] Methoden): [Artikel] Delegaten, anonyme Methoden, Lambda-Ausdrücke & Co.

Und "getNeighbours:" etc. sind "named parameters", s.a. Benannte und optionale Argumente (diese könnte man hier auch weglassen - Sir Rufo hat diese der besseren Lesbarkeit hinzugefügt, man könnte auch eine entsprechend benannte (in diesem Fall Func<...>-) Variable dafür verwenden.

okay ich hab mir jetzt das ganze mal durchgelesen aber nur die hälfte davon verstanden. Lambda's machen das ganze ja ehr schlimmer lesbarer als anders rum...

Also gut mit den Zeilen hier habe ich immer noch Probleme zu verstehen:

getNeighbours: v => fields.Where( ( f, idx ) => idx == fields.IndexOf( v ) - v.Value / 2 || idx == fields.IndexOf( v ) + v.Value ).Where( f => f != v ),
            distBetween: ( a, b ) => 1,
            heuristicCostEstimate: ( a, b ) => Math.Abs( fields.IndexOf( a ) - fields.IndexOf( b ) )

Das ist mal das was ich meine das es ist:

'getNeighbours' bekommt ein Feld('v') als Parameter übergeben. 'v' wird definiert indem ich durch die Liste von Feldern ('fields') die nächsten beiden felder hole. Dabei muss 'idx' berechnet werden indem ich mir den Index des aktuellen Feldes hole und den entweder den Wert des Feldes addiere oder subtrahiere und durch zwei teile.
Was genau macht aber jetzt das letze .Where( f => f != v )?

'distBetween' bekommt als Parameter 2 'Field' ('a' , 'b') entgegen und liefert einen 'Int' zurück. Dieser 'Int' wird mit 1 definiert?

'heuristicCostEstimate' bekommt als Parameter auch 2 'Field' ('a' , 'b') und liefert einen 'Int' zurück. Dieser wird berechnet indem von Feld 'a' und 'b' der Index genommen wird und subtrahiert wird. (Also von Start zum Ziel würde dann -19 rauskommen? Weil Start hat Index 0 und Ziel Index 19)

Ist das soweit korrekt wie ich das verstanden habe?

BTW: Ich kann mir kaum vorstellen das diese Aufgabe so schwer ist zu lösen da sie vom Ersten Semester Studiengang Informatik aus der Programmiersprache C kommt.

Der A*-Algorithmus ist ja nur eine Verbesserung des Dijkstra-Algorithmus, welcher für Graphen mit verschiedenen Kantengewichtungen angewendet wird (dies ist hier aber nicht der Fall, daher im Code von Sir Rufo immer distBetween: (a, b) => 1).

Bei deinem Problem gibt es ja je Zug nur maximal 2 Möglichkeiten (vor oder rückwarts) - welche gleich gut sind, d.h. das kann man auch mit einfacheren Mitteln lösen.

Gedacht ist es wohl eher dieses Problem mittels eines Backtracking-Algorithmus zu lösen, welcher alle Möglichkeiten durchgeht und den besten ermittelt (d.h. mittels der Tiefensuche).

Um direkt den kürzesten Zug zu ermitteln, eignet sich aber am besten die Breitensuche, d.h. sobald man das Ziel erreicht hat, hat man über die Suchtiefe die Anzahl der minimalen Schritte.