The New Sudoku Players' Forum

[tarek]

I thought when I programmed this technique that it was a form of Forcing chains however it turned out to be something else which I don't know know exactly how to describe it.

I would take a poly-valued cell, each candidate of that poly-valued cell is then picked to see what are the implications of it being the actual occupant of that cell.

I use only simple eliminations to study implications (to make it easier for humans), any advanced technique can be used of course.

If another bi- or poly-valued cell turns out to have exactly the same candidates with each candidate from the original cell then we can safely say that the the 2nd cell must have those same candidates (single or poly).

This is not new of course. I just don't know what is its name. There is no Contradiction involved so it shouldn't fit the GENERAL term of T&E.

I'll post the puzzle from which I discovered that I made a mistake in naming the technique. which came from here........

I have also posted this in the Programmers Index....

Code: Select all

 . 5 . | . . 1 | 6 . . 
 3 . 6 | . . 2 | . . . 
 . . 9 | 3 . . | 2 . 4 
-------+-------+------
 . . 4 | 5 3 . | 1 8 2 
 . . . | 8 . 4 | . . . 
 8 . 5 | 1 2 . | 4 . . 
-------+-------+------
 6 . 1 | . . 5 | 3 . . 
 . . . | 6 . . | 9 . 1 
 . . 7 | 2 1 . | . 4 6
