dailysudoku.com :: View topic - DB Saturday Puzzle

dailysudoku.com
Discussion of Daily Sudoku puzzles

FAQ

Memberlist

Usergroups

Profile

DB Saturday Puzzle - April 8, 2006

dailysudoku.com Forum Index -> Other puzzles

View previous topic :: View next topic

Author

Message

keith

Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA

Posted: Sat Apr 08, 2006 11:53 am Post subject: DB Saturday Puzzle - April 8, 2006

Here is today's puzzle. Easier than most.

Code:

Puzzle: DB040806 ******
+-------+-------+-------+
| 7 . . | 5 1 . | . . . |
| 5 . . | 8 . 9 | . . . |
| 4 6 1 | . . . | . . . |
+-------+-------+-------+
| . . . | . 9 . | . 8 2 |
| . 1 . | . . . | . 4 . |
| 2 4 . | . 3 . | . . . |
+-------+-------+-------+
| . . . | . . . | 1 7 3 |
| . . . | 3 . 7 | . . 9 |
| . . . | . 8 5 | . . 6 |
+-------+-------+-------+

Keith

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Sat Apr 08, 2006 9:27 pm Post subject:

Quote:

Here is today's puzzle. Easier than most.

Agreed. It almost seemed to solve itself while writing candidates in the cells. By the time that task was done, perhaps 80% of the cells were solved. Then a simple forcing chain finished it off.

However, I have a question about terminology. My chain started in a cell containing a "69." The first test was the "6" and that led to duplicates in a column, so "9" was obviously the resident of that original cell, and that finished it off.

So, technically speaking, was what I did within the meaning of the term "forcing chain"? Some of the definitions I've seen say that it "forces" one or more other cells to be a certain value, because either value in the starting cell leads to the same value in the other cell(s).

I tend to use "forcing chain" to cover any technique when I test a number to see what happens. I think others might call some of these "implications" or "constellations", thus, my question.

Guest

Posted: Sun Apr 09, 2006 12:23 am Post subject:

Marty R. wrote:

So, technically speaking, was what I did within the meaning of the term "forcing chain"?

All you need in this puzzle is (beside one naked pair) an xy-wing (stem cell in r4c1).

I dont know, what deductions you made to get a duplicate in a column, but lets take this one:
If r6c7=6, then r6c3=9 and
r1c3=8
r4c1=6,r7c1=8,r5c1<>8,r5c3=8, (=> r1c3<>8)

Then you can go back through the chains to get this forcing chain:
r1c3=9 => r6c3=6 => r6c7=9
r1c3=8 => r6c3=9 => r5c3<>8 => r5c1=8 => r7c1=6 => r4c1=3 => r6c3=6 => r6c7=9

So, for each "elimination" (implication/constellation) chain you can get a multiple forcing chain. But often the elimination can be spot easier.

ravel
Guest

Posted: Sun Apr 09, 2006 12:24 am Post subject:

eh, it was me ...

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Sun Apr 09, 2006 3:50 pm Post subject:

Quote:

All you need in this puzzle is (beside one naked pair) an xy-wing (stem cell in r4c1).

Of course, I have no way of going back to the point where I started my chain. And I don't know if I would have seen the XY-Wing, but I don't recall looking for one. I have a tendency to look for chains, as that seems to be my "go-to" method.

Just another of the many examples showing how a variety of techniques can lead to a solution.

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Sun Apr 09, 2006 7:47 pm Post subject:

Quote:

All you need in this puzzle is (beside one naked pair) an xy-wing (stem cell in r4c1).

I dont know, what deductions you made to get a duplicate in a column,

Ravel, you aroused my curiosity, so I erased the thing and did it again. I think I arrived at the same point as the first time. I can now see that XY-Wing, but I don't see how it solves the puzzle.

Code:

----------------------------------------
|7 89 89 |5 1 6 |2 3 4 |
|5 3 2 |8 4 9 |7 6 1 |
|4 6 1 |2 7 3 |5 9 8 |
----------------------------------------
|36 57 57 |4 9 1 |36 8 2 |
|389 1 389 |6 5 2 |39 4 7 |
|2 4 69 |7 3 8 |69 1 5 |
----------------------------------------
|68 58 568 |9 2 4 |1 7 3 |
|1 2 4 |3 6 7 |8 5 9 |
|39 79 379 |1 8 5 |4 2 6 |
----------------------------------------

