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

Theorem (Erdös): There exist graphs of arbitrarily high girth and 
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

On Fri, 23 Jan 2009 15:11:33 +0000, Invisible wrote:

> Sudoku. Nobody knows exactly how to pronounce it,

The Japanese do.  "Soo Dough Koo" is the way I have heard it pronounced.  
Spoken fairly quickly.

Jim

Post a reply to this message

Jim Henderson wrote:
> On Fri, 23 Jan 2009 15:11:33 +0000, Invisible wrote:
> 
>> Sudoku. Nobody knows exactly how to pronounce it,
> 
> The Japanese do.  "Soo Dough Koo" is the way I have heard it pronounced.  
> Spoken fairly quickly.
> 
> Jim

soo dough koo, or sud oh koo I've heard both.

-- 
~Mike

Post a reply to this message

Jim Henderson <nos### [at] nospamcom> wrote:
> The Japanese do.  "Soo Dough Koo" is the way I have heard it pronounced.  
> Spoken fairly quickly.

  No offence, but using English as a guide for pronounciation is a joke. ;)

-- 
                                                          - Warp

Post a reply to this message

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

I saw a solver someone had written using backtracking in Python (IIRC). It 
solved the empty sudoku problem in under a second. :-)

(Obviously, it wasn't a unique solution.)

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

I think you might need some backtracking in the hardest of problems.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   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.

> I think you might need some backtracking in the hardest of problems.

  Thinking about it, in fact I think the only requirement for a sudoku
puzzle to be rational is that it must have only one possible solution.
As far as I understand, all sudoku puzzles are like that.

  The difficulty of the puzzle is determined by how deep your deductions
must be if you want to solve it with certainty (ie. without trial and error).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> 
>   No offence, but using English as a guide for pronounciation is a joke. ;)
> 

It works for those who speak English. I realize the whole world does not 
speak English, but from English speaker to English Speaker it works.

I don't want to get into the IPA debate again, though. I can't 
understand IPA. I've read the Wikipedia entry on it, and I still can't 
understand it. It's completely non-intuitive to me.



-- 
~Mike

Post a reply to this message

Warp wrote:
>   Thinking about it, in fact I think the only requirement for a sudoku
> puzzle to be rational is that it must have only one possible solution.
> As far as I understand, all sudoku puzzles are like that.

I think that while it may be a rule that's the case, it isn't the case that 
such is mathematically guaranteed. In other words, I expect that it's not 
hard to make a sudoku puzzle with multiple solutions, but people don't make 
them like that because that takes the fun out of it?

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

On Fri, 23 Jan 2009 11:50:41 -0800, Darren New wrote:

> Warp wrote:
>>   Thinking about it, in fact I think the only requirement for a sudoku
>> puzzle to be rational is that it must have only one possible solution.
>> As far as I understand, all sudoku puzzles are like that.
> 
> I think that while it may be a rule that's the case, it isn't the case
> that such is mathematically guaranteed. In other words, I expect that
> it's not hard to make a sudoku puzzle with multiple solutions, but
> people don't make them like that because that takes the fun out of it?

I've done several where there were clearly multiple solutions - 
particularly at easier degrees of difficulty.

Jim

Post a reply to this message

On Fri, 23 Jan 2009 12:56:55 -0600, Mike Raiford wrote:

> Jim Henderson wrote:
>> On Fri, 23 Jan 2009 15:11:33 +0000, Invisible wrote:
>> 
>>> Sudoku. Nobody knows exactly how to pronounce it,
>> 
>> The Japanese do.  "Soo Dough Koo" is the way I have heard it
>> pronounced. Spoken fairly quickly.
>> 
>> Jim
> 
> soo dough koo, or sud oh koo I've heard both.

I've heard the second, but the first is more in line with Japanese 
pronunciation standards - and the word does come from Japanese.

Jim

Post a reply to this message

On Fri, 23 Jan 2009 14:28:43 -0500, Warp wrote:

> Jim Henderson <nos### [at] nospamcom> wrote:
>> The Japanese do.  "Soo Dough Koo" is the way I have heard it
>> pronounced. Spoken fairly quickly.
> 
>   No offence, but using English as a guide for pronounciation is a joke.
>   ;)

No offense taken, but now you get to show us a pronunciation guide. ;-)

Jim

Post a reply to this message

