Crosswords are pretty tough, partially because many puzzles (such as the Tuesday, Thursday, and Sunday puzzles in the New York Times) have enough wordplay in their answers (not just the clues) that they break normal crossword rules, in a specific way that the solver has to determine. I think Dr. Fill (https://arxiv.org/abs/1401.4597) is still the state of the art.