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