sudoku, again

[RichD]

ok, sudoku has probly been discussed 1000 times, so make it 1001 -

It's just a matter of logical elimination, tedious,
and holds no interest for me. Maybe for speed
contests, there's some challenge.

However, there are some interesting theoretical
questions. For instance, if we scale up to
N x N, with N (rather than 9) unique symbols,
what is the computational complexity?

What about 3-D?

Another thing: sometimes, I get to a point where
most of the cells are known, but a few remain
unresolved; each has typically 2 or 3 candidate
digits. This portion can only be solved through
brute force (one good guess usually brings in
the boat).

The question is: what is the largest possible
number of such unresolved cells?


--
Rich

[1treePetrifiedForestLane]

at least eighty-one.

[Eric Sosman]

On 9/15/2011 5:54 PM, RichD wrote:
> It's just a matter of logical elimination, tedious,

> and holds no interest for me.[...]

> Another thing: sometimes, I get to a point where

> most of the cells are known, but [...]

Who shaves the barber?

--
Eric Sosman
eso...@ieee-dot-org.invalid

[Rock Brentwood]

On Sep 15, 4:54 pm, RichD <r_delaney2...@yahoo.com> wrote:
> It's just a matter of logical elimination, tedious,
> and holds no interest for me.  Maybe for speed
> contests, there's some challenge.

It's not that tedious (anymore, for me).

> However, there are some interesting theoretical
> questions.  For instance, if we scale up to
> N x N, with N (rather than 9) unique symbols,
> what is the computational complexity?
>
> What about 3-D?

Actually Sudoku is not 2-D N x N (N = 9). It's 4-D M x N x N x M (M =
3 = N). The 4 coordinates are presented in a 2-D format with the
coordinates being (w, x) for the coordinates of the subgrids and (y,
z) for the coordinates within the subgrids. The Sudoku function f(w,
x, y, z) maps to an MN-sized set and satisfies the conditions:
In-grid one-to-one: f(w, x, _, _) is one-to-one for each (w, x) in
M x N.
In-column one-to-one: f(w, _, y, _) is one-to-one for each (w, y)
in M x N.
In-row one-to-one: f(_, x, _, z) is one-to-one for each (x, z) in N
x M.
The w, z coordinates range over M values, the x, y coordinates range
over N values.

> Another thing: sometimes, I get to a point where
> most of the cells are known, but a few remain
> unresolved; each has typically 2 or 3 candidate
> digits.  This portion can only be solved through
> brute force (one good guess usually brings in
> the boat).

There's a lot more going on than that. There are also "exclusion"
heuristics. For instance, of 3 cells in a given row, column or square
(for M = 3 = N Sudoku) are narrowed down to any one of 3 values and
only 3, then the remaining 6 can only have one of the remaining 6
values. This can ramify to lead to exclusions elsewhere in other rows,
columns or squares.

> The question is: what is the largest possible
> number of such unresolved cells?

The REAL issue is that to solve a Sudoku grid, there are actually TWO
parts: (a) find a solution (i.e. prove that one exists), but also (b)
prove that it is the ONLY solution.

You can work backwards, for a given initial grid, and try out
different starting configurations to see which ones have unique
solutions. First, take all the starting configurations that have one
less square filled in than the original puzzle did. See which ones
have unique solutions. Then for each of these, repeat the process.
Eventually, you get to the minimal start-up boards -- the ones which
have no unique solution if any of its initially filled-in squares is
blanked out.

More generally, you can randomly fill in a grid to satisfy the 3
Sudoku conditions listed above, and then work backwards in the way
just described to find all the minimal starting grids.

[Mike Terry]

"Rock Brentwood" <federat...@netzero.com> wrote in message
news:6c619e53-d125-494f...@19g2000vbx.googlegroups.com...
[snip..]

>
> The REAL issue is that to solve a Sudoku grid, there are actually TWO
> parts: (a) find a solution (i.e. prove that one exists), but also (b)
> prove that it is the ONLY solution.

I've never come across a sudoku variant where part of the objective was to
prove the solution is unique. In contrast, many sudoku puzzles actually
state up front that the solutions are unique as one of the puzzle
constraints, and the ones that don't do this *are* in fact always unique,
i.e. they have just made the constraint a "secret rule" of the puzzle
(grrrr!).

Mike.

[Mike Terry]

"Mike Terry" <news.dead.p...@darjeeling.plus.com> wrote in message
news:s9qdneVsZvHcN-nT...@brightview.co.uk...

