Hacker News Reader

Comment by dataflow | Hacker News Reader

If your guesses for 1-across are AAA and BBB, and your guesses for 1-down are ABC and DEF, and they share their first letters in common, then you necessarily have to prune DEF and BBB. I don't think there's a combinatorial explosion anywhere here right?

View on HN

In your contrived example, you only know the right answer after considering all four possible combinations. That is a combinatorial explosion when there are only two choices to make.

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.

How 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.

This 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.

> In your contrived example, you only know the right answer after considering all four possible combinations.

This is basically correct.

> That is a combinatorial explosion when there are only two choices to make.

But this isn't; you're being misled by the fact that 2×2 is equal to 2+2. The described algorithm is doing rows + columns amount of work, not rows × columns. If you had 14 guesses across and 3 guesses down, you'd know which ones to prune (according to this algorithm) after looking at 17 things. This is not a combinatorial explosion.

The issue is going to be in whittling down conflicts, there can be many clues which have at least one valid cross for each cross. If there are even a modest number of rows/columns (say, N) each with a modest number of solutions (say, M), your performance for checking is going to be very poor. You'll have to backtrack through the solution space I believe trying different possibilities, which should be m^n. For example for n=20 and m=3 you'll have 3^20, which is 3,486,784,401. Certainly not the worst, but this is quite sensitive to the numbers. If you have say 5 solutions on average you're instead looking at 9 * 10^13.

Reply on news.ycombinator.com