4 ms·
> A2 has 4 possibilities (1679) and A3 has 5 possibilities (12679); together that's 20, and if we keep multiplying, we get 4.62838344192 × 1038 possibilities fo
by alttag 15y ago
> A2 has 4 possibilities (1679) and A3 has 5 possibilities (12679); together that's 20, and if we keep multiplying, we get 4.62838344192 × 1038 possibilities for the whole puzzle
I realize this is the start of his search section, and he uses it as a springboard to present constrained search, but this struck me as either incorrect or an intentional straw man.
Applying even the simplest constraint (that a value cannot appear more than once in a cell) means that standard combinatorial formulas don't product accurate counts: by selecting a value, each peer has at least one cell that decrements its count of possible values (otherwise the value would have been detected by the naive algorithm). Applying constraints is the subtext of his eventual point, but I'm not seeing the value in presenting the flawed math the way he did.
The math on this really bugged me (my mind went directly to his eventual solution), and I had to go back and read the introduction to the "Search" section a couple of times to even wrap my head around what he was proposing for the "brute force" solution. Maybe its because I arrived at a solution similar to his eventual one years ago when I tackled a sudoku solver.
The other line that bothered me was: "The second choice is to somehow process much more than one possibility per machine instruction." After reading through, I understand what he means, but it's not equivalent to what he said.
- esrauch 15y agoI don't think it's a disingenuous idea; the a naive search solution is to fill in all of the boxes and then check if its a valid board. In fact, that is the only possible way you could do it if your evaluation function returned either "solved" or "not".