|
![](/i/fill.gif) |
Warp wrote:
>> Apparently it's actually a graph colouring problem. Or, equivilently, an
>> exact cover problem. And it's provably NP-complete.
>
> Solving a sudoku is O(1) because the size is fixed to a 9x9 grid.
I presume they were talking about the generalised problem of an n^2 x
n^2 grid...
Even if we assume 9x9, it's interesting to note that in paper the
process is O(1), and yet the amount of time it actually takes me to
solve one appears to be unbounded. I guess this indicates I'm using a
really, *really* inefficient solving algorithm? :-}
(Alternatively, I guess you could take N to mean not the size of the
grid but the number of unknowns...)
Post a reply to this message
|
![](/i/fill.gif) |