*--------------------------------------------------------------------------*
| 247     5       28     | 479     4789    1      | 6       379     3789   |
| 3       1478    6      | 479     45789   2      | 578     1579    5789   |
| 17      178     9      | 3       5678    678    | 2       157     4      |
|------------------------+------------------------+------------------------|
| 79      679     4      | 5       3       679    | 1       8       2      |
| 1279    123679  23     | 8       679     4      | 57      35679   3579   |
| 8       3679    5      | 1       2       679    | 4       3679    379    |
|------------------------+------------------------+------------------------|
| 6       2489    1      | 479     4789    5      | 3       27      78     |
| 245     2348    238    | 6       478     378    | 9       257     1      |
| 59      389     7      | 2       1       389    | 58      4       6      |
*--------------------------------------------------------------------------*
Eliminating 7 From r5c9 (XY wing)
Eliminating 7 From r6c9 (XY wing)
*--------------------------------------------------------------------------*
| 247     5       28     | 479     4789    1      | 6       379     3789   |
| 3       1478    6      | 479     45789   2      | 578     1579    5789   |
| 17      178     9      | 3       5678    678    | 2       157     4      |
|------------------------+------------------------+------------------------|
| 79      679     4      | 5       3       679    | 1       8       2      |
| 1279    123679  23     | 8       679     4      | 57      35679   359    |
| 8       3679    5      | 1       2       679    | 4       3679    39     |
|------------------------+------------------------+------------------------|
| 6       2489    1      | 479     4789    5      | 3       27      78     |
| 245     2348    238    | 6       478     378    | 9       257     1      |
| 59      389     7      | 2       1       389    | 58      4       6      |
*--------------------------------------------------------------------------*
7 in r7c8 would make placing other 7s impossible (Nishio)
*--------------------------------------------------------------------------*
| 247     5       28     | 479     4789    1      | 6       379     3789   |
| 3       1478    6      | 479     45789   2      | 578     1579    5789   |
| 17      178     9      | 3       5678    678    | 2       157     4      |
|------------------------+------------------------+------------------------|
| 79      679     4      | 5       3       679    | 1       8       2      |
| 1279    123679  23     | 8       679     4      | 57      35679   359    |
| 8       3679    5      | 1       2       679    | 4       3679    39     |
|------------------------+------------------------+------------------------|
| 6       489     1      | 479     4789    5      | 3       2       78     |
| 245     2348    238    | 6       478     378    | 9       57      1      |
| 59      389     7      | 2       1       389    | 58      4       6      |
*--------------------------------------------------------------------------*
Any Candidate in r3c8 forces r1c3 to have only 2 as valid Candidates (Forcing Sequence) or Something else ????
Any Candidate in r3c8 forces r3c2 to have only 8 as valid Candidates (Forcing Sequence
Any Candidate in r3c8 forces r3c6 to have only 6 as valid Candidates (Forcing Sequence)
Any Candidate in r3c8 forces r5c3 to have only 3 as valid Candidates (Forcing Sequence)
Any Candidate in r3c8 forces r8c3 to have only 8 as valid Candidates (Forcing Sequence)


[Jeff]

Code: Select all

*--------------------------------------------------------------------------*
| 247     5       28     | 479     4789    1      | 6       379     3789   |
| 3       1478    6      | 479     45789   2      | 578     1579    5789   |
| 17      178     9      | 3       5678    678    | 2       157     4      |
|------------------------+------------------------+------------------------|
| 79      679     4      | 5       3       679    | 1       8       2      |
| 1279    123679  23     | 8       679     4      | 57      35679   359    |
| 8       3679    5      | 1       2       679    | 4       3679    39     |
|------------------------+------------------------+------------------------|
| 6       489     1      | 479     4789    5      | 3       2       78     |
| 245     2348    238    | 6       478     378    | 9       57      1      |
| 59      389     7      | 2       1       389    | 58      4       6      |
*--------------------------------------------------------------------------*
Any Candidate in r3c8 forces r1c3 to have only 2 as valid Candidates (Forcing Sequence) or Something else ????


Hi tarek, Can you list the implication streams for this one?

[Myth Jellies]

There seems to be a huge variation in what people consider T&E.

To my way of thinking, T&E encompasses any method where you arbitrarily assign a possible solution to be true or false, and then see what happens, even in a limited fashion. (A better term might be trial and conclusion.) In general, I wouldn't use such a method in solving a puzzle. However, I might use your method to identify such linkages between cells, and then see if I could come up with a recognizable pattern or rule that always results in those conclusions, like almost locked sets or xy-loops, that I could apply to other puzzles.

There was great discussion on this topic about regarding another limited T&E method (my opinion) called Sherlock.

[tarek]

Code: Select all

*--------------------------------------------------------------------------*
| 247     5       28     | 479     4789    1      | 6       379     3789   |
| 3       1478    6      | 479     45789   2      | 578     1579    5789   |
| 17      178     9      | 3       5678    678    | 2       157     4      |
|------------------------+------------------------+------------------------|
| 79      679     4      | 5       3       679    | 1       8       2      |
| 1279    123679  23     | 8       679     4      | 57      35679   359    |
| 8       3679    5      | 1       2       679    | 4       3679    39     |
|------------------------+------------------------+------------------------|
| 6       489     1      | 479     4789    5      | 3       2       78     |
| 245     2348    238    | 6       478     378    | 9       57      1      |
| 59      389     7      | 2       1       389    | 58      4       6      |
*--------------------------------------------------------------------------*
Any Candidate in r3c8 forces r1c3 to have only 2 as valid Candidates (Forcing Sequence) or Something else ????


Hi tarek, Can you list the implication streams for this one?

Hi Jeff,

I think I know where this is going..... but first here are the implications

Code: Select all

implications of r3c8 being 1
*--------------------------------------------------------*
| 4     5     2    | 479   4789  1    | 6     379   89   |
| 3     14    6    | 479   4789  2    | 57    579   589  |
| 7     8     9    | 3     5     6    | 2     1     4    |
|------------------+------------------+------------------|
| 9     6     4    | 5     3     7    | 1     8     2    |
| 12    12    3    | 8     6     4    | 57    579   59   |
| 8     7     5    | 1     2     9    | 4     6     3    |
|------------------+------------------+------------------|
| 6     49    1    | 49    489   5    | 3     2     7    |
| 24    24    8    | 6     47    3    | 9     5     1    |
| 5     39    7    | 2     1     3    | 8     4     6    |
*--------------------------------------------------------*
This leads to a contradiction (r8c6 & r9c6)
which makes the puzzle flawed

Implications of r3c8 being 5 = complete solution

Implications of r3c8 being 7
*-----------------------------------------------*
| 7    5    2   | 49   489  1   | 6    3    89  |
| 3    4    6   | 79   89   2   | 5    1    89  |
| 1    8    9   | 3    5    6   | 2    7    4   |
|---------------+---------------+---------------|
| 9    6    4   | 5    3    7   | 1    8    2   |
| 2    1    3   | 8    6    4   | 7    9    5   |
| 8    7    5   | 1    2    7   | 4    6    3   |
|---------------+---------------+---------------|
| 6    9    1   | 4    48   5   | 3    2    7   |
| 4    2    8   | 6    7    3   | 9    5    1   |
| 5    3    7   | 2    1    9   | 8    4    6   |
*-----------------------------------------------*
This leads to a contradiction
which makes the puzzle flawed


The contradiction exists but I didn't look into that, I just looked at the state of the grid each time & you can see that r1c3 is always 2 with each one.

To my way of thinking, T&E encompasses any method where you arbitrarily assign a possible solution to be true or false, and then see what happens, even in a limited fashion.

Hi MythJellies,

I do understand what you're saying, but the general feeling was that T&E needs a contradiction to establish elimination, Now I'm not going to spark a T&E debate but isn't your statement above implicating Forcing Chains, Colouring of the same thing ???!!!!!

[Jeff]

The contradiction exists but I didn't look into that, I just looked at the state of the grid each time & you can see that r1c3 is always 2 with each one.

In this case, Tarek, it's easy. The name for your technique may be regarded as:

Trifurcation, or
Triple implication forcing net

This technique has been around for some time. Have fun

[tarek]

Thanx Jeff,

Would this technique be valid for solver/helper programs ?

[gsf]

Code: Select all

Any Candidate in r3c8 forces r1c3 to have only 2 as valid Candidates


To my way of thinking, T&E encompasses any method where you arbitrarily assign a possible solution to be true or false, and then see what happens, even in a limited fashion.

I do understand what you're saying, but the general feeling was that T&E needs a contradiction to establish elimination, Now I'm not going to spark a T&E debate but isn't your statement above implicating Forcing Chains, Colouring of the same thing ???!!!!!

how did you know to chose r3c8?
are there other cells you might have picked that would would have made no progress?
after completing 100 puzzles using this method would you do any better on #101 than you did on #1?
isn't it being pedantic to ignore contradictions where all but one candidate fails?
in your example r3c8 must be 5 but this is ignored -- just so the method won't be labeled T&E?

the upshot is that this method is brute force
there are no hints for how a human solver should proceed
(other than to pick a cell with the least # candidates)
in the worst case you have to make lucky random cell guesses to make progress

on the other hand this is a good method for machine solving
with contradictions it is basically a 1 level forward check

only a handful of 9x9 puzzles force more than one forward check on all cells
these (canonicalized) minimal puzzles from the top1465 trip up my solver:

Code: Select all

..3....8.4....9.......621..24..............7....8...53.........6...1.9....57.....
.2...76.....1.......9.6..4...1.3..9..7...18..5.......66..8....4..2.4..5..4...32..
12....6..4....9......3....5..78......6...14...................7....92.....5....38


[Jeff]

Would this technique be valid for solver/helper programs ?

Hi Tarek, That really depends on the purpose of your solver. If you are only interested to get to the final solution, then the answer is yes. If you want to simulate and keep track with human executable non-T&E techniques for analysis purpose, then the answer is no.

Gsf got some good points there too.

[ronk]

these (canonicalized) minimal puzzles from the top1465 trip up my solver:

Code: Select all

..3....8.4....9.......621..24..............7....8...53.........6...1.9....57.....
.2...76.....1.......9.6..4...1.3..9..7...18..5.......66..8....4..2.4..5..4...32..
12....6..4....9......3....5..78......6...14...................7....92.....5....38


I find neither of these in the top1465. Did you canonize them?

[tarek]

hmmmm......

It does make sense. However returning to all previous debates about T&E, it seems that it has to PEDANTIC as there is a fine line seperating T&E & other techniques employed by helper programs. The general feeling is that when there is a contradiction elimination then it is T&E if not then it is NOT.

If the general feeling about this is that it is T&E then I will rank it higher than Nishio just before what I describe as Simple Guessing (You describe it as a 1-forward check). That is because I still intend to post solving method in a forum discussion.

I like the name Forcing implications.

Thanx Jeff & gsf

[Wolfgang]

I find neither of these in the top1465. Did you canonize them?

Numbers 2,77 and 81

[tarek]

Code: Select all

 
..3....8.4....9.......621..24..............7....8...53.........6...1.9....57.....
.2...76.....1.......9.6..4...1.3..9..7...18..5.......66..8....4..2.4..5..4...32..
12....6..4....9......3....5..78......6...14...................7....92.....5....38


All of these 3 puzzles required Complex guessing to solve. with the forcing implications running, the order of difficulty from top to bottom was "2nd puzzle(77),1st puzzle(2),3rd puzzle(81).

these (canonicalized) minimal puzzles

I assume from the rearrangement that you use this to insure that the puzzle at hand is not a rearrangement of another. as all Top Lt boxes in the solutions are the same.

[gsf]

these (canonicalized) minimal puzzles

I assume from the rearrangement that you use this to insure that the puzzle at hand is not a rearrangement of another. as all Top Lt boxes in the solutions are the same.

yes
I swept through ~225M canonical order puzzles and canonicalized the top1465
to eliminate duplicates (because the 225M contain random generated
puzzles along with puzzles scraped from the forums)

the canonical order fixes the top left box to 123/456/789 and then
treats the remaining cells in row/col order as a digit string that is minimal up to isomorphism
(using relabling, chute shuffling, and row/col shuffling within chutes)
fixing the top left box makes the process efficient
the counting algs also fix the top left box

[Myth Jellies]

Myth Jellies wrote:
To my way of thinking, T&E encompasses any method where you arbitrarily assign a possible solution to be true or false, and then see what happens, even in a limited fashion.


Hi MythJellies,

I do understand what you're saying, but the general feeling was that T&E needs a contradiction to establish elimination, Now I'm not going to spark a T&E debate but isn't your statement above implicating Forcing Chains, Colouring of the same thing ???!!!!!

Simple Coloring does not arbitrarily assign either true or false to a candidate or to a color. Instead, it highlights a conjugate relationship between cells (i.e. green equals not blue) and looks to see if one color shows up twice in a group, or if a cell sees both a green and a blue cell.

If you apply Forcing Chains by looking for an ab-cell, which sees bc-cell, ... , which sees a ef-cell, which sees an fa-cell; and then get rid of all the candidate 'a's in cells which see both the ab-cell and the fa-cell; then you have never arbitrarily assigned true or false to any of your candidates. There are some ways of applying or finding Forcing Chains which are not T&E (by my definition) and some ways of applying/finding them which are T&E.

In both Simple Coloring and the Forcing Chain method I described, there is a search for a pattern, but there is no arbitrary assignment followed by an assessment of that guess like in your method. Find out why both your trials lead to the same answer in that other cell and derive a pattern or method from that reason and then you will be on to something.

Don't give up; there's plenty out there to find, yet.

[tarek]

Simple Coloring does not arbitrarily assign either true or false to a candidate or to a color. Instead, it highlights a conjugate relationship between cells (i.e. green equals not blue) and looks to see if one color shows up twice in a group, or if a cell sees both a green and a blue cell.

If you apply Forcing Chains by looking for an ab-cell, which sees bc-cell, ... , which sees a ef-cell, which sees an fa-cell; and then get rid of all the candidate 'a's in cells which see both the ab-cell and the fa-cell

I really DO understand what you are driving at, but I must confess that my feeling is that the use of the word HIGHLIGHTING is just a clever way of saying ASSIGNING. the same is the use of the words LOOK FOR.

Indeed there is a pattern, but what is the math behind the pattern, They all ASSIGN or ASSUME a certain chain of events.

I think that is why, all of the long debates about T&E started & that is why The line which everybody seem to recognise for sure is when there is a contradiction elimination.

What would that meen for the Forcing implications (that is what i call it now ), well it will be in the outer most parts of the nesting sequence, just before Nishio I think

Thanx MythJellies.

Tarek