I like it. I wonder if you could calculate how evil a solution would be in that regard, i.e. how likely you are to end up in a canyon. Maybe you could count how many substrings also occur in other valid words or something.
I never dove into the topic any deeper but I suspect that there is probably cryptanalysis literature related to letter string frequency--or just take a dictionary and brute force a substring frequency analysis.