Upfront, I'm not a computer science or mathematics graduate. I am a dabbler/recreational programmer and I find some problem/solution scenarios intellectually stimulating to attempt. Sometimes (frequently, actually), this lack of formal training limits my ability to formulate a good solution to a problem. I can pretty much always come up with a brute force solution, but that's never really fulfilling (especially if takes the age of the universe to run)! Better algorithms can almost be seen as things of beauty and help me learn more and equip me to tackle more challenging problems.
So, here's the problem I'm attempting to solve currently but not sure of the best approach. The New York Times’ daily Letter Boxed puzzle requires the player to input words using ONLY the 12 letters given (3 on each side of a square) but with some constraints...
- word length > 2,
- consecutive letters cannot be from the same side of the square,
- whilst the 1st word is constrained only by 1 & 2 above, subsequent words must start with the same last letter of the previous word.
The object is to use all the 12 letters using a number of words <= a number given for the puzzle – it’s “par”. (I’ve only seen this par as 4, 5 or 6 words).
My thinking is along these lines. As candidate words by definition need to have to be made from the 12 letters supplied, they are sub sets. Hence, the minimum set cover problem came to mind. Reducing the number of candidates sets was the second thing that came to mind and I thought it could be done this way...
A. In terms of letter constraints, a list of words can be pre-processed to remove words less than 3 letters long as well as double letters (they would violate constraint 2). This is generic as it works for ALL problems so the word dictionary I used is in this state.
B. Further pre-processing can then be done based on the 12 letters given for the particular puzzle to be solved. For each side of 3 letters, there are 6 letter pair combinations (doubles having already taken care of in A), so 24 such pairs in total that cannot appear in any word (constraint 2 again). All words containing these pairs can also be removed leaving a much smaller list of candidate words.
C. A final stage of pre-processing can be done which ensures that any words that contains a letter NOT in the 12 given is removed.
In using A, B & C I can get a dictionary of 50k words down to less that 1000 candidate words.
Implementing a minimum set cover (an exact cover may not always be available) wouldn’t be too difficult given the resources online. However, where I’m really stuck is understanding how to incorporate constraint 3 into the process.
So, is there a way or have I selected the wrong approach and need to go back to the drawing board?
Edit:
Having thought on this some more, I now think that I can incorporate constraint 3 as a "filter" when selecting from sets as per the greedy algorithm.
What I have experienced in the testing I've done with a particular puzzle is that the word with the biggest cover (i.e. that one that the greedy algorithm would choose first) does not facilitate using another word due to the last letter/first letter constraint. It contained 9 of the 12 letters but ended in a 'y'. No other word could follow that started with 'y' and contained any of the remaining 3 letters required for a solution. So I'm thinking something iterative that starts with the next best candidate if no solution is found using the best candidate.
I am also aware that most solutions published on the website are made up of just 2 words and is also dependent on what words are in the dictionary I use.
