The New Sudoku Players' Forum

[Jeff]

I have now solved the grid posted above by Jeff. I have used a total of 26 chains: 20 simple nice loops, 3 loops having an extended disjoint subset link (as defined by Rubylips), 2 weak nice loops, and 1 strong nice loop. Does anyone have come also to a solution? I would like to compare different solutions.

Well done, Carcul. You would have solved what has been reckoned as the third toughest grid in this forum. I have just started a new thread to collectively capture all logical solutions for this grid. Could you list your solution under the new thread preferably in 2 parts; separated by the following candidate grid. Thanks.

Code: Select all

 *-----------------------------------------------------------------------------*
 | 56      56      2       | 38      9       34      | 1       48      7       |
 | 179     3       8       | 6       2457    12      | 245     59      259     |
 | 4       179     17      | 12578   2578    128     | 2568    35689   23568   |
 |-------------------------+-------------------------+-------------------------|
 | 1236    12678   47      | 39      2678    5       | 246     16789   12689   |
 | 256     245678  9       | 278     1       268     | 3       45678   258     |
 | 123567  125678  1357    | 4       2678    39      | 2568    156789  125689  |
 |-------------------------+-------------------------+-------------------------|
 | 12579   12579   1357    | 125     2568    1268    | 68      368     4       |
 | 135     15      1345    | 158     4568    7       | 9       2       368     |
 | 8       24      6       | 29      3       49      | 7       15      15      |
 *-----------------------------------------------------------------------------*


[Jeff]

I had thought that "only strong links" would produce the same result as the bilocation/bivalue techniques, but obviously weak links are required too. I haven't a clue why.

The bilocation/bivalue technique, simple nice loops in particular, is equivalent to advanced colouring and I think 3D-Medusa as well, for identification of double implication chains. The bilocation/bivalue technique can also be extended to identify grouped nice loops and multiple nice loops; which are literally poly-implication chains. These nice loops comprise bilocation links and bivalue links.

[ronk]

Well done, Carcul. You would have solved what has been reckoned as the third toughest grid in this forum.

Considering that my solver only uses four T&E eliminations, I find that surprising. On each iteration it merely eliminates the first candidate for which a contradiction is found ... so it must be stumbling upon a magic candidate.

[Jeff]

By the way, adding the new "almost-locked" option solves this puzzle directly.

Well done, Bob. I have just started a new thread "The third toughest puzzle" to collectively capture all logical solutions for this puzzle. Could you list your solution under this thread. Thanks.

[Jeff]

Considering that my solver only uses four T&E eliminations, I find that surprising. On each iteration it merely eliminates the first candidate for which a contradiction is found ... so it must be stumbling upon a magic candidate.

Interestingly, although being named the third toughest puzzle in logical sense, T&E can be quite easy if a magic candidate is selected.

Try 4 at r8c3 and the entire puzzle is solved:

{5} {6} {2} {8} {9} {3} {1} {4} {7}
{7} {3} {8} {6} {4} {1} {5} {9} {2}
{4} {9} {1} {7} {5} {2} {6} {8} {3}
{2} {8} {7} {3} {6} {5} {4} {1} {9}
{6} {4} {9} {2} {1} {8} {3} {7} {5}
{1} {5} {3} {4} {7} {9} {2} {6} {8}
{9} {7} {5} {1} {2} {6} {8} {3} {4}
{3} {1} {4} {5} {8} {7} {9} {2} {6}
{8} {2} {6} {9} {3} {4} {7} {5} {1}

[Bob Hanson]

It shows 7 eliminations only ...

r9c2 ISN'T 9: weak corner eliminated by both 2(b) and 2(B)--4(D)
........
r9c2 ISN'T 9: weak corner eliminated by both 4(D) and 4(d)--2(b)
r7c1 ISN'T 3: weak corner eliminated by both 4(D) and 4(d)--16(p)
........
r7c1 ISN'T 3: weak corner eliminated by both 16(p) and 16(P)--4(D)

I hadn't noticed the duplications. Apparently, some eliminations may be made by following any one of several chains. IMO it would nicer if the Medusa only logged one of them. [edit: A revisit of the site shows Bob has already done exactly that.]

I had thought that "only strong links" would produce the same result as the bilocation/bivalue techniques, but obviously weak links are required too. I haven't a clue why.

Right, the thing is, there are often several different ways a possibility
could be eliminated. So I thought it would be better to show them all
rather than to show just the first.

I'm pretty sure the bivalue/bilocation business takes into consideration
weak links. You can see from

r7c1 ISN'T 3: weak corner eliminated by both 4(D) and 4(d)--16(p)

that, for example, there must be a weak connection between one of the
4(d) chain nodes and a 16(P) node -- both in the same row, for example,
but not JUST the two of them. So a TRUE for 4(d) carries over to a FALSE
for 16(P) -- or a TRUE, then, for 16(p). Apparently r7c1#3 sees both a
4(D) and a 16(p) node.

