[rhaps0dy]

The easiest thing to do is probably use A* to find the solution, then imitation learning on the NN to learn it. (The immediate feedback gets rid of the vanishing/exploding gradients problem).