Yeah yeah yeah... some puzzle setters screw up, and the puzzles aren't
actully unique by mistake :-)

[Eric Sosman]

Not sure why a solver should complain, or even care. If the
task is seen as "Find a solution," then any solution suffices and
the question of uniqueness never arises. If the task is "Find all
solutions," then puzzles having only one are if anything even less
interesting than those with more.

I guess it could be irritating if the task is "Find the
solution" and you find "the other" solution and an answer-checker
tells you you're wrong. But that's not a defect in the puzzle;
it's a fault of the answer-checker.[*]

[*] Friend of mine once had to take a really basic skills
screening test, and gave "1 3/8" as the answer to one question.
The person administering the test determined that my friend had
goofed, because the answer sheet gave "11/8" instead ...

--
Eric Sosman
eso...@ieee-dot-org.invalid

[Mike Terry]

"Eric Sosman" <eso...@ieee-dot-org.invalid> wrote in message
news:j52dio$ctt$1...@dont-email.me...

> On 9/17/2011 10:10 AM, Mike Terry wrote:
> > "Rock Brentwood"<federat...@netzero.com> wrote in message
> > news:6c619e53-d125-494f...@19g2000vbx.googlegroups.com...
> > [snip..]
> >>
> >> The REAL issue is that to solve a Sudoku grid, there are actually TWO
> >> parts: (a) find a solution (i.e. prove that one exists), but also (b)
> >> prove that it is the ONLY solution.
> >
> > I've never come across a sudoku variant where part of the objective was
to
> > prove the solution is unique. In contrast, many sudoku puzzles actually
> > state up front that the solutions are unique as one of the puzzle
> > constraints, and the ones that don't do this *are* in fact always
unique,
> > i.e. they have just made the constraint a "secret rule" of the puzzle
> > (grrrr!).
>
> Not sure why a solver should complain, or even care. If the
> task is seen as "Find a solution," then any solution suffices and
> the question of uniqueness never arises. If the task is "Find all
> solutions," then puzzles having only one are if anything even less
> interesting than those with more.

I wouldn't mind a puzzle where proving uniqueness was part of the aim of
solving the puzzle, if the puzzle clearly stated this. I don't believe
sudoku puzzles generally require this.

My "grrrr" was expressing my pet annoyance for puzzles with secret rules in
general. The issue for me is that these create a slight dilemma - should
the secret rules be used in solving the puzzle? To not use a rule that you
know to be valid just means you're possibly going to end up taking longer
solving the puzzle than you would otherwise, or that you will take longer
than someone who uses the rule which is unfair in a competitive sense. (OK,
I know not everyone is competitive! :-) Anyway, it's quite hard
deliberately not using a rule you know to be valid.

But... really what's the point in having a secret rule? Why not e.g. just
improve the statement of the puzzle so that the rule is explicit?

In other words I think secret rules are in fact mistakes - a consequence of:
a) bad wording of the puzzle statement
(if the rule is intended, but not stated) or
b) bad software generating the puzzle
(if the rule is unintended, but results from the software used
to generate the puzzle, e.g. maybe a sudoku generator never
puts a 1 in the top left cell, which would result in a
"secret rule"...)

(In the case of sudoku uniqueness, perhaps we could say that uniqueness is
simply universally understood, not an ommission in the puzzle statement, but
then why try to give a puzzle statement at all in that case?)

Regards,
Mike.

[Stephen J. Herschkorn]

It's no secret.  But if there is not a unique solution, the solver by necessity gets to a point where the "next step" is no longer logically implied by the structure of the puzzle.  That is, you have several equally valid guesses, all of which lead to a solution.  That defeats the whole purpose of the puzzle.

-- 
Stephen J. Herschkorn                        sjher...@netscape.net
Math Tutor on the Internet and in Central New Jersey and Manhattan

[Gus Gassmann]

On Sep 17, 12:14 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 9/17/2011 10:10 AM, Mike Terry wrote:
>

> > "Rock Brentwood"<federation2...@netzero.com>  wrote in message