Jim Henderson <nos### [at] nospamcom> wrote:
> I've done several where there were clearly multiple solutions - 
> particularly at easier degrees of difficulty.

  Did you actually try to solve it in different ways?

-- 
                                                          - Warp

Post a reply to this message

Mike Raiford <"m[raiford]!at"@gmail.com> wrote:
> Warp wrote:

> > 
> >   No offence, but using English as a guide for pronounciation is a joke. ;)
> > 

> It works for those who speak English.

  And who exactly is that? I assume you realize that, for example, people
from Alabama pronounce English rather differently than people from Britain,
Scotland or Australia? The exact same words may be pronounced rather
differently in these English-speaking countries.

> I don't want to get into the IPA debate again, though. I can't 
> understand IPA. I've read the Wikipedia entry on it, and I still can't 
> understand it. It's completely non-intuitive to me.

  English is not much better. It depends on where you are from how you
should pronounce something.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   And who exactly is that? I assume you realize that, for example, people
> from Alabama pronounce English rather differently than people from
> Britain, Scotland or Australia? The exact same words may be pronounced
> rather differently in these English-speaking countries.

"The quantity of consonants in the English language is constant. If omitted
in one place, they turn up in another. When a Bostonian 'pahks' his 'cah',
the lost r's migrate southwest, causing a Texan to 'warsh' his car and
invest in 'erl wells'."

Post a reply to this message

Warp wrote:
>   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).

Uh, shouldn't that be (9!)^9 instead of 9^(9!)?

Regards,
John
(who does his Sudoku in pen)

Post a reply to this message

John VanSickle <evi### [at] hotmailcom> wrote:
> Warp wrote:
> >   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).

> Uh, shouldn't that be (9!)^9 instead of 9^(9!)?

  Yes. You are right.

  Btw, 9!^9 = 109110688415571316480344899355894085582848000000000, which
would be the total number of possible combinations of those numbers.
(Of course only a small percentage of all these combinations form valid
sudoku solutions, and if equal all symmetric positions, it gets even
smaller.)

-- 
                                                          - Warp

Post a reply to this message

On Sat, 24 Jan 2009 06:08:51 -0500, Warp wrote:

> Jim Henderson <nos### [at] nospamcom> wrote:
>> I've done several where there were clearly multiple solutions -
>> particularly at easier degrees of difficulty.
> 
>   Did you actually try to solve it in different ways?

Yes.

Jim

Post a reply to this message

Jim Henderson <nos### [at] nospamcom> wrote:
> On Sat, 24 Jan 2009 06:08:51 -0500, Warp wrote:

> > Jim Henderson <nos### [at] nospamcom> wrote:
> >> I've done several where there were clearly multiple solutions -
> >> particularly at easier degrees of difficulty.
> > 
> >   Did you actually try to solve it in different ways?

> Yes.

  I mean: did you get two different solutions, or did you arrive at the
same solution by two different paths?

-- 
                                                          - Warp

Post a reply to this message

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

I was assuming (as do most others I think) that sudoku problems only have 1 
unique solution.  What would be the point of an empty grid?

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

However most people would rather use trial and error than go very deep in 
logical deductions.  ie write a 3 in lightly and fill in a few more squares 
based on that, oops no that doesn't work, original square must have been a 6 
then.  Isn't trial and error a form of deduction anyway?

Post a reply to this message

>> It works for those who speak English.
>
>  And who exactly is that? I assume you realize that, for example, people
> from Alabama pronounce English rather differently than people from 
> Britain,
> Scotland or Australia? The exact same words may be pronounced rather
> differently in these English-speaking countries.

They probably pronounce sudoku in their local accent though, you would sound 
a bit weird and out-of-place if you tried to sound exactly like a Japanese 
person saying it outside of Japan.

So what you're really trying to explain to people is that the Japanese Su/Ku 
letters rhyme with the English words "do" and "to", and the Japanese Do 
rhymes with a quickly spoken "saw" (OK those might not be the only or most 
accurate English words, but you get the idea).  If you pronounce the words 
to/do/saw differently, then chances are everyone is going to pronounce 
sudoku differently anyway, so you'll be fine.

Post a reply to this message

Nicolas Alvarez wrote:

> the lost r's migrate southwest, causing a Texan to 'warsh' his car and
> invest in 'erl wells'."

God help me if I ever talk like that.

We need an agreed upon pronunciation standard that A) is easy to 
understand for the majority of folks on here, and B) Won't get Warp's 
hackles up.

