Crossword Puzzle Generation Algorithm

[NotASmurf]

Hey all, for a dictionary app I have to code I have to implement as crossword game as a side feature, unfortunately this is compulsory, I can't figure out a good way of finding words that intersect each other (esp words that intersect multiple others) without a hell of a lot of goto and while's. Is there a good, inexpensive strategy (so no genetic algorithms or pure bruteforce) given a list of words, to find good intersections to procedural generate the crossword without while loops that may not even be guaranteed to resolve themselves? Any help appreciated.

 

[Svein]

Searching the dictionary word list using regular expressions? (https://en.wikipedia.org/wiki/Regular_expression)

 

[NotASmurf]

Thanks but that's just abstracting the loop, I'm certain the key lies in pre-processing the data.

 

[Svein]

You could, of course, put all the words in a database:

• Word
  
• Dictionary entry
  
• Word length
• First letter
• (Second letter etc.)

Now you have pre-processed the data. In order to find the word you want, create a query incorporating the word length and known letters...

 

[DrZoidberg]

Why gotos? What language are you using?
I don't see a really efficient way of doing this. I would just use simple recursive backtracking algorithm.
https://en.wikipedia.org/wiki/Backtracking

 

[PeroK]

Hey all, for a dictionary app I have to code I have to implement as crossword game as a side feature, unfortunately this is compulsory, I can't figure out a good way of finding words that intersect each other (esp words that intersect multiple others) without a hell of a lot of goto and while's. Is there a good, inexpensive strategy (so no genetic algorithms or pure bruteforce) given a list of words, to find good intersections to procedural generate the crossword without while loops that may not even be guaranteed to resolve themselves? Any help appreciated.

Transform code to produce a crossword (7 letters).

Spoiler

compile