Helping with crossword filling algorithm

Question

Such problem was given me at my university, maybe someone will have interesting algorithm how to solve the problem. There're several solutions for it on stackoverflow, but none of them is ok (because they're looping for all possibilities).

Problem: Find all possible combinations for allocating given words into given table, grid ( rectangular, see input below ). There should be no free cells and word can be located from left to right or up to down. Words can't be located word after word in a row (column).

Input: rectangular area, example:

+-----+
|  *  | 
|     |
+-----+

or

+-----+
|   * |
|     |
|    *|
|   * |
+-----+

Then after that different words are typed ( next input data ) to fill that grid such as:

cdi
zobxzst
tdxic
r
sc
zro
and etc ...

Number is initially unknown but inputs until end of stdin - active EOF.

Output: if one solution exists then output that possible solution within filled grid. If no solution or number of solutions then output 0 or that exact number.

Example:

(table inputted)

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

Then words cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

(Each as input, but here separated by spaces.)

Output ( 1 solution only ):

+-----+
|zro*h|
|ogish|
|bfkh*|
|xvf*r|
|za*c*|
|sc*df|
|tdxic|
+-----+

Important note: The inputted grid is limited by 16 (!) cells only, number of words is less than 60. I wrote an algorithm which search through all possible combinations but it didn't work for me as execution time is limited (by 10 sec I guess) and this problem couldn't be solved with rough algorithm ( e.g. 15 on 15 grid and about 60! possible or more possible permutations which can be processed about 1 day? on ordinary 2GHz PC ).

Maybe there exists another unique solution. Maybe this problem is more mathematic then programming, maybe possible to use some left-right combos compared with up-down? or maybe weighted cells?

P.S. I have 3 weeks to solve that problem, if not, I can post solution here after 3 weeks ( good news ) ;)

Answer 1

There're several solutions for it on stackoverflow, but none of them is ok (because they're looping for all possibilities).

My idea is probably wrong as well then: but here's an idea off the top of my head.

I wrote an algorithm which search through all possible combinations

If there are too many, then the problem is probably that you are also searching/looping through impossible combinations as well as possible combination.

For example when you place a word like "zro" in the top-left corner, there are very few "possible" combinations which can be placed in the vertical words below it:

1. the first vertical word must begin with 'z'
2. the second vertical word must begin with 'r'
3. the third vertical word must begin with 'o'
4. The combinations of letters on the second row (resulting from placing the vertical words) must itself be a valid word
5. etc.

Therefore:

1. Pick any word and place it in the top-left corner
2. Find existing words which satisfy the constraints above
3. If you find one or more such words, then continue in this way to see whether you can solve the whole thing; or if you fail, then try again using a different initial word

Summary:

• Don't generate every complete grid, and then test it to see whether it satisfies all constraints
• Instead use the constraints as you build the grid, to reduce the number of possibilities that you test

---

I'm suggesting that you solve the grid, starting from an initial word.

Instead of testing each words in the top-left corner, a better (e.g. because it moe quickly eliminates impossibilities) way to generate the starting position[s] is:

• Find the longest word (e.g. rgfvacd)
• Find all possible combinations of words which cross/join it
• Try to place each of those valid combinations on the grid

Answer 2

I suggest that you first should see what lengths of words you have to fill, in your example:

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

you have two 7 letter words, three 1 letter word, etc.

you should sort this list according to the count and first try with the wrod lengths with the lowest count, in the next iteration you should make a list of what word you need to find for example - three 4 letter words that start with 'a' - you should count how many of these words you have left in your word list, and then choose the one with the least words in it - if it's 0 then return.

hope it makes sense.