-- 
~Mike

Post a reply to this message

On Sun, 25 Jan 2009 17:03:13 -0500, Warp wrote:

> Jim Henderson <nos### [at] nospamcom> wrote:
>> On Sat, 24 Jan 2009 06:08:51 -0500, Warp wrote:
> 
>> > Jim Henderson <nos### [at] nospamcom> wrote:
>> >> I've done several where there were clearly multiple solutions -
>> >> particularly at easier degrees of difficulty.
>> > 
>> >   Did you actually try to solve it in different ways?
> 
>> Yes.
> 
>   I mean: did you get two different solutions, or did you arrive at the
> same solution by two different paths?

I got two different solutions.

Jim

Post a reply to this message

scott wrote:
>>  If trial-and-error was acceptable in a sudoku, then you could just as
>> well give an empty sudoku grid for someone to solve.
> 
> I was assuming (as do most others I think) that sudoku problems only 
> have 1 unique solution.  What would be the point of an empty grid?

To make sure your solving algorithm works! :)

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Jim Henderson <nos### [at] nospamcom> wrote:
> I got two different solutions.

  Then it sounds like that sudoku was broken. (How can they, for example,
give the solution to it if it has more than one?)

-- 
                                                          - Warp

Post a reply to this message

On Mon, 26 Jan 2009 13:56:21 -0500, Warp wrote:

> Jim Henderson <nos### [at] nospamcom> wrote:
>> I got two different solutions.
> 
>   Then it sounds like that sudoku was broken. (How can they, for
>   example,
> give the solution to it if it has more than one?)

No, it wasn't broken.

How many different possible solutions are there for filling in a Sudoku 
if no spaces are filled in?  Now fill in 6 of the spaces.  How many 
unique solutions result in numbers in those pre-filled conditions?

Logically, it *has* to be possible to come up with multiple solutions, 
otherwise there would only be *one* way to fill in the boxes to start 
with.

Jim

Post a reply to this message

On 26-Jan-09 9:39, scott wrote:
>>  If trial-and-error was acceptable in a sudoku, then you could just as
>> well give an empty sudoku grid for someone to solve.
> 
> I was assuming (as do most others I think) that sudoku problems only 
> have 1 unique solution.  What would be the point of an empty grid?
> 
>>  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.
> 
> However most people would rather use trial and error than go very deep 
> in logical deductions.  ie write a 3 in lightly and fill in a few more 
> squares based on that, oops no that doesn't work, original square must 
> have been a 6 then.  

You can do the simple ones by trial and error but that would take too 
much time for the more difficult ones. There you need deduction to 
complete it in a reasonable time. Applying deduction for the simple ones 
makes those rather boring. More time spend on writing down the numbers 
than on actually thinking and that irritating pen is in the way when 
write so you can not see part of the puzzle, annoying. I stopped doing 
the simple ones. ;)

> Isn't trial and error a form of deduction anyway?

I don't think it is. It is, however, a general and well known solving 
strategy.

Post a reply to this message

On 26-Jan-09 14:46, Mike Raiford wrote:
> Nicolas Alvarez wrote:
> 
>> the lost r's migrate southwest, causing a Texan to 'warsh' his car and
>> invest in 'erl wells'."
> 
> God help me if I ever talk like that.
> 
> We need an agreed upon pronunciation standard that A) is easy to 
> understand for the majority of folks on here, 
agreed

> and B) Won't get Warp's hackles up.

<innocently> why? </innocently>

Post a reply to this message

andrel wrote:
> On 26-Jan-09 14:46, Mike Raiford wrote:
>> Nicolas Alvarez wrote:
>>
>>> the lost r's migrate southwest, causing a Texan to 'warsh' his car and
>>> invest in 'erl wells'."
>>
>> God help me if I ever talk like that.
>>
>> We need an agreed upon pronunciation standard that A) is easy to 
>> understand for the majority of folks on here, 
> agreed
> 
>> and B) Won't get Warp's hackles up.
> 
> <innocently> why? </innocently>

So we don't get Warp's hackles up when someone innocently asks how 
something is pronounced. That's why.

Can you think of a better reason? :)

-- 
~Mike

Post a reply to this message

