At http://www.imada.ou.dk/~sik/index.html you will find a thesis
on crossword puzzle generation.