> >news:6c619e53-d125-494f...@19g2000vbx.googlegroups.com...
> > [snip..]
>
> >> The REAL issue is that to solve a Sudoku grid, there are actually TWO
> >> parts: (a) find a solution (i.e. prove that one exists), but also (b)
> >> prove that it is the ONLY solution.
>
> > I've never come across a sudoku variant where part of the objective was to
> > prove the solution is unique.  In contrast, many sudoku puzzles actually
> > state up front that the solutions are unique as one of the puzzle
> > constraints, and the ones that don't do this *are* in fact always unique,
> > i.e. they have just made the constraint a "secret rule" of the puzzle
> > (grrrr!).
>
>      Not sure why a solver should complain, or even care.  If the
> task is seen as "Find a solution," then any solution suffices and
> the question of uniqueness never arises.  If the task is "Find all
> solutions," then puzzles having only one are if anything even less
> interesting than those with more.
>
>      I guess it could be irritating if the task is "Find the
> solution" and you find "the other" solution and an answer-checker
> tells you you're wrong.  But that's not a defect in the puzzle;
> it's a fault of the answer-checker.[*]

The sudokus at brainbashers.com have that explicit uniqueness
constraint. In fact they show you in their hints some configurations
where elimination is possible based on uniqueness. (If cell (r,c)
takes value n instead of m, then there are provably two solutions,
ergo (r,c) must equal m, that sort of thing.)

[Herman Rubin]

On 2011-09-17, Stephen J. Herschkorn <sjher...@netscape.net> wrote:

> Mike Terry wrote:

>>"Rock Brentwood" <federat...@netzero.com> wrote in message
>>news:6c619e53-d125-494f...@19g2000vbx.googlegroups.com...
>>[snip..]


>>>The REAL issue is that to solve a Sudoku grid, there are actually TWO
>>>parts: (a) find a solution (i.e. prove that one exists), but also (b)
>>>prove that it is the ONLY solution.



>>I've never come across a sudoku variant where part of the objective was to
>>prove the solution is unique. In contrast, many sudoku puzzles actually
>>state up front that the solutions are unique as one of the puzzle
>>constraints, and the ones that don't do this *are* in fact always unique,
>>i.e. they have just made the constraint a "secret rule" of the puzzle
>>(grrrr!).

I have done sudoku puzzles in which I have gotten to a point from
which I could produce two solutions. I have not followed up on
these.

> It's no secret. But if there is not a unique solution, the solver by
> necessity gets to a point where the "next step" is no longer logically
> implied by the structure of the puzzle. That is, you have several
> equally valid guesses, all of which lead to a solution. That defeats
> the whole purpose of the puzzle.



--

This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558

[RichD]

On Sep 18, Herman Rubin <hru...@skew.stat.purdue.edu> wrote:
> >>>The REAL issue is that to solve a Sudoku grid, there are actually TWO
> >>>parts: (a) find a solution (i.e. prove that one

> >>>exists), but also (b)prove that it is the ONLY
> >>>solution.
>

> I have done sudoku puzzles in which I have gotten
> to a point from which I could produce two
> solutions.

What is the smallest number of initially
fixed cells such that the solution is
guaranteed unique?


--
Rich

[Willem]

RichD wrote:
) On Sep 18, Herman Rubin <hru...@skew.stat.purdue.edu> wrote:
)> >>>The REAL issue is that to solve a Sudoku grid, there are actually TWO
)> >>>parts: (a) find a solution (i.e. prove that one
)> >>>exists), but also (b)prove that it is the ONLY
)> >>>solution.
)>
)> I have done sudoku puzzles in which I have gotten
)> to a point from which I could produce two
)> solutions.
)
) What is the smallest number of initially
) fixed cells such that the solution is
) guaranteed unique?

78, I think. Or 17. I'm not sure what you wanted to ask exactly.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[1treePetrifiedForestLane]

as the answer to, what is the gretest number
of empty cells, such that the solution is unique?, then
was it proven to be 17, or 16?

[Moshe Rubin]

On Sep 17, 8:11 pm, "Mike Terry"
<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "Eric Sosman" <esos...@ieee-dot-org.invalid> wrote in message

>
> news:j52dio$ctt$1...@dont-email.me...
>
>
>
>
>
>
>
>
>
> > On 9/17/2011 10:10 AM, Mike Terry wrote:

> > > "Rock Brentwood"<federation2...@netzero.com>  wrote in message

> > esos...@ieee-dot-org.invalid


For just such a discussion as relates to the Solitaire Battleships
puzzle genre, see:

http://www.mountainvistasoft.com/t-uniq.htm

(Disclaimer <g>: Fathom It! is the name of a Windows game application
for playing and solving Battleship puzzles authored by yours truly.)

Many Battleship puzzle solvers assume there is a single, unique
underlying solution. This often leads to sloppy solving where the
solver makes a wild guess and, when s/he is able to finish the puzzle
based on this guess, assumes s/he has 'solved' the puzzle.
Unfortunately, Battleship puzzles often have multiple solutions,
leading to frustration, etc.

