4 ms·
No, you don't need to do it with such a slow algorithm like that. There are only 26 possibilities for a given square. All you need is to track the set of possib
by dataflow 4y ago
No, you don't need to do it with such a slow algorithm like that. There are only 26 possibilities for a given square. All you need is to track the set of possible letters for each square in each direction (52 bits of information—you can even literally fit it into a 64-bit integer). Then for each guess going across, cross it off your list if its corresponding letter isn't in the set of letters going down, and vice-versa. It should be pretty darn quick without any exponential growth.
- asxd 4y agoHow do you select the first guess? e.g. the clue is "popular yellow cartoon bear", and the answer is "pooh". You can satisfy the crossword using random words and a dictionary somewhat easily, but that's not really the task at hand.
- atwood22 4y agoThis solution would work if there were only one valid configuration for your set of possible guesses, but there will be many valid configurations. But you're right, it's not an exponential in the number of possible guesses, rather possibly an exponential in the number of possible guesses that lead to a valid configuration.