1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:

{
  /*
    0x88 board
    https://en.wikipedia.org/wiki/Board_representation_(chess)#0x88_method
    s: Start
    f: Finish
    Die rechte Hälfte dieses 16x8 Boards dient zur Kontrolle, ob ein Zug das Spielfeld verlässt.
  */
  const level = `
    x . . . x . . . . . . . . . . .
    . . . . . . . . . . . . . . . .
    . . x . x . . . . . . . . . . .
    . . . s . . x . . . . . . . . .
    . x . . f . . . . . . . . . . .
    . . . x . . . . . . . . . . . .
    . . . . . . . . . . . . . . . .
    x . x . x . . . . . . . . . . .
  `.trim().split(/\s*/g);

  const moves = [
    [ 1,  0],
    [ 0,  1],
    [-1,  0],
    [ 0, -1],
  ].map( ([x,y]) => x + 16 * y );

  const steps = [1, 3, 5];

  console.log( breadthFirstSearch(level, moves, steps, 1000) );
}

function decodeFieldIndex (i) {
  const x = i & 0b00000111;       // last 3 bits
  const y = i >> 4 & 0b00000111;  // last 7th to 5th bit
  return "abcdefgh"[x] + (y+1);
}

function breadthFirstSearch (level, moves, steps, depthLimit) {
  let depth = 0;
  let positions = [{
    index: level.indexOf("s"),
    history: [],
  }];

  while (depth < depthLimit) {
    const phase = depth % 3;
    const newPositions = [];

    for (const move of moves) {
      for (let {index, history} of positions) {

        let blocked = false;
        for (let step = 0; step < steps[phase]; step++) {
          index += move;
          if ((index & 0x88) || level[index] === "x") {
            blocked = true;
            break;
          }
        }
        if (blocked) continue;

        history = [...history, index];

        if (level[index] === "f") {
          /*
            solution found
          */
          return history
            .map(decodeFieldIndex)
            .join(" ");
        }

        newPositions.push({
          index,
          history,
        });
      }
    }

    positions = newPositions;
    depth++;
  }
  return "failed";
}					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:

{
  /*
    0x88 board
    https://en.wikipedia.org/wiki/Board_representation_(chess)#0x88_method
    s: Start
    f: Finish
    Die rechte Hälfte dieses 16x8 Boards dient zur Kontrolle, ob ein Zug das Spielfeld verlässt.
  */
  const level = `
    x . . . x . . . . . . . . . . .
    . . . . . . . . . . . . . . . .
    . . x . x . . . . . . . . . . .
    . . . s . . x . . . . . . . . .
    . x . . f . . . . . . . . . . .
    . . . x . . . . . . . . . . . .
    . . . . . . . . . . . . . . . .
    x . x . x . . . . . . . . . . .
  `.trim().split(/\s*/g);

  const moves = [
    [ 1,  0],
    [ 0,  1],
    [-1,  0],
    [ 0, -1],
  ].map( ([x,y]) => x + 16 * y );

  const steps = [1, 3, 5];

  (async () => {
    for await (const line of breadthFirstSearch(level, moves, steps, 1000)) {
      console.log(line);
    }
  })();
}

function decodeFieldIndex (i) {
  const x = i & 0b00000111;       // last 3 bits
  const y = i >> 4 & 0b00000111;  // last 7th to 5th bit
  return "abcdefgh"[x] + (y+1);
}

async function* breadthFirstSearch (level, moves, steps, depthLimit) {
  let depth = 0;
  let positions = [{
    index: level.indexOf("s"),
    history: [],
  }];
  const visited = Array(level.length)
    .fill()
    .map( () => [false, false, false] );

  while (positions.length && depth < depthLimit) {
    const phase = depth % 3;
    yield `depth: ${depth}, nodes: ${positions.length}`;
    const newPositions = [];

    for (const move of moves) {
      for (let {index, history} of positions) {

        let blocked = false;
        for (let step = 0; step < steps[phase]; step++) {
          index += move;
          if ((index & 0x88) || level[index] === "x") {
            blocked = true;
            break;
          }
        }
        if (blocked || visited[index][phase]) continue;
        visited[index][phase] = true;

        history = [...history, index];

        if (level[index] === "f") {
          /*
            solution found
          */
          yield history
            .map(decodeFieldIndex)
            .join(" ");

          continue;
        }

        newPositions.push({
          index,
          history,
        });
      }
    }

    positions = newPositions;
    depth++;
  }
  yield "done";
}					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

