The New Sudoku Players' Forum

[bennys]

Here what I found

Code: Select all

+----------------------+----------------------+----------------------+
| 56     56     2      |$38     9      348    | 1      348    7      |
| 179    3      8      | 6      2457   12     | 245    59     259    |
| 4      179   ^17     | 123578 2578   1238   |*2568   35689  235689 |
+----------------------+----------------------+----------------------+
| 12367  12678  1347   |$39     2678   5      |*2468   16789  12689  |
| 2567   245678 9      |$278    1      268    | 3      45678  2568   |
| 123567 125678 1357   | 4      2678   39     |*2568   156789 125689 |
+----------------------+----------------------+----------------------+
| 123579 12579 ^1357   | 12589  2568   12689  |*68     368    4      |
|%135   %15    %1345   | 158    4568   7      | 9      2      368    |
| 8      249    6      |$29     3      249    | 7      15     15     |
+----------------------+----------------------+----------------------+

First lets notice that if r1c4=3 then r6c3<>3.(because of r4c4 and r6c6)

A={R8C1,R8C2,R8C3} %
B={R3C7,R4C7,R6C7,R7C7} *
C={R3C3,R7C3} ^
D={R1C4,R4C4,R5C4,R9C4} $

R4C3=4=> both A and B are locked
A locked =>(R7C3=7 and R8C4=8(which mean R1C4=3 and that D is locked) now we get
R6C3=5(because of C and R1C4=3)
and R3C4=5(because of D and the 1 in R3C3)
but that cant be because of B

so we get R4C3<>4 and it solve the puzzle


[Jeff]

Maybe I can rewrite chain 11 in the following way:

Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c1|r8c2|r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

Thanks, Carcul. Why would you keep the link '=8|4='? Should it be just '=8=' such that [r4c3] forces [r8c1|r8c2|r8c3]<>4 and [r8c1|r8c2|r8c3] forces [r8c4]=8. Isn't it just another grouped nice loop?

[Carcul]

Ok Jeff.

I write the link that way because it is easier for me to understand. Also, because the link behaves as it would [r8c4]=8=["phantom cell"]=4=[r8c3]
with the cells r8c1 and r8c2 "playing the role" of the phantom cell. So, if "8" is not in r8c4, then it would be in the phantom cell, and "4" must be in r8c3. I abbreviate the notation above to =8|4=. This might look a little confusing, but it is easier for me to look to the link in this way.
BTW, I think Bennys have found the short way to the magic cell r8c3.

Regards, Carcul

[ronk]

Code: Select all

      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |   2578  2578    28 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3   249 |     7      15      15

Consider the cell r1c4.
When it contains the value 3, the values 2 and 9 in Column 4 must occupy the cells r4c4 and r9c4 in some order.
When it contains the value 8, the value 2 in Box 2 must occupy the cell r3c6.
Whichever value it contains, the cells r2c4 and r3c4 cannot contain the value 2.
- The move r3c4:=2 has been eliminated.

As you well know, that is an example of the interaction of two Conditional Disjoint Subsets that bennys has termed the Almost Locked Set xz rule where ...

Code: Select all

sets   A = {r1c4,r4c4,r4c9} = {2389}   in Col 4
       B = {r3c6} = {28}    in Box 2
values x = 8
       z = 2

... allowing safe elimination of z in the intersection of Box 2 and Col 4, excepting A.

I suggest your word description would better match set theory if it considered the xz cell, and then might read something like ...

Code: Select all

Consider the cell r3c6.
When it contains the value 2, the value 2 in Box 2 occupies r3c6.
When it contains the value 8, the values 2, 3, and 9 must occupy cells r1c4, r4c4, and r4c9 of Column 4 in some order, with the value 2 in Box 2 occupying the cell r3c4.
Whichever value it contains, the cells r2c4 and r3c4 cannot contain the value 2.
- The move r3c4:=2 has been eliminated.

Code: Select all

Consider the chain r9c6~2~r9c4=<9|4>=r9c6.
When the cell r9c6 contains the value 2, it likewise contains the value 4 - a contradiction.
Therefore, the cell r9c6 cannot contain the value 2.
- The move r9c6:=2 has been eliminated.

That is an illegal move that happens to have the correct result ... a happy accident. If that were a legal move, the same principle would work on cells r1c4 and r1c6 to eliminate candidate 3 from r1c6. It doesn't.

I'm sure you can find a replacement move, so congratulations on achieving a logical solution.

[Myth Jellies]

BTW, have you done a POM on this grid. If so, could you post the solution?

I have been working on shortcuts that combine POM with chains and ALS. As you know with chains such as ab-bc-cd-da, the correct solution pattern for 'a' must lie on at least one of the endpoints of the chain. Thus, if you combine the chain logic with POM, you can eliminate POM grid patterns via chains even if the puzzle was too ornery to provide a handy cell containing 'a' to complete the loop between the ab-cell and da-cell. Turns out there are even some limited things you can do with the b and d patterns in that chain as well if they show up in other cells.

A similar POM shortcut applies with the ALS xz rule. If you can find two ALS sets containing z and linked by x, then the valid solution pattern for z must be in those two sets. Thus you may make POM reductions even if there is no handy cell containing z that links to all of the other z-cells in the two sets.

I do POM by hand, so it looks like it will take awhile before I can come up with my own solution for this one. However, once you have a POM merge grid, I believe you can use the equations for all cells used by any non-uniqueness method to come up with at least the same reductions as that other method.

[Jeff]

I write the link that way because it is easier for me to understand. Also, because the link behaves as it would [r8c4]=8=["phantom cell"]=4=[r8c3]
with the cells r8c1 and r8c2 "playing the role" of the phantom cell. So, if "8" is not in r8c4, then it would be in the phantom cell, and "4" must be in r8c3. I abbreviate the notation above to =8|4=. This might look a little confusing, but it is easier for me to look to the link in this way.

Cool, I can see the purpose of the phantom cell. If that is your concern, how about this alternative notation:

Chain 11: [r3c4]-8-[r8c4]-15-[r8c1|r8c2|r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

[Jeff]

Bennys, What more can I say?

Finding a forcing net in this grid is difficult.
Finding a forcing net of such extraordinary length must be doubly difficult.
Finding such a lengthy forcing net and solve the grid with this one single deduction ought to be triply difficult.

Your almost locked set is making all this possible.

[rubylips]

Code: Select all

      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |   2578  2578    28 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3   249 |     7      15      15

Consider the chain r9c6~2~r9c4=<9|4>=r9c6.
When the cell r9c6 contains the value 2, it likewise contains the value 4 - a contradiction.
Therefore, the cell r9c6 cannot contain the value 2.
- The move r9c6:=2 has been eliminated.

That is an illegal move that happens to have the correct result ... a happy accident. If that were a legal move, the same principle would work on cells r1c4 and r1c6 to eliminate candidate 3 from r1c6. It doesn't.

It's legitimate. Check the Almost Locked Set {r3c6,r5c6,r7c6,r9c6} which contains the values {2,4,6,8,9}. The 4 occurs just once while the 9s are restricted to Box 8.

I've realized after a further check that I don't make use of the fact that r9c6 doesn't contain a 2. In fact, the value appears in a candidate grid and even in a chain later in the solution! This error crept in as I edited extracts from my solver log.

I'm sure you can find a replacement move, so congratulations on achieving a logical solution.

Thanks. I'm sure, however, that 'human' solvers such as bennys and Carcul deserve far greater praise.

[rubylips]

It requires (besides the obvious singles):
3 Forward implication chains (heavy ammo)

Ruud,

Would it be possible to list these chains? I imagine you must have used tables to build them. That's fine, of course, but I've stuck to traditional chains in order to allow a direct comparison with Carcul. Furthermore, it's hard to generate a fair chain count if tables are used, because the chains that are finally quoted will involve inferences drawn from other chains.

[rubylips]

Why would you keep the link '=8|4='?

I appreciate that the notation I've introduced for the new link types is unhelpful because it fails to highlight the Almost Locked Set that has been employed. I'll take the comments of Jeff and ronk on board and come up with something better ...

[rubylips]

Code: Select all

Consider the cell r1c4.
When it contains the value 3, the values 2 and 9 in Column 4 must occupy the cells r4c4 and r9c4 in some order.
When it contains the value 8, the value 2 in Box 2 must occupy the cell r3c6.
Whichever value it contains, the cells r2c4 and r3c4 cannot contain the value 2.
- The move r3c4:=2 has been eliminated.

As you well know, that is an example of the interaction of two Conditional Disjoint Subsets that bennys has termed the Almost Locked Set xz rule where ...

Code: Select all

sets   A = {r1c4,r4c4,r4c9} = {2389}   in Col 4
       B = {r3c6} = {28}    in Box 2
values x = 8
       z = 2

... allowing safe elimination of z in the intersection of Box 2 and Col 4, excepting A.

I think both ways adequately describe the underlying logic. I see the construction as a line/box interaction, so I find it natural to isolate the three distinct sets Column 4 <intersect> Box 2, Column 4 \ Box 2 and Box 2 \ Column 4, i.e. I don't find it natural to put r1c4 in A but not B. However, I don't have a problem with people who do. I don't see it as a big issue.

I suggest your word description would better match set theory.

Your alternative is quite possible superior but I'm unlikely to implement it because, as far as I'm concerned, the strategy has been superseded and I'm unlikely to quote its results much longer.

Thank-you for your comments.

[ronk]

Consider the chain r9c6~2~r9c4=<9|4>=r9c6.

That is an illegal move that happens to have the correct result ... a happy accident. If that were a legal move, the same principle would work on cells r1c4 and r1c6 to eliminate candidate 3 from r1c6. It doesn't.

It's legitimate. Check the Almost Locked Set {r3c6,r5c6,r7c6,r9c6} which contains the values {2,4,6,8,9}. The 4 occurs just once while the 9s are restricted to Box 8.

Right you are, but equation syntax that doesn't communicate the Almost Locked Sets being using is flawed IMO. In this case, the fundamental reason is the extended link is in two houses ... row 9 and col 6.

My current opinion is ...
1) any link not restricted to one house (row, col, box) ought to be deep-sixed, especially if it involves Almost Locked Sets, and
2) any link that is not symmetric ought to be deep-sixed. Otherwise, it's just too confusing.

