Help with crossword puzzle filling algorithm

Question

Such a problem was given to me at my university, maybe someone will have an interesting algorithm on how to solve the problem. There are several solutions for this in stackoverflow, but none of them are suitable (because they are cyclically suitable for all possibilities).

Task: find all possible combinations for highlighting the given words in the given table, grid (rectangle, see below). There should not be free cells, and the word can be located from left to right or down. Words cannot be found by words after a word in a row (column).

Input: rectangular area, example:

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

or

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

Then after that, different words are typed (the following input data) to fill this grid, for example:

 cdi zobxzst tdxic r sc zro and etc ... 

The number is initially unknown, but is entered until the end of stdin - active EOF.

Output: if there is one solution, output this possible solution inside the filled grid. If no solution or number of solutions prints 0 or this is an exact number.

Example:

(entered table)

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

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

(Each entry, but here is separated by spaces.)

Output (only 1 solution):

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

Important note: the entered grid is limited to only 16 (!) Cells, the number of words is less than 60. I wrote an algorithm that looked through all possible combinations, but this did not work for me, because the execution time is limited (by 10 seconds, I think), and this the problem cannot be solved using a crude algorithm (for example, 15 on 15 grids and about 60 possible or more possible permutations that can be processed for about 1 day on a regular PC with a frequency of 2 GHz).

Perhaps there is another unique solution. Maybe this problem is more mathematical than programming, maybe you can use some left-right combinations in comparison with the upstream one? or perhaps suspended cells?

PS I have 3 weeks to solve this problem, if not, I can send the solution here after 3 weeks (good news);)

Answer 1

There are several solutions for it in stackoverflow, but none of them are suitable (because they are fixated on all the possibilities).

My idea is probably also wrong, but here is an idea from my head.

I wrote an algorithm that looks through all possible combinations

If there are too many of them, then the problem is probably that you are also doing a search / loop through impossible combinations, as well as a possible combination.

For example, when you put the word "zro" in the upper left corner, there are very few "possible" combinations that can be placed under the vertical words below:

• first vertical word should start with 'z'
• the second vertical word should begin with 'r'
• the third vertical word should begin with 'o'
• The combination of letters in the second line (as a result of placing vertical words) must be a true word
• and etc.

In this way:

• Select any word and place it in the upper left corner.
• Find existing words that satisfy the restrictions above
• If you find one or more of these words, continue in this way to see if you can solve all this; or if you fail, try again using a different starting word

Summary:

• Do not create every complete grid, and then check it to make sure that it meets all the restrictions.
• Instead, use grid constraints to reduce the number of features you are testing.

---

I suggest you solve the grid, starting with the initial word.

Instead of checking every word in the upper left corner, a better way (for example, because it quickly eliminates the impossibility) is a way to generate the initial position [s]:

• Find the longest word (e.g. rgfvacd )
• Find all possible combinations of words that cross / join it
• Try placing each of these valid combinations in a grid.

Answer 2

I suggest you first see how many words you should fill out in your example:

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

you have two 7-letter words, three one-word words, etc.

you should sort this list according to the calculation and first try with the wrod lengths with the lowest score, in the next iteration you should make a list of what you need to find, for example, three 4-letter words that begin with "a" - you must calculate how many of these words you left in the list of words, and then select the one that has the smallest words - if it returns 0, return.

hope this makes sense.