Probability question: Estimating the number of attempts needed to exhaustively try all possible placements in a word search.

Question

Would it be reasonable to systematically try all possible placements in a word search?

Grids commonly have dimensions of 15*15 (15 cells wide, 15 cells tall) and contain about 15 words to be placed, each of which can be placed in 8 possible directions. So in general it seems like you can calculate all possible placements by the following: width*height*8_directions_to_place_word*number of words

So for such a grid it seems like we only need to try 15*15*8*15 = 27,000 which doesn't seem that bad at all. I am expecting some huge number so either the grid size and number of words is really small or there is something fishy with my math.

Answer 1

Formally speaking, assuming that x is number of rows and y is number of columns you should sum all the probabilities of every possible direction for every possible word.

Inputs are: x, y, l (average length of a word), n (total words)

so you have

• horizontally a word can start from 0 to x-l and going right or from l to x going left for each row: 2x(x-l)
• same approach is used for vertical words: they can go from 0 to y-l going down or from l to y going up. So it's 2y(y-l)
• for diagonal words you shoul consider all possible start positions x*y and subtract l^2 since a rect of the field can't be used. As before you multiply by 4 since you have got 4 possible directions: 4*(x*y - l^2).

Then you multiply the whole result for the number of words included:

total = n*(2*x*(x-l)+2*y*(y-l)+4*(x*y-l^2)