Invisible <voi### [at] devnull> wrote:
> 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...

  Has it been proven that it's possible to create unambiguous sudoku
problems for all possible values of n?

  (A sudoku problem only makes sense if it's unambiguous, iow. it can be
solved unambiguously without trial-and-error, only by pure deduction.)

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

  It cannot be unbounded because the number of possible permutations is
fixed.

  Inside a 3x3 square, where all the numbers between 1 and 9 are put, the
number of possible permutations of those numbers is 9! = 362880. Since
there are 9 such squares, the total number of combined permutations is
9^362880. Sure, this is a huge number, but it's a fixed upper bound and
makes the solver O(1).

-- 
                                                          - Warp

Post a reply to this message