Working through the night I found a workaround for the algorithm so it generates the puzzles more efficiently.
This reduces the speed for generating hard and expert puzzles significantly, so the user will barely notice the time it takes (took a few seconds for hard, and much more for expert before).
While I was at it, I also made all the puzzles a bit harder.
Hope whoever is into these things enjoys!