Sudoku. Nobody knows exactly how to pronounce it, but almost everybody 
knows what the rules are. And each person has their own Special Method 
for playing it.

Apparently it's actually a graph colouring problem. Or, equivilently, an 
exact cover problem. And it's provably NP-complete. (So, uh, how come 
it's solvable then? I thought "NP-complete" is supposed to mean 
"impossible to solve in less time than the age of the universe"?)

It appears you can theoretically solve it using the dancing links algorithm.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Sudoku. Nobody knows exactly how to pronounce it

  I'm not surprised *you* don't know how to pronounce it. ;)

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

-- 
                                                          - Warp

Post a reply to this message

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

chromatic number.

Post a reply to this message

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

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

Isn't trial-and-error a form of deduction?  ie "If I put a 4 in here, that 
square will need to be 3, and then that doesn't work so it must be a 6 in 
the original square".  Of course there are more complicated chains of logic, 
but essentially you try one number and see if it gives a valid result.

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> >  (A sudoku problem only makes sense if it's unambiguous, iow. it can be
> > solved unambiguously without trial-and-error, only by pure deduction.)

> Isn't trial-and-error a form of deduction?  ie "If I put a 4 in here, that 
> square will need to be 3, and then that doesn't work so it must be a 6 in 
> the original square".  Of course there are more complicated chains of logic, 
> but essentially you try one number and see if it gives a valid result.

  If trial-and-error was acceptable in a sudoku, then you could just as
well give an empty sudoku grid for someone to solve.

  The principle in sudoku puzzles is that they can be solved without having
to guess anything. The chain of required deductions may go very deep in
the hardest sudokus, but it's always possible to solve it without having
to guess.

-- 
                                                          - Warp

Post a reply to this message

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

If the number of unknowns is small enough, it should be possible to make 
it unambiguous. (E.g., if you have a 100 x 100 grid with 1 cell blank, 
how hard can it be to figure out what the final value is?)

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

So there we have it then: An absurdly inefficient algorithm! :-}

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> scott <sco### [at] scottcom> wrote:
> > >  (A sudoku problem only makes sense if it's unambiguous, iow. it can be
> > > solved unambiguously without trial-and-error, only by pure deduction.)

> > Isn't trial-and-error a form of deduction?  ie "If I put a 4 in here, that 
> > square will need to be 3, and then that doesn't work so it must be a 6 in 
> > the original square".  Of course there are more complicated chains of logic, 
> > but essentially you try one number and see if it gives a valid result.

>   If trial-and-error was acceptable in a sudoku, then you could just as
> well give an empty sudoku grid for someone to solve.

>   The principle in sudoku puzzles is that they can be solved without having
> to guess anything. The chain of required deductions may go very deep in
> the hardest sudokus, but it's always possible to solve it without having
> to guess.

  By the way, another requirement for the sudoku to be unambiguous is that
only one solution must exist.

-- 
                                                          - Warp

Post a reply to this message

One might argue that if, for a specific combination of givens, there is 
only one possible valid solution, then there must theoretically exist 
some chain of "logic" which can reveal it without backtracking.

Post a reply to this message