Can this be done with no trail and error?

Post the puzzle or solving technique that's causing you trouble and someone will help

Postby tarek » Sun Mar 12, 2006 9:54 pm

Hi MCC,

Just to make myself clear, Colouring of conjugates is pretty much universal, however the reasoning behind the elimination is different according to the state of the coloured grid.

Type 1: a non coloured candidate that "sees" both a Plus cell & a minus cell (or Green/Red, True/False) can be safely eliminated..........

Type 2: You can't have more than 1 candidates carrying the same colour in a sector, if that happens, all candidates carrying that colour in the grid can be safely eliminated

I don't like Type 2 because it is contradiction elimination...........

RULES (FACTS):

Fill in the grid so that
every row,
every column, and
every 3 x 3 box
contains the digits 1 through 9.


Statement:

We have 2 Greens/Pluses/Trues...... in a sector as a result of colouring candidate conjugates


The Statement CONTRADICTS the rules, don't you agree ?

As a result of that CONTRADICTION, a series of eliminations followed.

That is "contradiction elimination" IMO.

Tarek
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

Postby ronk » Sun Mar 12, 2006 10:22 pm

tarek wrote:
RULES (FACTS):

Fill in the grid so that
every row,
every column, and
every 3 x 3 box
contains the digits 1 through 9.


Statement:

We have 2 Greens/Pluses/Trues...... in a sector as a result of colouring candidate conjugates


The Statement CONTRADICTS the rules, don't you agree ?

I don't see a contradiction between those rules and that statement. Any one color represents -- alternately -- either the true and false state of a candidate. That state must simultaneously exist for all candidates with the same color over the entire grid. When one of those states causes a contradiction with the rules, that color must always be false.

Is that the type of contradiction you meant?

If so, I see that as entirely different from eliminations made upon discovering a contradiction caused by assertion or negation of a single candidate in a single cell, e.g.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tso » Sun Mar 12, 2006 11:19 pm

I'm with Ronk

Terak is makig what seems like an odd distinction. Here’s the puzzle, filtered for 8s for clarity:

Figure A
Code: Select all
*-----------------------------------------------*
|-8    .   .    | .   -8    .   | 8    .    .   |
| .    8   .    | .    .    .   | .    .    8   |
| .    8   .    | .    .   +8   | 8    .    .   |
|---------------+---------------+---------------|
|+8    .    .   | .    .   -8   | .    .    .   |
| .    .    .   | .    .    .   | 8    .    8   |
| .    .   -8   | .   +8    .   | .    .    .   |
|---------------+---------------+---------------|
| .    8    8   | .    .    .   | .    8    .   |
| .    .    .   | 8    .    .   | .    .    .   |
| .    .    8   | .    .    .   | .    8    .   |
*-----------------------------------------------*


No other 8’s are conjugates with these 7. Because two 8’s have the same symbol in the top row, we know that the PLUS signs are 8s and the MINUS signs are not. Your claim is that this is a contradiction -- a claim which I do not agree -- but I won’t argue that point. Instead, take a look a the following grid which has one change in brackets:


Figure B
Code: Select all
*-----------------------------------------------*
| 8    .   .    | .   -8    .   | 8    .    .   |
| .    8   .    | .    .    .   | .    .    8   |
| .    8   .    | .    .   +8   | 8    .    .   |
|---------------+---------------+---------------|
|+8    .    .   | .    .   -8   | .    .    .   |
| .    .    .   | .    .    .   | 8    .    8   |
| .    .   -8   | .   +8    .   | .    .    .   |
|---------------+---------------+---------------|
| .    8    8   | .    .    .   | .    8    .   |
| .    .    .   | 8    .    .   | .    .    .   |
|[8]   .    8   | .    .    .   | .    8    .   |
*-----------------------------------------------*


Because of the additional 8 at r9c1, the 8 at r1c1 cannot be labeled. We can still eliminate 8 from this cell, as it can ‘see’ cells of both signs. Suddenly, this deduction is ‘fair’ and clearly requires no contradiction.

In Figure A, the solver is free to refrain from labeling r1c1 and simple excude it once r1c5 and r4c1 are fixed. This is always the case. Just as you update your candidates after entering a digit, you could make exclusions as soon they become available and then continue coloring. You never need to label two cells in one group with the same color. However, it's much easier to show it that way when posting a solution.



