https://davidkoloski.me/blog/intelligent-brute-forcing/ might help, if you don't already have some sort of automatic solver to figure out solutions.
I did realize while reading this that I could get a little more sophisticated by finding out the number of moves in a best solution using an aggressively optimized fast solver. If that number is within a range that's fun to play, say 8-11 moves, then go ahead and find all the rest of the solutions with the maximum brute force. If not, then just scrub the whole thing since I wouldn't use that puzzle anyway.
This kind of problem is known as planning in old AI, and it's languishing. most techniques are just variations of A*, with things like symmetry detection and heuristics tailored to game benchmark problems. It's the kind of thing (IMO) that deep RL fails at, since unlike Chess or Go where your solution-finding simply needs to beat a competitor, here your solution needs to be exactly correct (and ideally minimal.) It's very sparse.