Alternatively, the solver may use the 'unique solution assumption' to
solve the puzzle elegantly (see examples: http://www.mountainvistasoft.com/solution/7-125.htm
and http://www.mountainvistasoft.com/solution/10-22.htm). As elegant
as it is, it is using an implicit assumption of uniqueness that may
not be true.

The bottom line is that one should solve Battleship (and other)
puzzles without assuming uniqueness. When one solves the puzzle, one
should be able to state that there is only one possible solution.
This is done by using only logically deductive strategies, without
resorting to guessing.

Moshe Rubin

http://www.mountainvistasoft.com
Home of Fathom It!, the Solitaire Naval Puzzle for Logical Deduction
Buffs

[Willem]

Moshe Rubin wrote:
) The bottom line is that one should solve Battleship (and other)

) puzzles without assuming uniqueness. When one solves the puzzle, one

) should be able to state that there is only one possible solution.
) This is done by using only logically deductive strategies, without
) resorting to guessing.

Slight nitpick:

Guessing is allowed, but it should be used to *eliminate* a possibility
by arriving at a contradiction.

[Moshe Rubin]

Nitpick acknowledged <g>. All logically valid Battleship solving
rules fall into one of the following two categories:

(a) The rule is an immediate positive inference rule (e.g., 'all cells
remaining in a row must be ship segments', 'there is only one position
in the grid to place the battleship')

(b) A proposed move ends in a proof by contradiction (as you mention
above), indicating that the move is incorrect.

Any move whose only merit is that it leads directly to a valid
solution is not a rigorous rule and should not be used because it
cannot prove there is a single, unique solution. This is what I mean
when I refer to 'a guess'.

Moshe

[RichD]

On Sep 20, Willem <wil...@toad.stack.nl> wrote:
> )> >>>The REAL issue is that to solve a Sudoku grid, there are actually TWO
> )> >>>parts: (a) find a solution (i.e. prove that one
> )> >>>exists), but also (b)prove that it is the ONLY
> )> >>>solution.
> )>
> )> I have done sudoku puzzles in which I have gotten
> )> to a point from which I could produce two
> )> solutions.
> )
> ) What is the smallest number of initially
> ) fixed cells such that the solution is
> ) guaranteed unique?
>
> 78, I think.  Or 17.  I'm not sure what you wanted to ask exactly.

It's a bit tricky to phrase precisely, though a simpe question.

What is the smallest number of initially determined cells,
such that there is at least one puzzle of such configuration,
with a unique solution?

And you claim there is a known example of 17?

--
Rich

[Andrew B]

http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php claims to list
about 50,000 known examples.

[Mike Terry]

"Moshe Rubin" <moshe...@gmail.com> wrote in message
news:fdd12e6f-ee31-4dfc...@f8g2000yqf.googlegroups.com...

<snip>

> For just such a discussion as relates to the Solitaire Battleships
> puzzle genre, see:

Hi Moshe - it seems I'm in disagreement with practically everything you say
below! :)

>
> http://www.mountainvistasoft.com/t-uniq.htm
>
> (Disclaimer <g>: Fathom It! is the name of a Windows game application
> for playing and solving Battleship puzzles authored by yours truly.)
>
> Many Battleship puzzle solvers assume there is a single, unique
> underlying solution. This often leads to sloppy solving where the
> solver makes a wild guess and, when s/he is able to finish the puzzle
> based on this guess, assumes s/he has 'solved' the puzzle.

"...assumes..."?

This begs the question - what IS the purpose of the puzzle:
- is it to "complete the grid etc. subject to constraints"
(in which case the solver assumes correctly - they HAVE solved it!) or
- is it to find and list out ALL POSSIBLE SOLUTIONS?

Is the puzzler expected to copy out the puzzle multiple times, and fill in
each copy with a valid completed grid until all the possible grid solutions
have been specified? Do the answers to the problem include all possible
solutions, and if a user found 5 solutions but missed one out would the user
be deemed to have got the wrong answer?
To me this is all ridiculous! (At least when applied to the regular logic
puzzles: Sudoku, Hitori, Nurikabe, etc.. I acknowledge there can be puzzles
where the objective might genuinely be to "list all possible answers"
satisfying given the constraints, e.g. "how many ways can black kill the
white group?" as a go puzzle.)

So for Sudoku etc, if the user correctly completes the grid according to the
constraints the user has solved it! (Surely?)

> Unfortunately, Battleship puzzles often have multiple solutions,
> leading to frustration, etc.

Deliberately so? That's a little surprising - I'm curious, how is the user
supposed to present the solution? (Given that the user is charged with
listing all possible solutions in order to have validly solved the puzzle!)

I don't really see why there would be frustration for the user who completes
the grid successfully - is it that they look up the "correct" solution and
find it's different? (That's a problem with the solution provider, not the
solver.)

