Stone Maze Chess solver

Question

Background:

Every war eventually comes to an end, but the end is never absolute. The Stone Maze Chess scenario takes place after a game of chess is finished. The enemy King is dead and the pieces is lost in vacuity almost out of faith, multiplying. The winning side has moved on except for the Hero who is left behind with one mission still to go.

Objective:

Your mission is to guide your hero to put a stone on the enemy Kings grave to prevent the ghost of the King from haunting the land in eternity.

Visualization:

Board size and positions are notated just like a normal chess table, lines from A to H and ranks from 1 to 8. Visualized almost empty table:

    A B C D E F G H

8   . . . H . . . .  8
7   . . . o . . . .  7
6   . . . . . . . .  6
5   . . . . . . . .  5
4   . . . . . . . .  4
3   . . . . . . . .  3
2   . . . . . . . .  2
1   . . . X . . . .  1

    A B C D E F G H

Movement:

You move your Hero(H) one square every move: North(N), South(S), East(E) or West(W). You can push the Stone(o) in front of the Hero(H) if the path is free from board edges, stonewalls and chess pieces. If you move your Hero(H) into the reach of any enemy piece, it will immediately take the first chance to kill the hero, and the game is over. That, for example, means that you cannot move the hero adjacent to an enemy Queen() or Rook(R) unless there is a wall between the Hero(H) and the piece.

The kings grave(X) and any Trap(T) cannot be crossed by the Hero(H) or any piece except for the Knight(K) who can leap over it.

Push & pull:

All of the chess pieces can also be pushed one square just like the Stone(o), leaving a stonewall behind. Pieces, unlike the Stone(o), is also pulled if the Hero moves away from the piece.

Piece movement:

On top of that, if your Hero(H) stands adjacent (orthogonal [not diagonally]) to a chess piece the chess piece can be moved like a chess piece in standard chess. This applies only to Pawns(P), Knights(K) and Bishops(B) because your Hero(H) can't stand adjacent to a Rook(R) or a Queen(Q) without being attacked by the piece, unless there is a stonewall between. Pawns(P) can only move forward (north), but can be pushed or pulled in any of the four directions. Pawns(P) on the 2nd rank can move either 1 or 2 steps forward on the same move if the path is free. The other pieces can also move like they do in chess, but cannot move through any stonewall, except for the knight who can leap over stonewalls, traps(T), the Hero(H), the Stone(o) and other pieces. Bishops(B) and Queens(Q) can diagonally tangent a stonewall, but cannot cross two connected stonewalls, when moved or attacking the Hero(H).

Pawns(P) attack diagonally in the same way, only connected stonewalls prevent the attack. A single loose stonewall can't prevent a Pawn(P) from attacking diagonally.

Edit: This hopefully explains how diagonal movement works, X's represents possible destination positions for the Bishop(B):

    A B C D E F G H     A B C D E F G H

8   .|_|. . . _ . .  8  X . . . . . . .
7   . _ . . . .|. .  7  . X . . . X . .
6   . _|. . . . . .  6  . . X . X . . .
5   . . . B _ . . .  5  . . . B . . . .
4   . .|. . _ . _ .  4  . . X . X . . .
3   .|. . . _ _ _ .  3  . X . . . X . .
2   .|. . . . . . .  2  . . . . . . . .
1   . . . . . . . .  1  . . . . . . . .

    A B C D E F G H     A B C D E F G H

/Edit

Stonewalls:

From the start the board is free from stonewalls. Chess pieces without their King stands still so long that they turn into stone, so when pushed or pulled they will leave a line of stones between the square they come from and the square they are pushed or pulled onto, preventing everything except Knights(K) to pass through it. The stonewalls gradually creates a maze. If all sides of a square is filled with stonewalls, that square is again released from all surrounding stonewalls, the square is reset. The four corner squares is reset when both edges facing the board get stonewalls, edge squares is reset when all three sides has stonewalls. Free squares that is surrounded by other squares has four sides and is reset when all four sides is filled with stonewalls.

Trap:

If a piece is pushed or moved to a trap, it dies and is removed from the table. Pieces cannot cross over a trap, except for Knights(K). If the Hero(H) moves to a trap, it is game over.

Game state (input to your program):

Input is always 8 lines of 16 characters, each 2 bytes (one state and one blankspace) is representing one square on the board.