depth: 0, nodes: 1
depth: 1, nodes: 4
depth: 2, nodes: 6
depth: 3, nodes: 2
depth: 4, nodes: 6
depth: 5, nodes: 8
depth: 6, nodes: 4
depth: 7, nodes: 9
depth: 8, nodes: 5
depth: 9, nodes: 3
depth: 10, nodes: 7
depth: 11, nodes: 5
depth: 12, nodes: 2
depth: 13, nodes: 6
depth: 14, nodes: 3
depth: 15, nodes: 3
depth: 16, nodes: 3
depth: 17, nodes: 3
depth: 18, nodes: 3
depth: 19, nodes: 3
depth: 20, nodes: 2
depth: 21, nodes: 1
depth: 22, nodes: 4
depth: 23, nodes: 3
depth: 24, nodes: 1
depth: 25, nodes: 1
depth: 26, nodes: 2
depth: 27, nodes: 2
depth: 28, nodes: 3
depth: 29, nodes: 3
depth: 30, nodes: 2
depth: 31, nodes: 2

c4 f4 a4 a5 a2 f2 e2 h2 c2 d2 g2 b2 c2 f2 f7 e7 h7 c7 d7 g7 b7 a7 a4 f4 f5 c5 h5 h4 h1 h6 h5 e5

depth: 32, nodes: 1
depth: 33, nodes: 1

done					

1:
2:
3:
4:
5:
6:

Found: lrldurllrllrdduddlurldurllrrdlurldurlrlrrlrrdlrlrrllurdlruudul
Found: lrldurllrllrdduddlurldurlrlrlrlrlrrlrrdlrlrrllurdlruudul
Found: lrldurllrllrdduddlurldurlrlrrlrrdlrlrrllurdlruudul
Found: lrldurllrrdlurldurlrlrrlrrdlrlrrllurdlruudul
Found: lrldurlrlrlrlrlrrlrrdlrlrrllurdlruudul
Found: lrldurlrlrrlrrdlrlrrllurdlruudul					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:

<?php

$f = array(
    array("#"," "," "," ","#"," "," "," "),
    array(" "," "," "," "," "," "," "," "),
    array(" "," ","#"," ","#"," "," "," "),
    array(" "," "," "," "," "," ","#"," "),
    array(" ","#"," "," "," "," "," "," "),
    array(" "," "," ","#"," "," "," "," "),
    array(" "," "," "," "," "," "," "," "),
    array("#"," ","#"," ","#"," "," "," ")
    );

function show($p) {
    static $ps = "";
    if(!strlen($ps)) {
        $ps = str_repeat("#", 256);
    }
    if(strlen($p) < strlen($ps)) {
        $ps = $p;
        echo "Found: $p\n";
    }
}

function check($f, $a1, $b1, $a2, $b2) {
    $ca1 = min($a1, $a2);
    $cb1 = min($b1, $b2);

    $ca2 = max($a1, $a2);
    $cb2 = max($b1, $b2);

    if($ca1 < 0 || $cb1 < 0) {
        return false;
    }

    if($ca2 > 7 || $cb2 > 7) {
        return false;
    }

    for($ca = $ca1; $ca <= $ca2; $ca++) {
        for($cb = $cb1; $cb <= $cb2; $cb++) {
            if($f[$ca][$cb] == "#") {
                return false;
            }
        }
    }

    return true;
}

function jump($f, $a, $b, $p) {
    if(strlen($p) > 64) {
        return;
    }

    if($a == 4 && $b == 4) {
        show($p);
        return;
    }

    $r = strlen($p) % 3;
    $d = 1 + 2 * $r;

    $al = $a;
    $bl = $b - $d;

    $ar = $a;
    $br = $b + $d;

    $au = $a - $d;
    $bu = $b;

    $ad = $a + $d;
    $bd = $b;

    if(check($f, $a, $b, $al, $bl)) {
        jump($f, $al, $bl, $p . "l");
    }

    if(check($f, $a, $b, $ar, $br)) {
        jump($f, $ar, $br, $p . "r");
    }

    if(check($f, $a, $b, $au, $bu)) {
        jump($f, $au, $bu, $p . "u");
    }

    if(check($f, $a, $b, $ad, $bd)) {
        jump($f, $ad, $bd, $p . "d");
    }
}

jump($f, 3, 3, "");					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:

  TDirection = (dirUp, dirRight, dirDown, dirLeft);
  TFieldVisited = Array [1..8, 1..8, 1..5] of Boolean;

