CODEWITHSUNDEEP
crossword
user3392947
user3392947

Reputation: 21

Crossword generator(swedish crossword) - Java

I'm trying to create a simple Java generator crossword(swedish crossword) - just for fun. I downloaded the vocabulary words from the Internet(about 300,000 words). These words I have save in a HashMap (sorted by word length). The input of the generator is the size of X and Y and a puzzle. Puzzle I inserted randomly into the matrix

But I am not able to figure out a working algorithm to fill the rest of the matrix.

For example:

X X X X
X D O G
X X X X

Does anybody have any advice? Or some useful article on the internet? thank you.

Upvotes: 2

Views: 3606

Answers (1)

Nikos M.
Nikos M.

Reputation: 8345

An algorithm for compiling crosswords (like swedish, scandinavian, etc..) is described here (among others of course :) )

https://stackoverflow.com/a/23435654/3591273

UPDATE: Posting the main steps of the algorithm described in the SO link given (per the comment)

  1. First step of the algorithm is select an empty wordslot (grid word) at random and fill it with a candidate word from its associated wordlist (randomization enables to produce different solutons in consecutive executions of the algorithm) ( complexity O(1) or O(N) )

  2. For each still empty word slots (that have intersections with already filled wordslots), compute a constraint ratio (this can vary, sth simple is the number of available solutions at that step) and sort the empty wordslots by this ratio ( complexity O(NlogN) or O(N) )

  3. Loop through the empty wordslots computed at previous step and for each one try a number of cancdidate solutions (making sure that "arc-consistency is retained", ie grid has a solution after this step if this word is used) and sort them according to maximum availability for next step (ie next step has a maximum possible solutions if this word is used at that time in that place, etc..) ( complexity O(N*MaxCandidatesUsed) )

  4. Fill that word (mark it as filled and go to step 2)

  5. If no word found that satisfies the criteria of step .3 try to backtrack to another candidate solution of some previous step (criteria can vary here) ( complexity O(N) )

  6. If backtrack found, use the alternative and optionally reset any already filled words that might need reset (mark them as unfilled again) ( complexity O(N) )

  7. If no backtrack found, the no solution can be found (at least with this configuration, initial seed etc..)

  8. Else when all wordlots are filled you have one solution

This algorithm does a random consistent walk of the solution tree of the problem. If at some point there is a dead end, it does a backtrack to a previous node and follow another route. Untill either a solution found or number of candidates for the various nodes are exhausted.

The consistency part makes sure that a solution found is indeed a solution and the random part enables to produce different solutions in different executions and also on the average have better performance.

PS was trying to avoid copy-paste back-and-forth between different SO answers, but ok maybe a some summary can be useful

Upvotes: 5

Related Questions