As to how I got to a duplicate:

r6c7=6-->r4c7=3-->r4c1=6-->r7c1=8-->r7c2=5-->r4c2=7-->r9c2=9-->r1c2=8-->r1c3=9

But also, r6c7=6-->r6c3=9. However, the above chain forced a "9" in r1c3, so we now have two "9s" in c3.

keith

Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA

Posted: Sun Apr 09, 2006 9:37 pm Post subject: XY-wing

Marty, The XY-wing (on <9>) is rooted in R4C1. It eliminates TWO possibilities of <9>: In R9C3 (leaving <37>) and R5C1 (leaving <38>). Then, R9C1 is pinned to be <9>, and the rest follows. Keith

ravel
Guest

Posted: Mon Apr 10, 2006 8:55 am Post subject:

Marty, the main reason for my post was to state, that chains, that lead to a contradiction are always equivalent to multiple forcing chains. This follows from the fact, that A => B is equivalent to (not B) => (not A). So you formulate also your chain now backwards to be r1c3<>9 => r1c2<>8 => r9c2<>9 => r4c2<>7 => r7c2<>5 => r7c1<>8 => r4c1<>6 => r4c7<>3 => r6c7<>6 r1c3=9 => r6c3<>9 => r6c7<>6 or r1c3=8 => r1c2=9 => r9c2=7 => r4c2=5 => r7c2=8 => r7c1=6 => r4c1=3 => r4c7=6 => r6c7=9 r1c3=9 => r6c3=6 => r6c7=9 resp. Many people look at forcing chains to be constructive and therefore positive, but at chains, that lead to a contradiction, as negative or even trial&error. But in fact they are equivalent, so there is no argument, that one is "better" than the other.

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Mon Apr 10, 2006 4:53 pm Post subject:

Keith, I missed that second elimination at r5c1. Ravel, thanks for that explanation. Thanks to both.

alanr555

Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39

Posted: Wed Apr 12, 2006 12:57 am Post subject:

Code:

> the main reason for my post was to state, that chains, that
> lead to a contradiction are always equivalent to multiple
> forcing chains. This follows from the fact, that A => B is
> equivalent to (not B) => (not A). So you formulate also
> your chain now backwards to be

GREAT CARE is needed here.
The above is true ONLY if every link in the chain consists
of exactly two value options.

It is possible to make use of "one-way" chains. These occur
when a link proves the truth of one member of a set of more
than two values. The truth of that value implies the falsehood
of all the others and any one of them can be used to continue
the chain to the point of the contradiction. However such a
chain is NOT reversible as proof of the falsehood of any one
member says nothing about the truth or falsehood of any
other member of the value set. It is only when (n-1) values
in a set on (n) values are proven false that the remaining
member is proven as true. Fortunately when n=2 (binary!)
the two considerations coincide and one has a reversible chain.

+++

> Many people look at forcing chains to be constructive and
> therefore positive, but at chains, that lead to a contradiction,
> as negative or even trial&error.

I take the latter view.

> But in fact they are equivalent, so there is no argument, that
> one is "better" than the other.