Or is it that they look up the correct solution, and are told their's is
valid but there are others, so they've "failed"? (In this case were the
users told up front they had to find all possible solutions to succeed? If
so it's the solver's fault because they've genuinely failed; if not, I could
understand their frustration I guess, as the puzzle setter is clearly at
fault...)

>
> Alternatively, the solver may use the 'unique solution assumption' to
> solve the puzzle elegantly (see examples:
http://www.mountainvistasoft.com/solution/7-125.htm
> and http://www.mountainvistasoft.com/solution/10-22.htm).

I don't see how a solver can use this assumption if it's *not true*. OK
they could use it incorrectly, and might still arrive at a valid solution
through pure luck I suppose. :-) This could hardly be considered elegent
though! (Or are you changing your mind, and saying that in fact the puzzles
DO have unique solutions? Earlier you said explicitly they have multiple
solutions...)

My point would be that arguments based on the uniqueness of solutions are
perfectly valid if the solutions actually ARE guaranteed to be unique. I
consider this a Good Thing, because it adds to the richness of the puzzle
solving experience, and many uniqueness arguments are comparitively subtle
compared to "direct" arguments, and so are more fun (and skillful) when they
apply. Also, how can anyone tell you "you're not allowed to think in this
way to get the solution, even though it's correct logic"? (Quick, call in
the thought police! :)

> As elegant
> as it is, it is using an implicit assumption of uniqueness that may
> not be true.

Again, begging the question - are the solutions actually guaranteed to be
unique or not? If multiple solutions are valid, of course you shouldn't use
uniqueness as an argument. If they are unique, to not use this knowledge is
just to artificially limit your thinking.

The grey area is where the solutions ARE always unique, but you've just not
been told this explicitly - that's where my personal beef against "secret
rules" comes in... I think the puzzles become better puzzles when all such
secret rules are openly stated, and everyone solving the puzzle has the same
information.

>
> The bottom line is that one should solve Battleship (and other)
> puzzles without assuming uniqueness.

"...should..."? That's just your moral view of puzzle solving then :)

Aside from the implied "thought police" angle, I believe the puzzles are
actually *better* the more logical arguments you can bring to bear on them,
so uniqueness arguments add to the richness and pleasure of the puzzle
solving, and promote the development of greater skill levels, but that's
just my opinion I guess.

I've certainly nothing against anyone who wants to limit their own thinking
to make a puzzle harder - I do as much when I solve the easy sudokus in the
local Metro paper: there are three shaded squares that you can send off when
you complete the puzzle to maybe win a prize, but the puzzle is such that I
can challenge myself to just fill in the 3 shaded squares without entering
anything else on the grid. (Really it's too easy treating it as a regular
sudoku, but can be quite challenging with my extra restriction.) Still, I
wouldn't go so far as to say other solvers "should" only fill in the 3
shaded cells...

(Also, many of these problems are quite hard enough not to need extra
artificial restrictions to make them harder - in fact there are many that I
doubt I could solve at all without invoking uniqueness arguments.)

> When one solves the puzzle, one
> should be able to state that there is only one possible solution.

OK I understand this is your personal opinion, but I've never seen it
reflected in the wording of the puzzle statements. (If it were, it would be
impractical to ever verify that someone had correctly solved the puzzle, as
this would require verifying that their logic at each stage was correct,
rather than just checking the finished grid...) So it's not an *actual*
requirement of solving the puzzle after all.

And... this seems to be contradicting your earlier words! Didn't you say
that battleship puzzles validly have multiple solutions? (I check - yes you
did, so how could solvers be required to prove uniqueness?)

> This is done by using only logically deductive strategies, without
> resorting to guessing.

Arguments based on uniqueness certainly count as logically deductive
strategies. Also guessing is "in principle" fine - many standard techniques
ultimately come down to spotting contradictions resulting from what could
only otherwise be called an initial guess.

