It all seems to hinge on the random placement of the first few words. After that, it jams them in wherever it can. But those first few make all the difference.

A challenging crossword algorithm would be one that randomly places a word, then the necessary dead spaces, then replicates the dead space according to some rule of symmetry, ultimately resulting in an "attractive" layout.