The New Sudoku Players' Forum

[nj3h]

I am curious where the line is between Forcing Chains and Trial and Error.

Last night I was working a puzzle. I started a chain at a cell with two candidates. After about 6 steps, I ended up with the same value in the same row. Obviously, my inital choice was incorrect.

Then I went back to the original cell and started with the other candidate. After 3 steps, I had found a cell with the same value as my first chain.

Now my question is this: The first chain yielded a solution that was incorrect. If I stopped when that chain failed and then used the other value in my chain starting cell, is that considered trial and error?

What I did was to use the value in the cell that yielded the same value in both chains (step 3 as mentioned above). I believe that this is the correct usage of the Forcing Chain technique.

I would appreciate any feedback on this situation desribed above.

Regards,
George

[sweetbix]

I think this is right. You take each value in a cell and proceed until they all give the same value in another cell then that value must be correct.

Also sometimes you take one value and if you reach a contradiction then that value was wrong. I think the contradiction goes back to the starting value eg if you start out r1c1=1 and the chain ends up r1c1=9 then you know r1c1 does not equal 1.

I think it's more like guessing if you just try one value until you reach a dead end. You either have to have two or more values ending up the same or one value looping back to itself.

[tso]

The line between forcing chains and trial and error is the same one that separates apples and grocery shopping.

Forcing chains are a pattern, as are naked singles, x-wings, etc.

Trial and error is a method of finding patterns.

One never need use trial and error to find a forcing chain -- though it may be faster and/or easier sometimes.

[sweetbix]

Are you saying that you can see the forcing chain as a pattern straight off, the same as Xwing? I have to go through it step by step and this seems like trial and error unlike Xwing where I can see the implications without checking every step.

[tso]

Are you saying that you can see the forcing chain as a pattern straight off, the same as Xwing? I have to go through it step by step and this seems like trial and error unlike Xwing where I can see the implications without checking every step.

It doesn't matter if the individual solver -- carbon or silicon based -- can see the pattern instantly or must search for it by her/his/its favorite method. A novice might require trial and error to locate and x-wing and prove to herself that it does what we claim it does.

If you find a xy-type forcing chain by drawing lines between the bivalue cells and labeling them, then looking for a closed loop that has a single repetion of lables, you can make the exclusion not only without using a method anything like trial and error. You don't even have to know *why* this method works. One doesn't have to trace back every step to the basic axioms in order to do calculus.

Here's an example:

Code: Select all

 3 . 1 | 9 7 2 | 4 . 8
 . 9 . | 1 8 . | . 3 7
 8 . 7 | 5 3 . | 2 9 1
-------+-------+------
 9 2 5 | 4 1 8 | 3 7 6
 4 7 3 | 6 2 9 | 8 1 5
 6 1 8 | 3 5 7 | 9 2 4
-------+-------+------
 1 8 . | 7 9 3 | . . 2
 7 3 . | . 4 5 | 1 . 9
 . . 9 | . 6 1 | 7 . 3

Code: Select all

 
 *--------------------------------------------------*
 | 3   [56]  1    | 9    7    2    | 4   [56]  8    |
 | 25   9    24   | 1    8    46   | 56   3    7    |
 | 8    46   7    | 5    3    46   | 2    9    1    |
 |----------------+----------------+----------------|
 | 9    2    5    | 4    1    8    | 3    7    6    |
 | 4    7    3    | 6    2    9    | 8    1    5    |
 | 6    1    8    | 3    5    7    | 9    2    4    |
 |----------------+----------------+----------------|
 | 1    8    46   | 7    9    3    | 56   456  2    |
 | 7    3    26   | 28   4    5    | 1   [68]  9    |
 | 25  [45]  9    | 28   6    1    | 7   [48]  3    |
 *--------------------------------------------------*

At this point, there are (at least) two clear choices.

[EDIT: typo corrected in bold]

(I) There is an xy-type forcing chain aka "nice loop" in the 5 cells marked in brackets. Either value of r9c2 forces r1c2=6.