The bivalue/bilocation idea does allow for "jumping" from one to another,
I'm sure, so that constitutes the weak link.

I've made the method description just a bit more explicit now:

Ms: 3D Medusa with only a SINGLE strong chain.
Mw: 3D Medusa taking into account multiple chains with weak links.

I'm certain the bivalue/bilocation considerations = Ms+Mw.

By the way, I was very happy to see that the almost-locked sets business
plugged in so nicely. Sudoku Assistant now can "connect the dots" and
reat an almost-locked set almost like a bivalue/bilocation pair.

Code: Select all

bivalue chain "edge" transmits weak link

   X*.....X-----Y.....Y*
                :
                :
                Y*


X* TRUE forces Y TRUE, so all weak link Y* FALSE.

Code: Select all

almost-locked set does the same

   X*.....X--A--Y.....Y*
             |
             Z....Z*


X* TRUE forces Y and Z both TRUE, so all weak link Y* and Z* FALSE.

The cool thing is that if X* is part of a bivalue/bilocation pair,
and Y* or Z* is also, then we have a new weak link between
chains. THIS is what then allows for advancement of the solution.

I've put "a" in the method description means that we have some sort of
almost-locked set that plugs in this way. It gets picked up in the
strong chain analysis.

"A" in the method description means we have the equivalent of
a weak corner for a chain:

Code: Select all

bivalue chain "edge" with weak corner, which can be eliminated
 
             X-----X
              .   . 
               . .
                X*

X-type almost-locked set with weak corner, which can be eliminated

   X---A--X"
   :   |
   X*..X'


or, possibly (and it turns out, pretty commonly):

Code: Select all

mutually linked almost-locked sets

       X...X
      /     \
  W--A       B--Z...Z*
  :   \     /
  W*   Y...Y


I especially like this one. ANY additional links W*, Z* can be
eliminated. (Because one of X and one of Y MUST be false, so
all the others have to be TRUE!)

These are found earlier, as part of the subset elimination/grid check.

[gsf]

Considering that my solver only uses four T&E eliminations, I find that surprising. On each iteration it merely eliminates the first candidate for which a contradiction is found ... so it must be stumbling upon a magic candidate.

Interestingly, although being named the third toughest puzzle in logical sense, T&E can be quite easy if a magic candidate is selected.

this puzzles has 25 magic cells (also known as backdoor solutions in the SAT literature):

Code: Select all

[1,4]=8[1,6]=3[1,8]=4[2,5]=4[2,7]=5[3,4]=7[4,3]=7[4,4]=3[4,7]=4
[4,9]=9[5,2]=4[5,4]=2[5,8]=7[6,3]=3[6,5]=7[6,6]=9[7,2]=7[7,3]=5
[7,5]=2[8,3]=4[8,4]=5[8,5]=8[9,2]=2[9,4]=9[9,6]=4


there is only one magic cell [8,5]=8 using the simplest constraints
(F: forced cell value, N: only value possible in row/col/box)

[Jeff]

this puzzles has 25 magic cells (also known as backdoor solutions in the SAT literature):

Code: Select all

[1,4]=8[1,6]=3[1,8]=4[2,5]=4[2,7]=5[3,4]=7[4,3]=7[4,4]=3[4,7]=4
[4,9]=9[5,2]=4[5,4]=2[5,8]=7[6,3]=3[6,5]=7[6,6]=9[7,2]=7[7,3]=5
[7,5]=2[8,3]=4[8,4]=5[8,5]=8[9,2]=2[9,4]=9[9,6]=4


there is only one magic cell [8,5]=8 using the simplest constraints
(F: forced cell value, N: only value possible in row/col/box)

How were these magic cells identified? A software?

[gsf]

this puzzles has 25 magic cells (also known as backdoor solutions in the SAT literature):

Code: Select all

[1,4]=8[1,6]=3[1,8]=4[2,5]=4[2,7]=5[3,4]=7[4,3]=7[4,4]=3[4,7]=4
[4,9]=9[5,2]=4[5,4]=2[5,8]=7[6,3]=3[6,5]=7[6,6]=9[7,2]=7[7,3]=5
[7,5]=2[8,3]=4[8,4]=5[8,5]=8[9,2]=2[9,4]=9[9,6]=4


there is only one magic cell [8,5]=8 using the simplest constraints
(F: forced cell value, N: only value possible in row/col/box)

How were these magic cells identified? A software?

yes
solve the puzzle
then go back to the original grid and plug in the answers, cell by cell
the ones that crack the puzzle are magic (backdoors)

this puzzle can be cracked by 1 magic cell (1-constrained)
some 9x9 sudoku have magic cell set size 2 meaning 2 cells together crack the puzzle (2-constrained)
most puzzles are 0-constrained
no 3-constrained or greater 9x9 has been found

