A challenging Puzzle – fitting words in a grid

\scrabble wordsYou are given a list of words. You have to fit them into a grid so that the grid is as small as possible. The words can go horizontal or vertical and can use letters from other words (like in Scrabble). But you can’t have words next to each other except where they share letters like in the picture above. MN BTW is not a valid Scrabble word so this is wrong! (I er borrowed it from somewhere!)

So words can be placed anywhere, in either orientation. Evaluating all the possibilities could probably be done by brute force. But for each word in each position on the board there are n-1 words to be fitted afterwards. Do you try and fit in each alternate word in a different orientation like horizontal thenĀ  vertical then horizontal?

If there are ten words to fit in say in a starting grid of 20 x 20 and the first word is 6 characters long then it can fit in 15 different places along the top line and on each of the 20 lines so that’s 300 positions. Then if its vertical there another 300 positions. That’s 600 positions to try. And for each of those 600 there’s 9! different combinations of words to fit in. 9! = 362,880.

Of course if the first word and the second word have no letters in common then it may be as well to skip that 2nd word and go onto the 3rd and so on. We want to keep the grid from getting too large with unconnected words. Also We might limit the first word to start in th 6 positions in the top row and maybe only the first and 2nd rows. That vastly reduces the number of combinations to try out. But still it’s a tough thing to program.

C isn’t usually the best language to program anything with text in, but in this case, we’re not building sentences or searching, just looking at arrays of characters and so it might just be suitable.

I’m going to have a go at this and see if it can be done and if so I’ll publish my code but this may take a few days. If so then it could be used as a basis of a word search generator though the rules about words being next to each other could be relaxed plus words run forwards and backwards in both horizontal and vertical orientation and also diagonal.

Previous Puzzle Answer

This was “If I have the integers 4,5,6,7 and 8 and a special C function f so that f(4)=2, f(5) = 5, f(6)=10, f(7)=40 and f(8) = 92. What is the function f?”.Bit of a trick question this as the function is returning the number of unique Queens that could be fitted on a chess board of size n (4×4,5×5..8×8) without being able to attack each other.

Philip Jama has posted a C program on GitHub to arrange the number of Queens on a chessboard of the specified size. So the function wasn’t really a function…