Personally I don't like the approach of guessing a cell, filling it in, and
proceding to continue solving and filling in cells until (darn-it!) it
becomes clear the puzzle is impossible, then rubbing out all the "guesses"
and just starting again. It's not that this is an invalid approach to
solving the puzzle - my objection is simply that it's boring and makes the
puzzle too easy (and ultimately it makes all such puzzles routine), so I
decline to do it! OTOH I've no problem with performing the same basic
approach purely in my head to solve the puzzle - it's the physical writing
down and mechanical back-tracking that spoils the enjoyment for me, but
doing it in my head is good mental exercise and I quite enjoy it. (So again
I'm saying "guessing" in itself isn't "wrong" or "invalid".)


Anyway, let's all enjoy the puzzles in the way we enjoy - even people who
want to guess at random and later rub it all out I wouldn't begrudge them
doing this if that's what they enjoy! :-)

Mike.

[Moshe Rubin]

On Sep 22, 3:55 am, "Mike Terry"
<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "Moshe Rubin" <moshe.ru...@gmail.com> wrote in message

> > andhttp://www.mountainvistasoft.com/solution/10-22.htm).

> ultimately come down to spotting contradictions ...
>
> read more »

Hi Mike,

Coincidentally I too disagree with almost everything you've written,
but that's the beauty of a free world. I unfortunately do not have
the time or inclination to comment on every clause of your reply (I
have an uneasy sense of a flaming thread in the offing <g>). I will
remark that you should avoid attributing statements to someone
statements he never made (e.g., in response to my comment of

"Unfortunately, Battleship puzzles often have multiple solutions,

leading to frustration, etc.", you write "Deliberately so? That's a
little surprising". No, Mike, inadvertently, not deliberately).

There is often an implicit, although not mandatory, 'contract' between
puzzle maker and solver that there will be only one solution. The
existence of more than one solution often gives a feeling that the
puzzle maker didn't do his work correctly. GAMES Magazine, to mention
one such puzzle journal, will apologize in their 'Letters to the
Editor' whenever a reader reports a multiple solution. I think this
indicates the editorial mindset that multiple solutions are a glitch,
not a feature (and GAMES is a reputable puzzle magazine).

Let's take this 'multiple solutions are fine' thing to its logical
conclusion: present the reader with a blank 9x9 Sudoku grid and tell
him to find a solution. Whatever solution he comes up with should be
considered a solution and he should be thrilled. I have a sneak
feeling that our reader will be less than happy.

Speaking for myself (no, this is not the 'thought police' speaking
<G>) I get a thrill when I have matched my mind to that of the puzzle
maker, finding (and proving!) that there is only one solution, and
that I have grasped the cleverness of his puzzle. If I find another
solution I certainly wouldn't call myself a failure, but neither would
I have the satisfaction of having grasped the puzzle maker's
intentions. If that doesn't interest you, that's fine, too.

I get the feeling you didn't read, or understand, the t-uniq.htm web
page (you didn't relate to anything written there). Of course you're
free to have your own opinion, but I think Wei-Hwa Huang's opinion
counts for something -- it's certainly not a "ridiculous" one.

Bottom line: let's enjoy puzzle solving for the fun it's meant to be,
without getting sidetracked by philosophical hair-splitting.

Moshe

[Stephen J. Herschkorn]

I remember hearing long ago that, empirically, 17 was the smallest
number amogst sudokus prodcued to date. Has it actually been proven
that there can be no fewer than 17?

[1treePetrifiedForestLane]

yeah; in the meanwhile,
can someone post an example with 17 entries?

[1treePetrifiedForestLane]

yeah; in the meanwhile,
can someone post an example with 17 entries?

[Willem]

1treePetrifiedForestLane wrote:
) yeah; in the meanwhile,
) can someone post an example with 17 entries?

A link was already posted to a website with a collection of around 50,000
of them. And giggle gives enough hits for 'sudoku 17'.

[Mike Terry]

"Moshe Rubin" <moshe...@gmail.com> wrote in message

news:994c53fb-7b0a-4e4b...@u15g2000yqk.googlegroups.com...

> On Sep 22, 3:55 am, "Mike Terry"
> <news.dead.person.sto...@darjeeling.plus.com> wrote:

<snip>

Moshe - sorry if I've misrepresented what you said - initially I did think
you were saying Battleships solutions were routinely (by design) not unique,
but as I went on that didn't fit with later remarks, so I should have
understood. I think we're both in agreement that deliberately having
multiple solutions for these sorts of logic puzzles is bad all around, if
for no other reason that specifying and checking the solutions becomes
impractical.

I did read the t-uniq.htm page, and it basically says "I think the solver
should prove the solution is unique" which had already been said in this
thread. There is an argument around how uniqueness is a "meta-rule" and we
"shouldn't use meta-rules", but that's not convincing to me - I understand
"meta rule", but don't see why meta rules shouldn't be used, provided the
logic is correct, so it didn't seem to offer me any insight...

