"8 Puzzle" lösen mit A* Algo - "Neighbor function"

[Lyan]

Hallo,

bin vor kurzem nochmal auf den A*-Algorithmus gestoßen.
Wollte diesen verwenden um ein 8-Puzzle zu lösen.

Ich habe das Puzzle in einem Array vorliegen: 0 1 2 3 4 5 6 7 8

Bildlich so:

0 1 2
3 4 5
6 7 8

Die sogenannte Neighbor-function soll alle Nachbarn eines Array-Indexes ermitteln.
Nachbarn sind all die Zahlen, die ein Feld vertikal oder horizontal von dem Array-Index entfernt liegen.

Beispiel: Neighbors(4) würde die Zahlen 1,5,7,3 zurückliefern. Neighbors(6) würde hingegen 7, 3 zurückliefern.


Meine Funktion ist nicht so toll ich hätte lieber eine schöne Lösung, wenn möglich mit Operatoren/Mathematisch anstelle von vielen Prüfungen/if's etc.

Also gesucht ist eine schöne, einfache, kurze Implementation der Neighbor-function.


Vielen Dank im voraus

[Sherlock]

Ja, wie sieht denn Deine Lösung aus? Nicht das man da etwas baut, das am Ende identisch wird...

Sherlock

[Lyan]

Zitat von Sherlock:

Ja, wie sieht denn Deine Lösung aus? Nicht das man da etwas baut, das am Ende identisch wird...

Sherlock

Naja, prüfen ob 0 =< index+3/-3 <= 8 ist. Für die +1/-1 ists halt eklig. Mir ist wie gesagt nichts gutes eingefallen...(index+1) mod 3 um zu prüfen ob am Rand usw. ist halt ungeschickt.. hätte gerne die einfache Lösung die ich gerade nicht sehe

[Uwe Raabe]

So ganz ohne if wird es wohl nicht gehen. Hier mein Vorschlag:

Delphi-Quellcode:

function Neighbours(zahl: Integer): TArray<Integer>;
var
  lst: TList<Integer>;
  c: Integer;
  r: Integer;
begin
  lst := TList<Integer>.Create;
  try
    c := zahl mod 3;
    r := zahl div 3;
    if r > 0 then
      lst.Add(zahl-3);
    if c > 0 then
      lst.Add(zahl-1);
    if c < 2 then
      lst.Add(zahl+1);
    if r < 2 then
      lst.Add(zahl+3);
    result := lst.ToArray;
  finally
    lst.Free;
  end;
end;

[SProske]

Mit X - 3 > -1 kannst du prüfen, ob es einen oberen Nachbarn gibt, diesen erhälts du dann mit X - 3.
Mit X + 3 < 9 kannst du prüfen, ob es einen unteren Nachbarn gibt, diesen erhälts du dann mit X + 3.
Mit X mod 3 <> 0 kannst du prüfen, ob es einen linken Nachbarn gibt, diesen erhältst du mit X - 1.
Mit (X + 1) mod 3 <> 0 kannst du prüfen, ob es einen rechten Nachbarn gibt, diesen erhältst du mit X + 1.

Wobei X der Index deines Arrays ist und der berechnete Wert der Index des entsprechenden Nachbarn.

[Neutral General]

Wenn es immer 3x3 ist kannst du dir theoretisch 9 Konstante Arrays mit den Nachbarn für jeden Index anlegen.
Ist dann zur Laufzeit auch richtig schnell.

Algorithmisch ist das natürlich Ödland. Kommt drauf an auf was du wert legst. (oder auf was der Fragesteller wert legt)

[Lyan]

Die Lösung von Uwe ist schon besser und etwas kompakter als meine eigene - habe die nun vorab auch übernommen, danke dafür!

Zitat von Neutral General:

Algorithmisch ist das natürlich Ödland. Kommt drauf an auf was du wert legst. (oder auf was der Fragesteller wert legt)

Ich möchte die Funktion so kompakt wie möglich halten. Mir ist leider nichts eingefallen mit dem ich wirklich zufrieden bin.

[Uwe Raabe]

Na ja, etwas kompakter ginge es schon so (allerdings mit Sets, weil TArray<Integer> nicht als Konstante geht):

Delphi-Quellcode:

const
  Neighbours: array[0..8] of set of 0..8
             = ([1,3], [0,2,4], [1,5],
                [0,4,6], [1,3,5,7], [2,4,8],
                [3,7], [4,6,8], [5,7]);

Damit wird auch das Überprüfen auf Nachbarschaft einfacher.

Delphi-Quellcode:

{ is A neighbour of B }
A in Neigbours[B];

Das Iterieren geht genauso:
for A in Neighbours[B] do ...

[BUG]

Ich weiß nicht genau was du vorhast, habe aber den Verdacht das dir der A* so nicht weiter hilft. Welchen kürzesten Weg möchtest du denn finden?

Ich vermute, das du eigendlich A* auf einem anderen Graph ausführen müsstet, wo der Gesamtzustand des Puzzles ein Knoten ist und die Kanten mögliche Spielzüge. Die Nachbarn wären demnach alle Zustände, die du von einem Zustand in einem Zug erreichen kannst.