On 26-Jan-09 21:40, Mike Raiford wrote:
> andrel wrote:
>> On 26-Jan-09 14:46, Mike Raiford wrote:
>>> Nicolas Alvarez wrote:
>>>
>>>> the lost r's migrate southwest, causing a Texan to 'warsh' his car and
>>>> invest in 'erl wells'."
>>>
>>> God help me if I ever talk like that.
>>>
>>> We need an agreed upon pronunciation standard that A) is easy to 
>>> understand for the majority of folks on here, 
>> agreed
>>
>>> and B) Won't get Warp's hackles up.
>>
>> <innocently> why? </innocently>
> 
> So we don't get Warp's hackles up when someone innocently asks how 
> something is pronounced. 
<innocently> I though that was the sole object of it </innocently>

Post a reply to this message

andrel wrote:
> On 26-Jan-09 21:40, Mike Raiford wrote:
>> andrel wrote:
>>> On 26-Jan-09 14:46, Mike Raiford wrote:
>>>> Nicolas Alvarez wrote:
>>>>
>>>>> the lost r's migrate southwest, causing a Texan to 'warsh' his car and
>>>>> invest in 'erl wells'."
>>>>
>>>> God help me if I ever talk like that.
>>>>
>>>> We need an agreed upon pronunciation standard that A) is easy to 
>>>> understand for the majority of folks on here, 
>>> agreed
>>>
>>>> and B) Won't get Warp's hackles up.
>>>
>>> <innocently> why? </innocently>
>>
>> So we don't get Warp's hackles up when someone innocently asks how 
>> something is pronounced. 
> <innocently> I though that was the sole object of it </innocently>

Ahh, I missed the overall goal then. Carry on.

-- 
~Mike

Post a reply to this message

Jim Henderson <nos### [at] nospamcom> wrote:
> No, it wasn't broken.

> How many different possible solutions are there for filling in a Sudoku 
> if no spaces are filled in?  Now fill in 6 of the spaces.  How many 
> unique solutions result in numbers in those pre-filled conditions?

> Logically, it *has* to be possible to come up with multiple solutions, 
> otherwise there would only be *one* way to fill in the boxes to start 
> with.

  If there were multiple solutions to sudoku puzzles, it would be
impossible to give an answer, like most sudoku magazines have: The
given answer would only be *one* of the solutions and wouldn't really
help.

  That's the marvel of sudoku: There's only one solution, but it's hard
to find because you need to make a lot of deductions in order to come up
with the correct numbers. The harder the sudoku is rated, the deeper the
chain of deductions you need.

-- 
                                                          - Warp

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> Isn't trial and error a form of deduction anyway?

  The most common aid used in solving sudoku (and thus supported by most
sudoku software) is to put small marks like "in this 3x3 subgrid a 5 goes
to either this square or this one" (by writing small 5's at the corner of
the square) and the like. I don't call that "trial and error", but a form
of bookkeeping. You are simply marking what you can deduce (ie. which
numbers must go where). At some point when you solve parts of the rest
of the puzzle, you'll end up seeing in which of the two squares the 5
really goes.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   That's the marvel of sudoku: There's only one solution,

