3 ms·
> In your contrived example, you only know the right answer after considering all four possible combinations. This is basically correct. > That is a combinato
by thaumasiotes 4y ago
> 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.
- foota 4y agoThe 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.