Traveling salesman problem variant: which algorithm to choose?
If you have lots of rules then you should be able to come up with lots of heuristics for A*. If I were you I would try A* first, and come up with as many heuristics as I could. You can also use Deep Q learning. I don't think you want to just throw coordinates into a Deep Q network. You want a simpler representation. I would probably give the nodes symbolic identifiers like sparse matrices, integers or sigmoids, and then craft the loss function to reflect the actual cost of moving from node to node and ascribe a high cost to illegal moves.