From my point of view, the notation of equations is meant to be a shorthand replacement for a wordy description. But an incomplete or ambiguous equation is next to useless.

As to the particular Almost Locked Set(s) under discussion, I don't see why r9c4 is involved at all. [edit: Dumb, dumb statement, of course r9c4 is involved. It's an application of bennys' almost locked set xz-rule.

Code: Select all

      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |   2578  2578    28*|  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268*|     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689*|    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29#    3   249 |     7      15      15

   A = {r3c6,r5c6,r7c6} = {2689}
   B = {r9c4} = {29}
   where x = 9 and z = 2, therefore r9c6<>2

end of edit]

[QBasicMac]

at least two logical solutions have been found

There is only one solution, so I guess you mean at last two ways to get there.

Two? There must be at least 20 along these lines:

if r9c9=5 then puzzle is invalid
therefore r9c9=1

if r9c6=2 then puzzle is invalid
if r9c6=9 then puzzle is invalid
therefore r9c6=4

if r8c9=8 then puzzle is invalid
therefore r8c9=6

Puzzle solved

Mac

[stuartn]

No messin' about QB.... a good point.

Stuartn

[Bob Hanson]

However, could you tell us how many deductions were made from 3D-medusa and how many from almost locked set? I know that both techniques can be executed manually.

Hmm. Probably not. But I think it's safe to say that just about ALL of these were made possible ONLY by adding almost-locked sets. I'm pretty sure the solution choked without ALS.

Without ALS, the solver had to start hypothesizing "Cell X is N" and see where it leads. That's what I call "hypothesis and disproof" but is really just trial and error. This was successful in this case, too, but less fulfilling.

I'm not sure what makes this puzzle the "third hardest." Plenty of the top95 puzzles require what I call "Proof++" whcih means you have to go all the way through the next cycle of subset elimination or at least locked candidates to progress. That to me sounds WAY more difficult.