Tuesday, January 10, 2006

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.

2 Comments:

Anonymous top affiliate programs said...

How is Everyting in YOUR LIFE... Waste your money and your only out your money,but waste your time and your out part of your life... Michael Leoboeuf

Inflation is when you pay fifteen dollars for the ten dollar hair cut you used to get for five dollars when you had hair... Sam Ewing

If You Find a need to become part of the top affiliate programs so you make a few extra bucks.. go to http://7day2success.com/ ....top affiliate programs...top affiliate programs....

Live a better life today..

5:20 AM  
Blogger Paul Adams said...

This is an excellent blog. Keep it going.You are providing
a great resource on the Internet here!
If you have a moment, please take a look at my wooden baby toys site.
Have a great week!

2:20 AM  

Post a Comment

<< Home