In my experience, the only way to make meaningful progress on performance from here on out is to:

- Squeeze out more entropy (for example, rotating states for symmetric boards)

- Make the heuristic function smarter (for example, by calculating the assignment bottleneck)

I wrote a Carcassonne solver once and found many little optimization opportunities by detecting fail states early for example. Avoiding dead ends saves a massive amount of time.