I think it's possible (trivial, even) to create a sudoku puzzle with 
multiple solutions quite easily. You have to trust the people generating the 
puzzles to ensure they're unique. If the creator hasn't done that, then you 
wind up with a sudoku puzzle with multiple solutions. Whether you still want 
to call that Sudoku or not (or just call it "like sudoku, but with multiple 
correct answers") is another question.

Conceivably, even crossword puzzles might have multiple solutions, altho 
it's far less likely.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   That's the marvel of sudoku: There's only one solution,

> I think it's possible (trivial, even) to create a sudoku puzzle with 
> multiple solutions quite easily.

  I don't think anyone doubts that. In fact, creating a good sudoku with
a unique solution is probably the hard part.

> You have to trust the people generating the 
> puzzles to ensure they're unique. If the creator hasn't done that, then you 
> wind up with a sudoku puzzle with multiple solutions. Whether you still want 
> to call that Sudoku or not (or just call it "like sudoku, but with multiple 
> correct answers") is another question.

  I'd call it a poor sudoku puzzle. :)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Warp wrote:
>>>   That's the marvel of sudoku: There's only one solution,
> 
>> I think it's possible (trivial, even) to create a sudoku puzzle with 
>> multiple solutions quite easily.
> 
>   I don't think anyone doubts that. In fact, creating a good sudoku with
> a unique solution is probably the hard part.

OK. It just wasn't clear whether you were saying it *does* have only one 
solution, or *should* only have one solution.

-- 
   Darren New, San Diego CA, USA (PST)
   "Ouch ouch ouch!"
   "What's wrong? Noodles too hot?"
   "No, I have Chopstick Tunnel Syndrome."

Post a reply to this message

On Mon, 26 Jan 2009 16:30:34 -0500, Warp wrote:

> Jim Henderson <nos### [at] nospamcom> wrote:
>> No, it wasn't broken.
> 
>> How many different possible solutions are there for filling in a Sudoku
>> if no spaces are filled in?  Now fill in 6 of the spaces.  How many
>> unique solutions result in numbers in those pre-filled conditions?
> 
>> Logically, it *has* to be possible to come up with multiple solutions,
>> otherwise there would only be *one* way to fill in the boxes to start
>> with.
> 
>   If there were multiple solutions to sudoku puzzles, it would be
> impossible to give an answer, like most sudoku magazines have: The given
> answer would only be *one* of the solutions and wouldn't really help.

Some of the articles I've read have suggested that a puzzle with more 
than one solution is generally considered "broken" or "nonstandard".  
Nevertheless, those configurations do exist, and in electronic games, 
they do turn up.

Jim

Post a reply to this message

On Mon, 26 Jan 2009 18:40:30 -0500, Warp wrote:

>> You have to trust the people generating the puzzles to ensure they're
>> unique. If the creator hasn't done that, then you wind up with a sudoku
>> puzzle with multiple solutions. Whether you still want to call that
>> Sudoku or not (or just call it "like sudoku, but with multiple correct
>> answers") is another question.
> 
>   I'd call it a poor sudoku puzzle. :-)

Ah, but you *would* call it a Sudoku puzzle nonetheless. ;-)

Jim

Post a reply to this message

>> Isn't trial and error a form of deduction anyway?
>
>  The most common aid used in solving sudoku (and thus supported by most
> sudoku software) is to put small marks like "in this 3x3 subgrid a 5 goes
> to either this square or this one" (by writing small 5's at the corner of
> the square) and the like. I don't call that "trial and error", but a form
> of bookkeeping.

But then at some point, you are going to think to yourself - if I put the 5 
in this box, that means a 7 must go in that box (maybe some more steps here) 
nope that doesn't work, therefore the original 5 must go in that other box. 
Isn't that trial and error?

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> >> Isn't trial and error a form of deduction anyway?
> >
> >  The most common aid used in solving sudoku (and thus supported by most
> > sudoku software) is to put small marks like "in this 3x3 subgrid a 5 goes
> > to either this square or this one" (by writing small 5's at the corner of
> > the square) and the like. I don't call that "trial and error", but a form
> > of bookkeeping.

> But then at some point, you are going to think to yourself - if I put the 5 
> in this box, that means a 7 must go in that box (maybe some more steps here) 
> nope that doesn't work, therefore the original 5 must go in that other box. 
> Isn't that trial and error?

  No, trial and error is thinking "I don't know if the 5 goes into this
box, but I'll put it anyways to see if it works" and then later if it
doesn't work you erase it.

-- 
                                                          - Warp

Post a reply to this message

>> But then at some point, you are going to think to yourself - if I put the 
>> 5
>> in this box, that means a 7 must go in that box (maybe some more steps 
>> here)
>> nope that doesn't work, therefore the original 5 must go in that other 
>> box.
>> Isn't that trial and error?
>
>  No, trial and error is thinking "I don't know if the 5 goes into this
> box, but I'll put it anyways to see if it works" and then later if it
> doesn't work you erase it.

I don't see the difference between what you just said and what I said... oh 
well.

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> >> But then at some point, you are going to think to yourself - if I put the 
> >> 5
> >> in this box, that means a 7 must go in that box (maybe some more steps 
> >> here)
> >> nope that doesn't work, therefore the original 5 must go in that other 
> >> box.
> >> Isn't that trial and error?
> >
> >  No, trial and error is thinking "I don't know if the 5 goes into this
> > box, but I'll put it anyways to see if it works" and then later if it
> > doesn't work you erase it.

> I don't see the difference between what you just said and what I said... oh 
> well.

  The difference is in the "if". When you think "if I put 5 here, then..."
that's deduction. If you think "I don't know if 5 goes here, but I'll put
it anyways", that's trial and error.

-- 
                                                          - Warp

Post a reply to this message