The distinction between contradition and other types of deduction is arbitrary:


Code: Select all
[12][23]
[13][34]

We could say:

R1c1=1 -> r2c1=3 -> r2c2=4
R1c1=2 -> r1c2=3 -> r2c2=4
Therefore r2c2=4

… and call it a “forcing chain”

Or we could say:

R2c2=3 -> r1c2=2 -> r1c1=1
R2c2=3 -> r2c1=1 -> r1c1=2
Therefore, r2c2<>3

… and call it a “proof by contradiction”


Or we could say:

“That’s an xy-wing -- r2c2 cannot be 3.”



Coloring is not the pattern -- it is an efficient *method* for finding a *pattern*. I don’t see why we would handicap ourselves.
tso
 
Posts: 798
Joined: 22 June 2005

Postby tarek » Mon Mar 13, 2006 1:31 am

ronk wrote:When one of those states causes a contradiction with the rules, that color must always be false.

Is that the type of contradiction you meant?

Yes
tso wrote:The distinction between contradition and other types of deduction is arbitrary

Can I choose what type of deduction I'm using ?

I tend to choose what makes ME happy

Did I say it was Wrong to use that type of colouring ? NO

Did I say it wasn't effecient? NO

I was asked by another member to show him how the elimination was done using colouring.

The way that type of colouring is presented TO ME feels like contradiction elimination, that's why I don't use it. [a personal choice]

tso wrote:Coloring is not the pattern -- it is an efficient *method* for finding a *pattern*. I don’t see why we would handicap ourselves.

Well it doesn't handicap me, too many x-cycle & grouped x-cycle identificatin & elimination techniques are now present that removes the need to use ANY type of colouring, even type 1.

Some people always shop at Tesco, I myself like Waitrose.......:D

Tarek
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

Whoa!

Postby villagegreen » Mon Mar 13, 2006 2:30 am

You guys are nuts! I'm just asking if trying out different numbers hypothetically to see what might be eliminated is trial and error or logic? Can this puzzle be solved without trial and error?
villagegreen
 
Posts: 8
Joined: 10 March 2006

Re: Whoa!

Postby ronk » Mon Mar 13, 2006 5:01 am

villagegreen wrote:I'm just asking if trying out different numbers hypothetically to see what might be eliminated is trial and error or logic?
You answered your own question.

Can this puzzle be solved without trial and error?
Earlier posts indicate the answer is "yes".

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Whoa!

Postby tso » Mon Mar 13, 2006 6:22 am

villagegreen wrote:You guys are nuts! I'm just asking if trying out different numbers hypothetically to see what might be eliminated is trial and error or logic? Can this puzzle be solved without trial and error?


Testy. Especially considering these questions have been asked and answered eleventy six times already in this forum.

Your first question is flawed -- "... is trial and error or logic?" Trial and error *is* logic.

Your second question -- Trial and error is *never* required.

The discussion is largely semantics. There's always someone who thinks nearly *any* tactic beyond their paygrade is trial and error. You've got to be more specific -- "can this puzzle be solved without proof by contradiction?" or "can this be solved without bifurcation" or whatever. (The answer will still always be "yes", but at least then someone will be able to proceed to do so.)

That said, this particular puzzle was one of the simplest to be posted with this question.
tso
 
Posts: 798
Joined: 22 June 2005

Postby ravel » Mon Mar 13, 2006 10:23 am

Like tso already denoted, for every elimination by contradiction there exists one without. E.g. in the sample above, an elimination
r1c1=8 => r4c1<>8 => r6c3=8 => r6c5<>8 => r1c5=8 => r1c1<>8
can be done with a forcing chain
r4c1=8 => r1c1<>8
r4c1<>8 => r6c3=8 => r6c5<>8 => r1c5=8 => r1c1<>8

So i cannot see anything ugly at elimination by contradiction, because it is often the more elegant way.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Mon Mar 13, 2006 11:53 am

ravel wrote:Like tso already denoted, for every elimination by contradiction there exists one without.

Indeed, I see no difference. That elimination, expressed as a nice loop is:

