Crossword Puzzles

A trivial backtracking search to generate an N*N crossword puzzle consumes a depressingly rapidly growing running time O(c^(2*N)), where c is the number of N-letter words. On my computer all 3*3-crosswords are found instantly, 4*4-crosswords in a day, and 5*5-crosswords would take longer than sun shines.

The key to make crossword puzzle generation efficient is in to check immediately when laying a new letter of a word in a puzzle that the crossing direction is not impossible to satisfy. For example, if I place the word "take" immediately above "time" at the top of the puzzle, it will be impossible to find crossing words which begin with letters "tt" or "km" later in the search. This prunes the search space increasingly efficiently as N grows, because while some 31% of all digraphs occur in some word, only 8% of all trigraps and less than 1% of all 4-graphs occur in some word. Furthermore not all combinations occur in any place, for example both digraphs "tt" and "km" do occur in some words, but neither can begin a valid word.

I also wrote hints of varying difficulty to a number of the words. To tease you, here's an easy 3*3-puzzle:

  impregnate color -----+
  celestial rotation -+ !
  beer -------------+ ! !
                    ! ! !
                    V V V
  increase      ->
  put down      ->
  visual organ  ->

And a very hard one:

  protective clothing -+
  anecdotes ---------+ !
  metal bar -------+ ! !
                   ! ! !
                   V V V
  chatter      ->
  cuckoo       ->
  small amount ->

There are numerous puzzles when N is 3, 4 and even 5, but my program found only two 6*6 crossword puzzles when using an old /usr/dict/words without names of places and people:

a c c u s e
p r o p e l
h a n d e d
i n v a d e
d i e t e r
s a y e r s

The second 6*6-crossword is of course the transpose of the above one.