var
  Form1: TForm1;

  Steps: Array [0..2] of Integer = (1,3,5);
  Spielfeld: Array [1..8, 1..8] of Integer =
  ( (0,1,1,1,0,1,1,1),
    (1,1,1,1,1,1,1,1),
    (1,1,0,1,0,1,1,1),
    (1,1,1,1,1,1,0,1),
    (1,0,1,1,1,1,1,1),
    (1,1,1,0,1,1,1,1),
    (1,1,1,1,1,1,1,1),
    (0,1,0,1,0,1,1,1)
  );

  FieldVisited: TFieldVisited;
  MoveList: TStringList;
  curX, curY, curStep: Integer;

implementation

{$R *.dfm}

procedure OutPutPath;
var i: Integer;
begin
    for i := 0 to MoveList.Count-1 do
      Form1.Memo1.Lines.Add(Movelist[i]);
    Form1.Memo1.Lines.Add('-------');
end;

function FreeLineUp(Stepwidth: Integer): Boolean;
var i: Integer;
begin
    result := True;
    for i := 1 to Stepwidth do
        result := result AND (Spielfeld[curY-i, curX] = 1);
end;

function FreeLineDown(Stepwidth: Integer): Boolean;
var i: Integer;
begin
    result := True;
    for i := 1 to Stepwidth do
        result := result AND (Spielfeld[curY+i, curX] = 1);
end;

function FreeLineLeft(Stepwidth: Integer): Boolean;
var i: Integer;
begin
    result := True;
    for i := 1 to Stepwidth do
        result := result AND (Spielfeld[curY, curX-i] = 1);
end;

function FreeLineRight(Stepwidth: Integer): Boolean;
var i: Integer;
begin
    result := True;
    for i := 1 to Stepwidth do
        result := result AND (Spielfeld[curY, curX+i] = 1);
end;


function MovePossible(aDir: TDirection): Boolean;
var currentWidth: Integer;
begin
    currentWidth := Steps[curStep mod 3];
    case aDir of
      dirUp    : result := (curY - currentWidth >= 1) and FreeLineUp(currentWidth);
      dirRight : result := (curX + currentWidth <= 8) and FreeLineRight(currentWidth);
      dirDown  : result := (curY + currentWidth <= 8) and FreeLineDown(currentWidth);
      dirLeft  : result := (curX - currentWidth >= 1) and FreeLineLeft(currentWidth);
    end;
end;

procedure DoMove(aDir: TDirection);
var currentWidth: Integer;
begin
    currentWidth := Steps[curStep mod 3];
    case aDir of
      dirUp    : begin
          curY := curY - currentWidth;
          MoveList.Add('Hoch');
      end;
      dirRight : begin
          curX := curX + currentWidth;
          MoveList.Add('Rechts');
      end;
      dirDown  : begin
          curY := curY + currentWidth;
          MoveList.Add('Runter');
      end;
      dirLeft  : begin
          curX := curX - currentWidth;
          MoveList.Add('Links');
      end;
    end;
    inc(curStep);
end;

procedure UndoMove(aDir: TDirection);
var currentWidth: Integer;
begin
    dec(curStep);
    currentWidth := Steps[curStep mod 3];
    case aDir of
      dirUp    : curY := curY + currentWidth;
      dirRight : curX := curX - currentWidth;
      dirDown  : curY := curY - currentWidth;
      dirLeft  : curX := curX + currentWidth;
    end;
    MoveList.Delete(MoveList.Count - 1);
end;


procedure GoOnWalking;
var aDir: TDirection;
    currentWidth: Integer;
begin
    currentWidth := Steps[curStep mod 3];
    // check for circle
    if FieldVisited[curX, curY, currentWidth] then
        exit;

    // check for destination
    if (curX = 5) and (curY = 5) then
        OutPutpath;

    FieldVisited[curX, curY, currentWidth] := True;
    for aDir := Low(TDirection) to High(TDirection) do
    begin
        if MovePossible(aDir) then
        begin
            DoMove(aDir);
            GoOnWalking;
            UnDoMove(aDir);
        end;
    end;
    FieldVisited[curX, curY, currentWidth] := False;
end;


procedure TForm1.Button1Click(Sender: TObject);
var x,y, s: Integer;
begin
    curStep := 0;
    curX := 4;
    curY := 4;
    Memo1.Clear;

    for x := 1 to 8 do
      for y := 1 to 8 do
        for s := 1 to 5 do
            FieldVisited[x,y,s] := False;

    MoveList := TStringList.Create;
    try
      GoOnWalking;
    finally
      MoveList.Free;
    end;
end;