r1c1-8-r4c1=8=r6c3-8-r6c5=8=r1c5-8-r1c1

One of the "properties" of a nice loop is that one can start at any node (cell) and get two implication streams (chains), one right-to-left from that node, and the other left-to-right.

Starting at r4c1, as you did, we get ...
r4c1=8 => r1c1<>8
r4c1<>8 => r6c3=8 => r6c5<>8 => r1c5=8 => r1c1<>8
... which people refer to as a "forcing chain".

Starting at the left end, we still have two implication streams:
r1c1<>8
r1c1=8 -> r4c1<>8 => r6c3=8 => r6c5<>8 => r1c5=8 => r1c1<>8
In this case, most people just omit the first trivial implication "stream", and refer to the second as "elimination by contradiction."

We could start at any one of the other four nodes (including the rightmost r1c1) and obtain four other pairs of implication streams. And three of these would be "forcing chains" and one more (starting from the rightmost node) would be "elimination by contradiction."

Hmm. One nice loop, but two different names for the deduction? As I wrote at the opening, I see no difference.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Whoa!

Postby villagegreen » Tue Mar 14, 2006 5:03 pm

tso wrote:
villagegreen wrote:You guys are nuts! I'm just asking if trying out different numbers hypothetically to see what might be eliminated is trial and error or logic? Can this puzzle be solved without trial and error?


Testy. Especially considering these questions have been asked and answered eleventy six times already in this forum.

Your first question is flawed -- "... is trial and error or logic?" Trial and error *is* logic.

Your second question -- Trial and error is *never* required.

The discussion is largely semantics. There's always someone who thinks nearly *any* tactic beyond their paygrade is trial and error. You've got to be more specific -- "can this puzzle be solved without proof by contradiction?" or "can this be solved without bifurcation" or whatever. (The answer will still always be "yes", but at least then someone will be able to proceed to do so.)

That said, this particular puzzle was one of the simplest to be posted with this question.


Sorry, I didn't mean to come off as testy. It's just that I'm not even at square one in terms of the lingo being employed in here. But your point is well taken. I suppose proof by contradiction or bifurcation is as "logical" as anything else, but it just doesn't seem right or fun to me to be plugging in numbers to see what "would" happen.
villagegreen
 
Posts: 8
Joined: 10 March 2006

Re: Whoa!

Postby gsf » Tue Mar 14, 2006 11:08 pm

villagegreen wrote:Sorry, I didn't mean to come off as testy. It's just that I'm not even at square one in terms of the lingo being employed in here. But your point is well taken. I suppose proof by contradiction or bifurcation is as "logical" as anything else, but it just doesn't seem right or fun to me to be plugging in numbers to see what "would" happen.

I sympathize with villagegreen here
saying "this forcing chain solves this puzzle" is like presenting a fish instead of teaching to fish
i.e., given a puzzle where you believe or have been told that forcing chains will solve it,
where do you start?
what cells, what candidates, how deep before trying another chain

getting some fun out of forcing chains means being able to do use it with success on the next puzzle
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Whoa!

Postby tso » Tue Mar 14, 2006 11:57 pm

gsf wrote:
villagegreen wrote:Sorry, I didn't mean to come off as testy. It's just that I'm not even at square one in terms of the lingo being employed in here. But your point is well taken. I suppose proof by contradiction or bifurcation is as "logical" as anything else, but it just doesn't seem right or fun to me to be plugging in numbers to see what "would" happen.

I sympathize with villagegreen here
saying "this forcing chain solves this puzzle" is like presenting a fish instead of teaching to fish
i.e., given a puzzle where you believe or have been told that forcing chains will solve it,
where do you start?
what cells, what candidates, how deep before trying another chain getting some fun out of forcing chains means being able to do use it with success on the next puzzle


Again, the problem is confusing the methods for finding patterns with the patterns themselves. "What cell do you start to look for a forcing chain?" is no more or less meaningful than "What cell do you start to look for a Swordfish?" Or a naked triple. Or even a hidden single! How do you know where to look for anything, anywhere under any circumstances? Use your senses and filter through your judgement along with your creativity. As the patterns get more complex, the complexity and the variety of methods to find them increase -- as well as the difficulty of spelling them out with ascii -- but many of these methods HAVE been spelled out many times in these and other forums.