If you merely searched for all possible xy-type forcing chains they way you'd search for x-wings, your search would be longer and more tedious -- but it would only be different by degree, not by quality. A search is a search.

However, this loop can also be found by drawing labeled edges between all bivalue cells. Then, the search is *shorter* than one for an x-wing, as there are only a few loops to check -- and knowing that at least one edge of the loop must join two cells in either row 7, column 8 or box 9 (because these three groups contain the last tri-value cell) shortens the search to a few seconds. Often, knowing where to look can allow you to do it in your head without drawing lines in simpler puzzles like this one once you get the hang of it. There are those of us who feel this is one of the most enjoyable parts of solving a Sudoku. I no longer think in terms of "all values of cell x lead to cell y=z", but instead just look at the labels. Starting from r9c2 and traveling counterclockwise:

[45]---(4)---[48]---(8)---[68]---(6)---[56]---(5 or 6, your choice)---[56]---(5)---[45]

The consecutive (6)s eliminate a 6 from r1c8.
The consecutive (5)s eliminate a 5 from r1c2.

I no longer have to remember why I can make the exclusion or convert it into a pair of "if this, then this" implication chains.


(II) Look at r7c8 in the candidate diagram. It is the only cell that has three possible values. This means you can solve this in one fell swoop using BUG avoidance. [EDIT: switched to more appropriate link]

All you need to know is:

-- All but one of the undecided cells have exactly two candidates.
-- One undecided cell has exactly three candidates.
-- Therefore, the candidate that appears exactly three times in the row, column and box containing the tri-value cell must be placed in the tri-value cell.

Now, very little in the way of *search* is required to recognize the existance of a BUG -- nothing that could be labeled as trial and error. But at the same time, I would be hard pressed to be able to follow all of the implications. I just know it works. This pattern is just easier to recognize that an odd shaped 5 cell forcing chain. Different by degree, not quality.

[sweetbix]

A novice might require trial and error to locate and x-wing ...

... this loop can also be found by drawing labeled edges between all bivalue cells. Then, the search is *shorter* than one for an x-wing, as there are only a few loops to check

At one end of the scale the novice is searching to locate the Xwing and at the other you are searching for the labelled edges. If a "search is a search" then isn't it all some kind of trial and error whether it's a simple technique or an advanced one?

Can anyone actually define trial and error? If it's a method then won't it have definable steps?

[Jeff]

If a "search is a search" then isn't it all some kind of trial and error whether it's a simple technique or an advanced one?

Can anyone actually define trial and error? If it's a method then won't it have definable steps?

Some people might argue that everything done in solving Sudoku is some form of "packaged" Trial and Error. This would be the extreme case but true; simply because everyone has his/er own standard and definition of T&E. It is therefore important that we keep an open mind during the discussion of this issue.

This is my definition of T&E:

'Trial' means testing each possibility in turn, and
'Error' means backtracking when a contradiction is identified.

A T&E process has no definable steps and patterns to be recognised with, such that the 'search' is aimless and some kind of proof is performed during the process. For example, candidates in a cell could be tested in turns until a contradiction is identified.

A non-T&E process has definable steps and the 'search' would be in the form of pattern recognition without a need to perform any proof at all since the logic has already been understood. The definable steps would include steps to establish such patterns, eg.a BUG or nice loops, so that a targeted 'search' can be carried out.

[ronk]

... at least one edge of the loop must join two cells in either row 7, column 8 or box 9 (because these three groups contain the last tri-value cell) ...

Do you know where that "rule of thumb" is discussed?

There is an xy-type forcing chain aka "nice loop" in the 5 cells marked in brackets. Either value of r9c2 forces r1c2=5.

Assuming you meant r1c2<>5.

[Carcul]

Code: Select all

There is an xy-type forcing chain aka "nice loop" in the 5 cells marked in brackets. Either value of r9c2 forces r1c2=5.

The pure bivalue nice loop of Tso implies r1c8<>6, and therefore r1c2<>5.