[Jeff]

[this puzzle can be cracked by 1 magic cell (1-constrained)
some 9x9 sudoku have magic cell set size 2 meaning 2 cells together crack the puzzle (2-constrained)
most puzzles are 0-constrained
no 3-constrained or greater 9x9 has been found

Good stuff. This gives me an idea. Is there a short cut to find these magic cells before the grid is solved?

[gsf]

[this puzzle can be cracked by 1 magic cell (1-constrained)
some 9x9 sudoku have magic cell set size 2 meaning 2 cells together crack the puzzle (2-constrained)
most puzzles are 0-constrained
no 3-constrained or greater 9x9 has been found

Good stuff. This gives me an idea. Is there a short cut to find these magic cells before the grid is solved?

that's a fertile topic
since most 9x9 sudoku are 0 or 1-constrained you can brute force
by combining a simple logic solver with a one single loop through all cells
and candidate values -- if you're looking for speed that's the way to go,
if you're looking for intuitive logical hints its not

[ronk]

there is only one magic cell [8,5]=8 using the simplest constraints
(F: forced cell value, N: only value possible in row/col/box)

I'm of the impression that the "magic candidate" would be the candidate eliminated causing [8,5]=8, also via the simplest of constraints (naked or hidden single).

Do you concur?

[Ruud]

I'm of the impression that the "magic candidate" would be the candidate eliminated causing [8,5]=8, also via the simplest of constraints (naked or hidden single).

That's an interesting new way of looking at "magic candidates", Ron.

When looking for the optimal solving path, I used the term "magic candidate" for the candidates that forced a complete solution. Since there can be only one per cell, the term "magic cell" is equally valid.

What you're proposing here is that any single candidate that, when eliminated, forces a magic cell to it's solution digit is in itself a "magic candidate". Of course, you will only be able to find such a magic candidate if the magic cell belongs to a size-2 constraint (bivalue/bilocation).

Considering the sheer number of magic cells in this sudoku, it would greatly increase our chance of success, if we look for any candidate that can force one of the known magic cells to its solution. In my experience, only a few eliminations can be made at any time with forward implication chains. When all magic candidates have been found, the one unlocking the optimal "magic cell" can be selected.

Ruud.

[ronk]

I'm of the impression that the "magic candidate" would be the candidate eliminated causing [8,5]=8, also via the simplest of constraints (naked or hidden single).

That's an interesting new way of looking at "magic candidates", Ron.

When looking for the optimal solving path, I used the term "magic candidate" for the candidates that forced a complete solution. Since there can be only one per cell, the term "magic cell" is equally valid.

What you're proposing here is that any single candidate that, when eliminated, forces a magic cell to it's solution digit is in itself a "magic candidate".

Didn't realize I was proposing anything new, since I thought that's what we agreed too here.

[gsf]

there is only one magic cell [8,5]=8 using the simplest constraints
(F: forced cell value, N: only value possible in row/col/box)

I'm of the impression that the "magic candidate" would be the candidate eliminated causing [8,5]=8, also via the simplest of constraints (naked or hidden single).

Do you concur?

in this example clearing one candidate cracks the puzzle
but there may be other examples with magic cells with >2 candidates
"magic cell" as it has been used pertains to the cell that cracks the puzzle,
not the cells eliminated to the point that exposed the magic cell
there would be a similar argument for the magic candidate within a magic cell

here's an FN-1-constrained puzzle with 15 magic cells and >2 candidates in all of them, where the candidates are listed after all FN constraints have been applied (excuse the last 2 candidate col alignment)

Code: Select all

..........6.5.2.1..9..6..2.1..4.6..9..9.3.5..4....9..2....4..5..7.8.5.9..3.....6.

# 15 magic cells
#    [1,3]=1[1,5]=9[1,9]=5[2,3]=8[3,1]=5[3,3]=7[3,4]=1
#    [3,9]=8[5,6]=1[7,3]=2[7,7]=8[8,7]=2[9,1]=8[9,5]=2[9,9]=1

  {23578}   {12458}  {1234578}  {1379}    {1789}    {13478}  {346789}   {3478}  {345678}
   {378}      6       {3478}      5        {789}      2       {34789}     1 {3478}
  {3578}      9      {134578}    {137}      6       {13478}   {3478}      2 {34578}
    1        {258}    {23578}     4       {2578}      6        {378}     {378}  9
  {2678}     {28}       9        {127}      3        {178}      5        {478} {14678}
    4        {58}     {35678}    {17}     {1578}      9       {13678}    {378}  2
  {2689}     {128}    {1268}   {123679}     4        {137}    {12378}     5  {1378}
   {26}       7       {1246}      8        {12}       5       {1234}      9  {134}
  {2589}      3       {12458}   {1279}    {1279}     {17}     {12478}     6  {1478}