See: this post and this post.

That being said, the way NOT to look for forcing chains is to pick a cell at random, place a number in there and see what it implies. "How far should I go" is a question that has little meaning. When do you stop looking for naked pairs?

It's not unlike the study of geometry -- we learned many facts, but we had to use our own judgement to figure out when to look for what.
tso
 
Posts: 798
Joined: 22 June 2005

Re: Whoa!

Postby gsf » Thu Mar 16, 2006 8:25 am

tso wrote:Again, the problem is confusing the methods for finding patterns with the patterns themselves. "What cell do you start to look for a forcing chain?" is no more or less meaningful than "What cell do you start to look for a Swordfish?" Or a naked triple. Or even a hidden single! How do you know where to look for anything, anywhere under any circumstances? Use your senses and filter through your judgement along with your creativity. As the patterns get more complex, the complexity and the variety of methods to find them increase -- as well as the difficulty of spelling them out with ascii -- but many of these methods HAVE been spelled out many times in these and other forums.

See: this post and this post.


There is a difference between looking for patterns like row/col/box based naked/hidden tuples
or rectangular area based xwing/swordfish versus serpentine forcing chains.

The urls cleared up one thing -- I had lumped "forcing chain" and "forcing net" into one category.

I based my comments on posted puzzle solutions that seem to grab
forcing chains, sometimes very long, from thin air.
Solving by hand, such long chains would be a big time investment,
especially since there's no guarantee that a particular chain will result
in any placements or eliminations.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Myth Jellies » Thu Mar 16, 2006 9:08 am

Terek, if you don't like that particular coloring rule, you might note that prior to getting there, you will have something like this situation...

Code: Select all
*-----------------------------------------------*
|-8    .   .    | .   *8    .   | 8    .    .   |
| .    8   .    | .    .    .   | .    .    8   |
| .    8   .    | .    .   +8   | 8    .    .   |
|---------------+---------------+---------------|
|+8    .    .   | .    .   -8   | .    .    .   |
| .    .    .   | .    .    .   | 8    .    8   |
| .    .   -8   | .    8    .   | .    .    .   |
|---------------+---------------+---------------|
| .    8    8   | .    .    .   | .    8    .   |
| .    .    .   | 8    .    .   | .    .    .   |
| .    .    8   | .    .    .   | .    8    .   |
*-----------------------------------------------*

...The starred 8 sees both a + and a - and so can be eliminated. Since that leaves singles in box 2 and column 5, you can make the rest of the eliminations that the other coloring rule would make. I think you can always avoid that rule you don't like and do this instead.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tarek » Thu Mar 16, 2006 9:45 am

Myth Jellies wrote:...The starred 8 sees both a + and a - and so can be eliminated. Since that leaves singles in box 2 and column 5, you can make the rest of the eliminations that the other coloring rule would make. I think you can always avoid that rule you don't like and do this instead.

This may sound silly, but what you suggested is actually what I would do. I know that at the end the same result & probably the same logic is applied as the contradiction elimination method........but I prefer to use alternative methods, these alternatives happen to be also very good....

& by the way the way Myth Jellies, I'm sure that you would agree that this may constitute an alternative:D .....
Code: Select all
*-----------------------------------------------*
|*458  9    1   | 7   -58  *6   | 458  3    2   |
| 6    58   2   | 4    1    3   | 7    9    58  |
| 3    458  7   | 9    2   #58  | 458  1    6   |
|---------------+---------------+---------------|
|*58   3    4   | 2    7   *58  | 1    6    9   |
| 2    6    9   | 1    3    4   | 58   7    58  |
| 1    7    58  | 6    58   9   | 3    2    4   |
|---------------+---------------+---------------|
| 9    458  568 | 3    46   7   | 2    458  1   |
| 45   2    3   | 8    9    1   | 6    45   7   |
| 7    1    68  | 5    46   2   | 9    48   3   |
*-----------------------------------------------*
Eliminating 8 From r1c5 (Finned XWing in Columns 16)
:D
Tarek
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

PreviousNext

Return to Help with puzzles and solving techniques