You're clearly not convinced by my suggestion that the puzzles are actually
better *as puzzles* if uniqueness arguments are employable? I imagine
puzzle setters are fully aware of this, and plan for some of their advanced
puzzles to be solved like this, but I don't really know as I don't create
these puzzles myself. (I've a feeling that advanced Slitherlink puzzles
that I solve are designed to require uniqueness arguments to solve, but of
course how could I be sure?...)

Anyway, happy puzzling! :)
Mike.

[Rock Brentwood]

On Sep 17, 9:10 am, "Mike Terry"

<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "Rock Brentwood" <federation2...@netzero.com> wrote in message

> > The REAL issue is that to solve a Sudoku grid, there are actually TWO
> > parts: (a) find a solution (i.e. prove that one exists), but also (b)
> > prove that it is the ONLY solution.
>
> I've never come across a sudoku variant where part of the objective was to
> prove the solution is unique.

Well, when the puzzles lose their lustre, we have to make up our own
challenges. So, I added item (b) to make everything more interesting.

[Rock Brentwood]

On Sep 22, 5:57 pm, "Mike Terry"

<news.dead.person.sto...@darjeeling.plus.com> wrote:
> You're clearly not convinced by my suggestion that the puzzles are actually
> better *as puzzles* if uniqueness arguments are employable?  I imagine
> puzzle setters are fully aware of this, and plan for some of their advanced
> puzzles to be solved like this, but I don't really know as I don't create
> these puzzles myself.  (I've a feeling that advanced Slitherlink puzzles
> that I solve are designed to require uniqueness arguments to solve, but of
> course how could I be sure?...)

The uniqueness part of Sudoku is generally tractible (for the grids
I've seen). So, it's worthwhile extending the problem into this even
where it's not originally stated as such.

Generally, uniqueness comes out by way of the solution method(s)
employed. What I've noticed for this particular puzzle is that there
are actually two levels of complexity for initial boards. Some have
solutions can be found (and proven unique) solely by exclusion
arguments with no branching (or backtracking) argument made at any
point.

Others reach a maximally filled out grid where exclusion can no longer
be used any further. At that point, it becomes necessary to branch non-
deterministically (or in parallel). Normally, I work it out in
parallel, rather than by backtracking, since it's easier to write out
parallel grids. I've never found a set up that did not ramify in
patterns such as A |- B + C, B |- fail, C |- D + E, etc. where a
traversal did not exist which kept the maximum number of live branches
under 3.

If you're stopping after one solution, you're employing a "parallel
or". In that case, if you had a tree like the following (where, now, I
make B a success branch):
A |- B + C, B |- true, C |- D + E, D |- true, E |- fail.
A possible traversal would be
A |- B + C, C |- D + E, D |- true, E cut off, C succeeds, B cut-
off, A succeeds
so B + C is treated as a "parallel or", where C succeeds and B is
terminated (or B succeeds and C, D and E are terminated).

[Rock Brentwood]

On Sep 16, 5:18 pm, Rock Brentwood <federation2...@netzero.com> wrote:
> On Sep 15, 4:54 pm, RichD <r_delaney2...@yahoo.com> wrote:
> > The question is: what is the largest possible
> > number of such unresolved cells?
>
> The REAL issue is that to solve a Sudoku grid, there are actually TWO
> parts: (a) find a solution (i.e. prove that one exists), but also (b)
> prove that it is the ONLY solution.

Of course, it also goes without saying, that the other reason I framed
this as a "uniqueness" problem is because otherwise the original query
would not make sense. If you didn't require unique solutions, then the
answer to the question above would just be "the largest number of
unresolved cells is where they are all left initially empty." So,
uniqueness was a defacto part of the original question.

[RichD]

On Sep 22, "Stephen J. Herschkorn" <sjhersc...@netscape.net> wrote:
> >>> ) What is the smallest number of initially
> >>> ) fixed cells such that the solution is
> >>> ) guaranteed unique?
>
> >>>78, I think.  Or 17.  I'm not sure what you
> >>>wanted to ask exactly.
>

> >>What is the smallest number of initially
> >>determined cells, such that there is at least
> >>one puzzle of such configuration,
> >>with a unique solution?
>
> >> And you claim there is a known example of 17?
>
> >http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php
> > claims to list about 50,000 known examples.
>
> I remember hearing long ago that, empirically,
> 17 was the smallest number amogst sudokus prodcued
> to date.  Has it actually been proven
> that there can be no fewer than 17?