Valid input characters and their purpose:

. = Empty square
H = Hero start position.
X = The kings grave.
o = The stone.
T = A trap.
P = Pawn.
K = Knight.
B = Bishop.
R = Rook.
Q = Queen.

Example input:

. . . H . . . . 
. . . o . . . . 
. P . . . P . . 
. P . K . P . . 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
. . . X . . . . 

In addition to the Hero(H), the Stone(o) and the Kings grave(X) we here have four Pawns(P) and one Knight(K) on the board setup.

How to solve the example puzzle: Here is a solution where we push two pieces creating only two single vertical stonewalls on the board. Not exactly a Maze, but will serve as an example.

1. Push the stone one step south.
2. Go around with the Hero far east, south to rank 2, west and up on line D adjacent to the knight at D5.
3. Move the knight to B4.
4. Move the knight to A6.
5. Push the pawn at F5 one step east, and then move it one step north (this way we avoid end up adjacent to it and pull it south again).
6. Move the pawn at F6 one step north.
7. Move the Hero north and around the stone on east side.
8. Push the stone south until the kings grave. Successful solution.

The above solution is intentionally a bit unneccessary complex, just to demonstrate how stonewalls appear. Stonewalls can appear horizontally also if pieces is pushed or pulled north or south.

Here is visualizations of some states of the example game solution:

1.  . . . H . . . .
    . . . o . . . .
    . P . . . P . .
    . P . K . P . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . X . . . .

2.  . . . . . . . .
    . . . . . . . .
    . P . o . P . .
    . P . K . P . .
    . . . H . . . .
    . . . . . . . .
    . . . . . . . .
    . . . X . . . .

7.  . . . . . . . .
    . . . . H P . .
    K P . o . . P .
    . P . . . .|. .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . X . . . .

8.  . . . . . . . .
    . . . H P|. . .
    K P . o . . P .
    . P . . . .|. .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . X . . . .

Control notation (output from your program):

Move the Hero(H) using 4 commands:

+N = Move 1 step north 
+S = Move 1 step south  
+E = Move 1 step east 
+W = Move 1 step west  

If you move the Hero(H) 1 step east and the Stone(o) or a chess piece is adjacent to the east then your Hero(H) will push the Stone(o) or the piece 1 step east in front of the Hero(H). This is only possible if the square behind in the pushing direction is a free square and no stonewall in the path. Same for all four directions.

If you move 1 step east and there is a piece adjacent behind to the west without a stonewall between, the Hero will pull that piece one step east and create a stonewall behind it. The same in all four directions.

If your Hero(H) stands adjacent to any chess piece you may also move the piece if it is able to move, notation is newline + source position + destination position, examples:

E2E3    = Moves a *Pawn*(P) from square E2 to E3. The *Hero*(H) cannot stand at square E3 before this move.
D8G5    = Moves a *Bishop*(B) from square D8 to G5.

The output should be one solution to the input. There may be several different solutions to the same input, your program only needs to provide one solution for one input.

In practise:

If feeding your program with this input (the above example):

. . . H . . . .
. . . o . . . .
. P . . . P . .
. P . K . P . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . X . . . .

Then this is one valid output:

+S+N+E+E+E+E+S+S+S+S+S+S+W+W+W+W+N+N+N
D5B4+W+W
B4A6+E+E+E+N+E+S+E
G5G6+W+N
F6F7+W+N+N+W+S+S+S+S+S

Your program should - using a standard computer with normal proccessing power - be able to provide a solution within 30 minutes of calculations.

Test cases:

4 Example inputs your program should be able to solve (among other ones, don't try hardcoding their solutions):

. . . H . . . .
. . . o . . . .
. P . . . P . .
. P . K . P . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . X . . . .

. . . H . . . .
. . . o . . . .
. . . . . . . .
. P . . . P . .
. . P T P . . .
. . . . P . . .
. . . . . . . .
. . . X . . . .

. . . . . . . .
Q . . . . . . .
. . . . . . . .
P P . . K T K .
. . . . . . . .
. . . P . . . .
. o . . . . . .
. H . . P . X .

. . . H . . . .
. . . o . . . .
R . . . . . . .
P P P P P . . .
. . . . . . . .
. . . . . . . .
. . . P P P P P
. . . . . . . X

This is code-golf, shortest solution in bytes of sourcecode wins!