![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
chromatic number.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> (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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
scott <sco### [at] scott com> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp <war### [at] tag povray org> wrote:
> scott <sco### [at] scott com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |