In https://squareword.org (2D variant) I was also running into this problem. It's a bit different though, since I need to find valid 5x5 squares, with 5 words down and 5 across. Surprisingly, there is quite a limited number of such squares.

Ive been able to solve it by slowly injecting more challenging words over time, which has the side effect of also introducing a difficulty gradient. Players seem happy so far :)