Regards, Carcul

[stuartn]

There is an xy-type forcing chain aka "nice loop" in the 5 cells marked in brackets. Either value of r9c2 forces r1c2=5.

Tso - no it doesn't. What did you really mean?

stuartn

[Lardarse]

Code: Select all

 3 . 1 | 9 7 2 | 4 . 8
 . 9 . | 1 8 . | . 3 7
 8 . 7 | 5 3 . | 2 9 1
-------+-------+------
 9 2 5 | 4 1 8 | 3 7 6
 4 7 3 | 6 2 9 | 8 1 5
 6 1 8 | 3 5 7 | 9 2 4
-------+-------+------
 1 8 . | 7 9 3 | . . 2
 7 3 . | . 4 5 | 1 . 9
 . . 9 | . 6 1 | 7 . 3

Code: Select all

 
 *--------------------------------------------------*
 | 3   [56]  1    | 9    7    2    | 4   [56]  8    |
 | 25   9    24   | 1    8    46   | 56   3    7    |
 | 8    46   7    | 5    3    46   | 2    9    1    |
 |----------------+----------------+----------------|
 | 9    2    5    | 4    1    8    | 3    7    6    |
 | 4    7    3    | 6    2    9    | 8    1    5    |
 | 6    1    8    | 3    5    7    | 9    2    4    |
 |----------------+----------------+----------------|
 | 1    8    46   | 7    9    3    | 56   456  2    |
 | 7    3    26   | 28   4    5    | 1   [68]  9    |
 | 25  [45]  9    | 28   6    1    | 7   [48]  3    |
 *--------------------------------------------------*

(II) Look at r7c8 in the candidate diagram. It is the only cell that has three possible values. This means you can solve this in one fell swoop using BUG avoidance.

All you need to know is:

-- All but one of the undecided cells have exactly two candidates.
-- One undecided cell has exactly three candidates.
-- Therefore, the candidate that appears exactly three times in the row, column and box containing the tri-value cell must be placed in the tri-value cell.

I'll let you explain that one to me somewhere else...

The obvious thing that I spot here is that r1c8=r7c7 (law of leftovers). Of course it wo't help you to solve the puzzle...

[tso]

... at least one edge of the loop must join two cells in either row 7, column 8 or box 9 (because these three groups contain the last tri-value cell) ...

Do you know where that "rule of thumb" is discussed?

No. It *might* have hinted at it some time ago when discussing the mostly obsolete *binary groups* method of finding xy-type chains.

A binary group the set of edges connecting a number of bivalue cells in a row, column or box that can exist in only two states, such as [12][12] or [12][23][34][14]. If a closed path is formed in which each edge is part of a binary group, the entire loop is a binary group, within which no contradiction can occur. The entire structure can exist in two states. It will be of no help to move the puzzle forward other than identifying which connections. (It does form a nice loop -- the non-repetitive type -- but since each edge is already a binary group, no exclusions will result.) At least one edge must therefore must connect two cells in a row, column or box that has at least one tri-value or greater cell.

There is an xy-type forcing chain aka "nice loop" in the 5 cells marked in brackets. Either value of r9c2 forces r1c2=5.

Assuming you meant r1c2<>5.

I corrected the mistake. I have *got* to stop making so many tyops.

[sweetbix]

My understanding of the nice loop was that you could eliminate the candidate that intersected with 2 cells in which it was also a candidate.

Can you explain how 4 is eliminated at r1c2 between 45 - 56. Thanks.

[Jeff]

My understanding of the nice loop was that you could eliminate the candidate that intersected with 2 cells in which it was also a candidate.

Hi Sweetbix, Just would like to clarify that your statement is true for xy-type (bivalue) of nice loops . There are other types of nice loops that can:

1) eliminate a candidate that intersected with 2 cells in which only one of them has the same candidate.
2) fix a digit into a cell.

[sweetbix]

Thanks Jeff, is this a bivalue nice loop?