You could do via brute force, checking every
sudoku with 16 entries.

What's the running time on that program?

--
Rich

[quasi]

If that was feasible, don't you think someone would have thought
of that, then implemented and ran such a search?

>What's the running time on that program?

A simpler question is:

What is a rough estimate for the number of sudoku starting
positions containing 16 entries?

I would guess about 10^25, which if so, means it's way out
of range for brute force checking.

quasi

[James Waldby]

On Fri, 23 Sep 2011 15:05:40 -0500, quasi wrote:

> On Fri, 23 Sep 2011 11:02:09 -0700 (PDT), RichD wrote:
>>On Sep 22, "Stephen J. Herschkorn" <sjhersc...@netscape.net> wrote:
>>> >>> ) What is the smallest number of initially ) fixed cells such that
>>> >>> the solution is ) guaranteed unique?
>>>
>>> >>>78, I think.  Or 17.  I'm not sure what you wanted to ask exactly.
>>>
>>> >>What is the smallest number of initially determined cells, such that
>>> >>there is at least one puzzle of such configuration,
>>> >>with a unique solution?
>>>
>>> >> And you claim there is a known example of 17?
>>>
>>> >http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php
>>> > claims to list about 50,000 known examples.
>>>
>>> I remember hearing long ago that, empirically, 17 was the smallest

>>> number amongst sudokus produced to date.  Has it actually been proven

>>> that there can be no fewer than 17?
>>
>>You could do via brute force, checking every sudoku with 16 entries.
>
> If that was feasible, don't you think someone would have thought of
> that, then implemented and ran such a search?
>
>>What's the running time on that program?
>
> A simpler question is:
>
> What is a rough estimate for the number of sudoku starting positions
> containing 16 entries?
>
> I would guess about 10^25, which if so, means it's way out of range for
> brute force checking.

Over 10^26 is another possible guess, based on following:
For each of about 5*10^9 distinct completed sudoku grids,
there are binomial(81,16) ~ 3*10^16 choices of 16 cells to
initially populate and then test. The product is 5*10^9 *
3*10^16 or 15*10^25. More precisely, the 5*10^9 number is
5,472,730,538, per <http://en.wikipedia.org/wiki/Sudoku>,
which provides links to OEIS references that in turn reference
several published papers on the counts of sudoku grids.

--
jiw

[Matthew Russotto]

In article <e8281bc4-7a66-42a6...@cd4g2000vbb.googlegroups.com>,

RichD <r_dela...@yahoo.com> wrote:
>On Sep 22, "Stephen J. Herschkorn" <sjhersc...@netscape.net> wrote:
>> >>> ) What is the smallest number of initially
>> >>> ) fixed cells such that the solution is
>> >>> ) guaranteed unique?
>>

>> >>>78, I think. =A0Or 17. =A0I'm not sure what you

>> >>>wanted to ask exactly.
>>
>> >>What is the smallest number of initially
>> >>determined cells, such that there is at least
>> >>one puzzle of such configuration,
>> >>with a unique solution?
>>
>> >> And you claim there is a known example of 17?
>>
>> >http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php
>> > claims to list about 50,000 known examples.
>>
>> I remember hearing long ago that, empirically,
>> 17 was the smallest number amogst sudokus prodcued

>> to date. =A0Has it actually been proven

>> that there can be no fewer than 17?
>
>You could do via brute force, checking every
>sudoku with 16 entries.
>
>What's the running time on that program?

81C16 on placement of entries. 9^16 on what they are.
So roughly 6 * 10^31 times the time it takes to solve a sudoku.
That's probably too long; it's about 2^106. But it's not that far
from tractable. Figure out enough symmetries and other ways of elimination and
it might actually become tractable.

For instance, fix the value of the first entry -- that's 3 bits right
there.
--
The problem with socialism is there's always
someone with less ability and more need.

[Matthew Russotto]

In article <j5lsi9$jkm$1...@dont-email.me>,

Matthew Russotto <russ...@grace.speakeasy.net> wrote:
>
>81C16 on placement of entries. 9^16 on what they are.
>So roughly 6 * 10^31 times the time it takes to solve a sudoku.
>That's probably too long; it's about 2^106. But it's not that far
>from tractable. Figure out enough symmetries and other ways of elimination and
>it might actually become tractable.

Oops I was basing that thought on the number of bits solved in
elliptic curve cryptography problems. But those are O(sqrt(N)), and
brute force sudoku is linear.