I wonder if machine learning could be used to model the probability distributions at a greater capacity, and thus reduce backtracking.
One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.