Let me know if you find some reasonably fast sub-optimal algorithm, I'd be interested in trying it.

There seems to be some literature on the complexity this kind of sliding puzzles, like https://www.sciencedirect.com/science/article/abs/pii/S03043....