In MANY cases they are equivalent - but not all (certainly not
for all cases of "one-way" chains described above.

The challenge for those using "reductio ad absurdum" reasoning
is to transform the presntation so that the chain(s) conform(s) to
the concept of "B has value X irrespective of the value in cell A".
Unless this is demonstrated, there is no absolute proof that the
equivlence applies in the particular case that will be discussed.

I find it perfectly acceptable for someone to use trial and error
in order to locate a forcing chain BUT once found, the result
should be presented in an "all roads lead to Rome" fashion
rather than "starting from there leads into a swamp" as then
there is the logistical difficulty of getting back to the divergence
point in order to continue with the other route for the chain(s).

I remember from decades ago when my mother was with the
Ramblers that it was quite acceptable (even expected?!) that
one would get lost on a reconoitre walk but on the actual day
of leading the walk, getting lost or going the wrong one was
like a heinous sin - just not done by people with standards.
Thus it is with forcing chains and contradictions. One needs to
accept the squelchy mud of the byway in order to find the dryway.

Alan Rayner BS23 2QT

ravel
Guest

Posted: Wed Apr 12, 2006 9:55 am Post subject:

Hi Alan,

alanr555 wrote:

The above is true ONLY if every link in the chain consists
of exactly two value options ...

Can you give me a concrete example, where it would not be true ?

Quote:

> Many people look at forcing chains to be constructive and
> therefore positive, but at chains, that lead to a contradiction,
> as negative or even trial&error.

I take the latter view.

What i wanted to say is, that this is just a matter of taste, nothing else.
My taste is, that i prefer, what is easier to spot and/or easier to notate.

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Wed Apr 12, 2006 4:44 pm Post subject:

Quote:

> Many people look at forcing chains to be constructive and
> therefore positive, but at chains, that lead to a contradiction,
> as negative or even trial&error.

I take the latter view.

Alan, are you making a distinction between chains that lead to a contradiction and ones that don't? That is, do you think positively about the latter?

Everyone's entitled to their opinion, and I respect them all. In my case, chains, many of which lead to contradictions, allow me to solve just about all of the difficult puzzles that I do manage to solve. Chains are extremely powerful tools.

Sure, I'd love to solve more puzzles using coloring, fish, wings, rectangles, remote pairs and the like, but they all appear only occasionally in my little world. I'm sure that, in many cases, they're there and I don't spot them, but, nevertheless, when they're not available to me for whatever reason, I have nothing to turn to but chains.

I can see where these are a form of trial and error, but, regardless, they don't mitigate my satisfaction at arriving at the solution.

OK, I am now off the soapbox. Laughing

Guest

Posted: Wed Apr 12, 2006 9:50 pm Post subject:

Marty R. wrote:

That is, do you think positively about the latter?

I do, and also about the former Smile

I dont mind, how i can solve a puzzle, forward or backward.

ravel
Guest

Posted: Wed Apr 12, 2006 9:53 pm Post subject:

Think i should register, i always forget to fill in the name

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Thu Apr 13, 2006 3:27 pm Post subject:

ravel wrote:

Think i should register, i always forget to fill in the name Sad

Nah, since it happens so often, every time I see "Guest", I know it's you. Laughing

alanr555

Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39

Posted: Sun Apr 16, 2006 9:27 am Post subject:

Code:

>> Many people look at forcing chains to be constructive and
>> therefore positive, but at chains, that lead to a contradiction,
>> as negative or even trial&error.

> Are you making a distinction between chains that lead to a
> contradiction and ones that don't? That is, do you think
> positively about the latter?

I have responded on a similar point in the "This is Killing Me"
topic under this category of the forum.
Essentially, there ARE chains (provided that one can find the
starting point!) that PROVE the uniqueness of the value in a
particular cell whatever the value in the starting cell. Our
friend from Bavaria called them "Double Implication Chains"
(but they could theoretically be triple, quadruple etc!).

Basically, an implicational chain is a route from Cell A to Cell B
where the assumed value for Cell A leads a value for Cell B as
a result of "forced" intermediate values. If it can be shewn that
there exists an implicational chain starting at cell A (and leading
to cell B) for EVERY possible value of A AND which leads to the
same implied value for B then one has a positive set of chains
(DIC as above) and a resolved cell.

If one is dependent upon the "contradiction" method, one is
involved with setting values in cells until a contradiction is
reached and then ERASING them on backtracking. It is to
this erasure (trial and error) to which I object - not the logic
that underlies it. I am quite willing for 'possibilities' (ie pencil
marks) to be erased. what I do not countenance is the Ariadne's
Thread approach of setting "values" and then erasing them
because one's guess resulted in a contradiction. I accept that
it is valid (albeit mechanistic) and has the virtue of being CERTAIN
to reach a solution (given enough time!!!) but, as SamGJ writes
about computer solvers, what is the point?

+++
> Everyone's entitled to their opinion, and I respect them all.

> In my case, chains, many of which lead to contradictions,
> allow me to solve just about all of the difficult puzzles that
> I do manage to solve. Chains are extremely powerful tools.

Agreed - Chains are extremely powerful.
If one has discovered a chain leading to a contradiction, it may
often (can someone prove ALWAYS?) be possible to find a
different start point that would prove the uniqueness of cell B
whatever the value of cell A. This emphasises the positive!

If someone can present a generalised (ie mathematical/logical)
proof that a reductio ad absurdum chain must ALWAYS contain
an implication of a unique resolution for the cell concerned
- based on the a priori given situation - then I could accept
that "contradiction" methods are just a short cut. However, I
have yet to see any such general proof. There is a separate
topic (to which I have contributed) that addresses the special
case of four cells - it needs wider consideration.

> Sure, I'd love to solve more puzzles using coloring, fish,
> wings, rectangles, remote pairs and the like,

Why - just to stop the toolbox getting rusty?
If one has a set of universal principles that one can apply
without a tool box, so well and good. If chains can do ALL
that the other techniques can do (can they??) then why
bother with the tool box?

> but they all appear only occasionally in my little world.
> I'm sure that, in many cases, they're there and I don't
> spot them, but, nevertheless, when they're not available
> to me for whatever reason,
> I have nothing to turn to but chains.

Of course, workers of the world have nothing to lose, but .....!

> I can see where these are a form of trial and error, but,
> regardless, they don't mitigate my satisfaction at arriving
> at the solution.

The last point is the most important.

Far be it from me to deny satisfaction. All I am doing is
presenting another challenge - seeking a way to utilise
the undoubted power of chains in ways that do not draw
one into the realms of "trial and error".

Alan Rayner BS23 2QT

Marty R.

Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

Posted: Sun Apr 16, 2006 4:24 pm Post subject:

As always, Alan, your comments are appreciated.

Quote:

If one is dependent upon the "contradiction" method, one is
involved with setting values in cells until a contradiction is
reached and then ERASING them on backtracking. It is to
this erasure (trial and error) to which I object - not the logic
that underlies it.

I don't know that I'm "dependent" upon the contradiction method, but I'm definitely dependent on chains. As I mentioned earlier, when other techniques are not apparent, then I have to use chains. I don't start out looking for a contradiction; I wouldn't know how to do that, if indeed, there is even a way to do it.

I eyeball a cell to make sure it's a chain candidate, that is, each value can start off with at least a couple of links. Sometimes, it leads nowhere, sometimes it leads to a contradiction and sometimes it is positive, i.e., a DIC where other cells are forced by virtue of being the same for each value in the starting cell. I'm as happy with this as a contradiction.

Quote:

Why - just to stop the toolbox getting rusty?
If one has a set of universal principles that one can apply
without a tool box, so well and good. If chains can do ALL
that the other techniques can do (can they??) then why
bother with the tool box?

Just for the sheer fun of it. I have been trying to learn as many techniques as possible and want to have them available to me if needed. I don't know why, but I get a bigger kick from, say, coloring and unique rectangles, than, say, X-Wings or swordfish.

Quote:

All I am doing is
presenting another challenge - seeking a way to utilise
the undoubted power of chains in ways that do not draw
one into the realms of "trial and error".

I can't argue with that. But as I said above, I start a chain without deliberately trying trial and error. If it forces others cells, then I've done a positive DIC, if it results in a contradiction, then I've done trial and error.

What do others do when they encounter contradictions? Do they not use it to solve the starting cell and instead look for other things that are "positive"?

I hope that this doesn't come across as argumentative, as that is not my intent. It's just to try and explain where I'm coming from and looking for ways to become a better solver.

Again, Alan, I enjoy these discussions, even if I don't always understand everything that's being said.

ravel
Guest

Posted: Mon Apr 17, 2006 9:00 pm Post subject:

alanr555 wrote:

If someone can present a generalised (ie mathematical/logical)
proof that a reductio ad absurdum chain must ALWAYS contain
an implication of a unique resolution for the cell concerned
- based on the a priori given situation - then I could accept
that "contradiction" methods are just a short cut.

If only forcing chains are positive for you, that force a number in a cell, not those also, that eliminate one. you will not be able to solve hard puzzles with positive methods.
If you "allow" also the latter, i am still sure, that all contradiction/elimination chains are equivalent to forcing chains. Still awaiting a counter example. For bivalue/bilocation chains it is obviously for me, but i think it also holds for chains using box eliminations, k-tupels etc.
But when results from further steps are needed in the chain, it might be neccessary, that the equivalent forcing chain needs a "case distinction" for this.

As for the solving process, i do it like Marty. When i am stuck, i look at single candidates to see "what would happen, if". It can be part of an x-wing, 2 strong links, the stem cell of an xy-wing, start for an xy-chain, part of a closed chain or whatever. Or it can lead to an easy-to-spot elimination chain.
It is positive, when i find a nice solution. A method cannot be positive or negative for me, just more or less complicated and effective for a given situation.

Display posts from previous:

	dailysudoku.com Forum Index -> Other puzzles	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum