Help with a proof?

Advanced methods and approaches for solving Sudoku puzzles

Help with a proof?

Postby Sudtyro2 » Tue Nov 26, 2013 9:40 pm

Some empirical observations regarding properties of eventual-elimination (EE) cells in single-digit grids were summarized on the arcilla thread in a posting
here.

A number of example grids were cited in that post (in hidden text) all having the property that they contained one or more row/column-based conjugate pairs (box-based pairs don't apply). It was then also noted in all of those grids that each EE cell was always a peer of at least one of the conjugate-pair candidates in that grid.

A more recent review of additional sample grids in the UFG and elsewhere has revealed the same property, including some grids having multiple EE cells, such as the grid below from Obi-Wahn's arithmetic post. The conjugate pairs of interest here are r12c1 and r17c8:
Code: Select all
 
 2  .  . |  .  . -2 |  . *2  2
 2  .  . |  2 -2  . |  .  .  2
 .  .  . |  . *2 *2 | *2  .  .
---------+----------+----------
 .  .  . |  .  . *2 | #2  .  .
 .  .  2 |  2  .  . |  2  .  .
 .  .  2 |  2  .  . |  .  .  2
---------+----------+----------
 .  .  . |  2  .  . | -2 *2  .
 .  .  . |  . *2 *2 | *2  . *2
 .  .  . |  .  .  . |  .  .  .
 jellyfish r348c8\c56b39 plus remote fin r4c7, implies r1c6<>2, r2c5<>2 and r7c7<>2

Even with all these examples, a proof seems elusive, at least for me! :(

Any takers?
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby StrmCkr » Sat Nov 30, 2013 8:27 am

Finned X-Wing: 2 r34 c67 fr3c5 => r1c6<>2
Finned Swordfish: 2 r348 c567 fr8c9 => r7c7<>2
Finned Mutant Squirmbag: 2 r34c148 r127c7b5 fr3c5 fr3c6 => r1c6,r2c5<>2
Finned Mutant Squirmbag: 2 r348c18 r12c67b9 fr3c5 fr8c5 => r2c5<>2

for the above grid the above mutiple fish accounts for all the elimination however it can also be replicated in one move without using remote fins.
its explained in detail how obi was able to transform the kraken fish {remote fin} you LISTED into the following

mutant squirmbag: r348c8b1\r12c567b9 => r1c6,r2c5<>2,r7c7<>2

so let's add r12 to both sides yielding r123348c8\r12c567b239. Now we can replace r123 by b123, because both sets contain exactly the same candidates, again not changing the individual excess cover numbers. This yields r348c8b123\r12c567b239. Now we can remove b23 from both sides and get r348c8b1\r12c567b9. This is a Mutant Squirmbag with one fin sector that explains all exclusions without a remote fin.


hope that helps
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 673
Joined: 05 September 2006

Re: Help with a proof?

Postby Sudtyro2 » Sat Nov 30, 2013 4:20 pm

Thx, StrmCkr, for your reply.

Yes, I do fully understand HOW all the eliminations were developed in Obi-Wahn's grid and in all the other example grids cited in the arcilla post. What I don't understand is WHY each EE cell is always a peer of at least one of the conjugate-pair candidates in its grid.

At first, I thought this property applied only to single-elimination grids, but it now appears that it may also apply to multi-elimination grids, such as it does in Obi's grid shown above.

What might be helpful is for someone to provide a counter-example of a single-digit grid where the EE cell does not have this property. Of course, the grid must also contain one or more row/column-based conjugate-pairs.
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby JC Van Hay » Sat Nov 30, 2013 7:40 pm

1. For a tricky counter-example, have a look at NoFish3, here.
2. An example with a box conjugate pair, from Mike Barker's example #6 here
Code: Select all
+-----------------------+---------------------+---------------------+
| 3       789(1)   6    | 1478   1578  1459   | 14579  2      1579  |
| 7(1)    279(1)   4    | 167    3     2569-1 | 8      9(1)   15679 |
| 78(1)   2789(1)  5    | 14678  178   269-1  | 3      49(1)  1679  |
+-----------------------+---------------------+---------------------+
| 14567   167      179  | 1478   1578  3      | 1469   49(1)  2     |
| 458(1)  58(1)    2    | 9      6     45(1)  | 4(1)   7      3     |
| 1467    3        179  | 2      17    14     | 469    5      8     |
+-----------------------+---------------------+---------------------+
| 567(1)  4        7(1) | 6(1)   2     8      | 579-1  3      1579  |
| 9       5(1)     8    | 3      4     7      | 2      6      15    |
| 2       67(1)    3    | 5      9     6(1)   | 17     8      4     |
+-----------------------+---------------------+---------------------+
Starfish(1R5C8B178) :=> -1r7c7,r23c6
JC Van Hay
 
Posts: 716
Joined: 22 May 2010

Re: Help with a proof?

Postby Sudtyro2 » Sun Dec 01, 2013 7:04 pm

Interesting catches, JC! Thx for the feedback!

Regarding Mike Barker's #6 example...I see that his grid only listed the single EE of (1)r7c7. There is actually a (1)r8c29 conjugate-pair having a peer to that EE, so no problems there.

I guess you worked up the Starfish solution separately to get the two extra exclusions at r23c6. I think the jury is still out concerning the multi-elimination grids, where one might need to include box conjugate-pairs. That may very well be the case here where (1)r9c6 is the b8 peer needed for r23c6. I hadn't thought it necessary to include box pairs in Corollary #1 since the grids I'd previously examined didn't seem to need them. However, inclusion of box pairs would actually be less restrictive and would immediately cover cases like your Starfish example.

Regarding the NoFish3...you've got me cold there! I never thought to look at NoFish cases, so it'll take me awhile to review that arena. I'll have to learn about Nice-Loop notation, as well!

Edit:
StrmCkr just supplied another counter-example based on NoFish1 processing having no row/column-based conjugate pairs and only one box pair but with no peer to the EE cell.
http://forum.enjoysudoku.com/post201249.html#p201249
http://forum.enjoysudoku.com/post201288.html#p201288

Clearly, these NoFish grids are not following the conjugate-pair hypothesis, so more analysis is obviously in order. In the meantime, any further inputs or suggestions are most welcome!
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby Sudtyro2 » Wed Dec 04, 2013 3:40 pm

It now appears that the previous counter-examples do, in fact, follow the conjugate-pair hypothesis when one takes into account implicit or “hidden” pairs that appear when the two possible parity states of other conjugate-pairs present in the grid are examined.

For each counter-example below (in hidden text), two conjugate-pair candidates are separately set true, from which a short chain for each then reveals a “hidden” row/column-based conjugate-pair(cp) having a peer to the EE cell(s).

Is this “cheating?”

Hidden Text: Show
Code: Select all
MB#6: r7c7<>1 already accounted for by (cp)r8c29
 .  1  . |  1  1  1 |  1  .  1
 1  1  . |  1  . -1 |  .  1  1
 1  1  . |  1  1 -1 |  .  1  1
---------+----------+---------
 1  1  1 |  1  1  . |  1  1  .
 1  1  . |  .  .  1 |  1  .  .
 1  .  1 |  .  1  1 |  .  .  .
---------+----------+---------
 1  .  1 |  1  .  . | -1  .  1
 .  1  . |  .  .  . |  .  .  1
 .  1  . |  .  .  1 |  1  .  .
For r23c6<>1:
r8c2-r123c2=(cp)r23c1
r8c9-r9c7=(cp)r9c26

NoFish1:
 .  .  . |  .  .  . |  .  .  .
 .  5  . |  5  5  5 |  .  .  .
 5  .  5 |  . -5  5 |  .  .  .
---------+----------+---------
 .  .  . |  .  .  . |  .  .  .
 5  5  . |  .  .  5 |  .  .  .
 .  .  5 |  5  5  . |  .  .  .
---------+----------+---------
 5  5  . |  5  .  . |  .  .  .
 .  5  5 |  .  .  5 |  .  .  .
 .  .  . |  .  .  . |  .  .  .
For r3c5<>5:
r7c4-r6c4=(cp)r6c35
r8c6-r5c6=(cp)r6c45

NoFish3:
 .  .  . |  .  9  9 | -9  .  9
 .  .  9 |  .  9  . |  9  .  9
 9  .  . |  .  .  9 |  .  .  9
---------+----------+---------
 .  9  . |  .  9  . |  9  .  .
 .  .  9 |  .  .  9 |  9  .  .
 .  9  9 |  .  9  9 |  .  .  9
---------+----------+---------
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 9  9  . |  .  .  . |  .  .  .
For r1c7<>9:
r9c1-r3c1=r2c3-r5c3=(cp)r5c67
r9c2-r4c2=(cp)r4c57
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby blue » Thu Dec 05, 2013 9:40 am

Hi Sudtyro2,

Can you make anything of this one ?

Code: Select all
+-----------------+-------------------+----------------+
| 159   8    1579 | 2    6      157   | 4    159   3   |
| 2     3    17-5 | 9    157    4     | 157  6     8   |
| 1569  156  4    | 3    1578   1578  | 157  1259  125 |
+-----------------+-------------------+----------------+
| 7     156  158  | 568  29     3     | 15   4     29  |
| 3     9    58   | 1    4      258   | 6    25    7   |
| 156   4    2    | 567  579    5679  | 3    8     159 |
+-----------------+-------------------+----------------+
| 159   125  3    | 56   1259   12569 | 8    7     4   |
| 4     125  6    | 578  12578  12578 | 9    3     15  |
| 8     7    159  | 4    3      159   | 2    15    6   |
+-----------------+-------------------+----------------+
finned swordfish: r159\c368b1 => r2c3<>5

Code: Select all
+---------+---------+---------+
|#5  . *5 | .  . *5 | . *5  . |
| .  . -5 | .  5  . | 5  .  . |
| 5  5  . | .  5  5 | 5  5  5 |
+---------+---------+---------+
| .  5  5 | 5  .  . | 5  .  . |
| .  . *5 | .  . *5 | . *5  . |
| 5  .  . | 5  5  5 | .  .  5 |
+---------+---------+---------+
| 5  5  . | 5  5  5 | .  .  . |
| .  5  . | 5  5  5 | .  .  5 |
| .  . *5 | .  . *5 | . *5  . |
+---------+---------+---------+
finned swordfish: r159\c368b1 => r2c3<>5

Added: I can see something similar to what's in your post above, but it uses grouped/segment candidates.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Help with a proof?

Postby Sudtyro2 » Thu Dec 05, 2013 12:22 pm

Hi blue,

How about:
r8c9-r9c8=(cp)r9c36
r9c8-r5c8=(cp)r5c36
Code: Select all
+---------+---------+---------+
|#5  . *5 | .  . *5 | . *5  . |
| .  . -5 | .  5  . | 5  .  . |
| 5  5  . | .  5  5 | 5  5  5 |
+---------+---------+---------+
| .  5  5 | 5  .  . | 5  .  . |
| .  . *5 | .  . *5 | . *5  . |
| 5  .  . | 5  5  5 | .  .  5 |
+---------+---------+---------+
| 5  5  . | 5  5  5 | .  .  . |
| .  5  . | 5  5  5 | .  .  5 |
| .  . *5 | .  . *5 | . *5  . |
+---------+---------+---------+
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby blue » Thu Dec 05, 2013 1:52 pm

Right ... I saw that, and then completely forgot about it, since it used a box pair "internally".
Back to the drawing board ...
blue
 
Posts: 573
Joined: 11 March 2013

Postby blue » Thu Dec 05, 2013 2:43 pm

Here's are 3 more to try.
(I'll keep it short this time -- no full PM grids).

Code: Select all
#1
+---------+---------+---------+
| .  .  . | 3  .  . | .  3  . |
| .  .  . | .  3  3 | .  3  3 |
| 3  3  . | .  .  . | .  .  . |
+---------+---------+---------+
| 3  .  . | .  3  . | 3  3  3 |
| .  3  3 | 3  .  . | .  3  . |
| .  . -3 | .  3  3 | 3  .  3 |
+---------+---------+---------+
| .  .  3 | 3  .  . | .  3  . |
| 3  .  3 | .  .  3 | 3  3  . |
| 3  3  . | .  3  3 | .  .  3 |
+---------+---------+---------+

#2
+---------+---------+---------+
| .  7  . | 7  .  . | .  7  . |
| .  .  . | 7  .  7 | .  .  7 |
| .  7  7 | 7  7  7 | 7  .  7 |
+---------+---------+---------+
| .  7  . | .  . -7 | 7  .  7 |
| .  .  7 | .  7  . | .  7  7 |
| .  7  . | 7  7  7 | .  .  7 |
+---------+---------+---------+
| .  .  . | 7  .  7 | .  .  7 |
| .  .  . | 7  7  . | 7  7  7 |
| 7  .  . | .  .  . | .  .  . |
+---------+---------+---------+

#3
+---------+---------+---------+
| .  .  6 | .  .  6 | .  6  6 |
| 6  .  6 | .  6  . |-6  .  6 |
| 6  .  . | 6  .  6 | 6  .  6 |
+---------+---------+---------+
| .  .  . | 6  .  . | 6  6  . |
| .  .  6 | 6  .  . | 6  6  . |
| .  6  . | .  6  6 | 6  .  6 |
+---------+---------+---------+
| 6  .  6 | .  .  6 | 6  .  . |
| 6  6  6 | .  .  6 | .  6  . |
| .  .  . | 6  6  6 | .  6  6 |
+---------+---------+---------+
blue
 
Posts: 573
Joined: 11 March 2013

Re: Help with a proof?

Postby JC Van Hay » Thu Dec 05, 2013 2:45 pm

Try now the 2 first puzzles here
JC Van Hay
 
Posts: 716
Joined: 22 May 2010

Re: Help with a proof?

Postby Sudtyro2 » Thu Dec 05, 2013 5:31 pm

Hi blue and JC,
You guys are going for blood, it seems! :)

Blue's grids 1,2,3 are in hidden text below.
Grid #3, in particular, has lots of paths available.
Grid #2 was tricky...needed a [c8] SIS for the r5c3=7 case, but there's probably something simpler that I missed.
Hidden Text: Show
Code: Select all
#1
| .  .  . | 3  .  . | .  3  . |
| .  .  . | .  3  3 | .  3  3 |
| 3  3  . | .  .  . | .  .  . |
+---------+---------+---------+
| 3  .  . | .  3  . | 3  3  3 |
| .  3  3 | 3  .  . | .  3  . |
| .  . -3 | .  3  3 | 3  .  3 |
+---------+---------+---------+
| .  .  3 | 3  .  . | .  3  . |
| 3  .  3 | .  .  3 | 3  3  . |
| 3  3  . | .  3  3 | .  .  3 |
r1c4-r7c4=(cp)r7c38
r1c8-r7c8=(cp)r7c34

#2
| .  7  . | 7  .  . | .  7  . |
| .  .  . | 7  .  7 | .  .  7 |
| .  7  7 | 7  7  7 | 7  .  7 |
+---------+---------+---------+
| .  7  . | .  . -7 | 7  .  7 |
| .  .  7 | .  7  . | .  7  7 |
| .  7  . | 7  7  7 | .  .  7 |
+---------+---------+---------+
| .  .  . | 7  .  7 | .  .  7 |
| .  .  . | 7  7  . | 7  7  7 |
| 7  .  . | .  .  . | .  .  . |
r3c3-r5c3=(cp)r46c2
r5c3-r5c8
      ||
     r1c8-r3c7=(cp)r48c7
      ||
     r8c8-r8c7=(cp)r34c7

#3
| .  .  6 | .  .  6 | .  6  6 |
| 6  .  6 | .  6  . |-6  .  6 |
| 6  .  . | 6  .  6 | 6  .  6 |
+---------+---------+---------+
| .  .  . | 6  .  . | 6  6  . |
| .  .  6 | 6  .  . | 6  6  . |
| .  6  . | .  6  6 | 6  .  6 |
+---------+---------+---------+
| 6  .  6 | .  .  6 | 6  .  . |
| 6  6  6 | .  .  6 | .  6  . |
| .  .  . | 6  6  6 | .  6  6 |
r6c2-r6c5=(cp)r29c5
r8c2-r7c13=(cp)r7c67


And JC...no single-digit grids in that link.
Did I miss something?
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Re: Help with a proof?

Postby JC Van Hay » Thu Dec 05, 2013 7:27 pm

Sudtyro2 wrote:And JC...no single-digit grids in that link.
Did I miss something?
Here are the puzzles+PMs+JFs(a lot of) :
#1. 005000800010405060700000001050906020000000000060102040400000009020609010001000300 ; patterns_game_0058-017_tarek
Code: Select all
+--------------------------+--------------------------+--------------------------+
| 269-3   49(3)    5       | 2(37)    1269-37  1(37)  | 8       9(37)    24-37   |
| 2389    1        2389    | 4        23789    5      | 279     6        237     |
| 7       49(38)   2469-38 | 2(38)    269-38   (38)   | 2459    59(3)    1       |
+--------------------------+--------------------------+--------------------------+
| 138     5        3478    | 9        3478     6      | 17      2        378     |
| 129-38  49(378)  249-378 | 5(378)   45-378   4(378) | 1569-7  59(378)  56-378  |
| 389     6        3789    | 1        3578     2      | 579     4        3578    |
+--------------------------+--------------------------+--------------------------+
| 4       (378)    6-378   | 25(378)  125-378  1(378) | 256-7   5(78)    9       |
| 358     2        378     | 6        34578    9      | 457     1        4578    |
| 569-8   9(78)    1       | 25(78)   245-78   4(78)  | 3       5(78)    2456-78 |
+--------------------------+--------------------------+--------------------------+
Jellyfishes(378C2468)
#2. 003000600060509080100000007030806090000000000080305020600000002050208060009000400 ; patterns_game_0058_Jellyfish1
Code: Select all
+---------------------------+-------------------------+---------------------------+
| 2589-47  29(47)   3       | (147)   28-147   2(147) | 6        5(14)    59-14   |
| 247      6        247     | 5       12347    9      | 123      8        134     |
| 1        29(4)    258-4   | 6(4)    2368-4   23(4)  | 2359     35(4)    7       |
+---------------------------+-------------------------+---------------------------+
| 2457     3        12457   | 8       1247     6      | 157      9        145     |
| 259-47   29(147)  256-147 | 9(147)  29-147   2(147) | 358-17   35(147)  3568-14 |
| 479      8        1467    | 3       1479     5      | 17       2        146     |
+---------------------------+-------------------------+---------------------------+
| 6        (147)    8-147   | 9(147)  359-147  3(147) | 3589-17  35(17)   2       |
| 347      5        147     | 2       13479    8      | 1379     6        139     |
| 238-7    2(17)    9       | 6(17)   356-17   3(17)  | 4        35(17)   358-1   |
+---------------------------+-------------------------+---------------------------+
Jellyfishes(147C2468)
JC Van Hay
 
Posts: 716
Joined: 22 May 2010

Re: Help with a proof?

Postby Sudtyro2 » Thu Dec 05, 2013 9:37 pm

Hi JC,

For these two puzzles, as near as I can tell, the single-digit grids having exclusions (EE cells) don't have any conjugate pairs. The hypothesis needs at least one to work. Please correct me if I missed something.
Sudtyro2
 
Posts: 464
Joined: 15 April 2013

Postby blue » Fri Dec 06, 2013 4:40 pm

This one should be a little more difficult ...

Code: Select all
+----------------+-------------------+-------------------+
| 7   1359  1259 | 49     135   8    | 2356   2456  356  |
| 58  4     1258 | 1357   6     1357 | 235    258   9    |
| 6   3589  589  | 49     35    2    | 357    4578  1    |
+----------------+-------------------+-------------------+
| 3   1568  4    | 12568  1258  15   | 5679   5679  5678 |
| 2   568   7    | 3568   9     35   | 4      1     3568 |
| 9   1568  1568 | 13568  7     4    | 356    56    2    |
+----------------+-------------------+-------------------+
| 4   7     3589 | 1358   138-5 1359 | 12569  2569  56   |
| 58  2     3589 | 1358   4     6    | 1579   579   57   |
| 1   569   569  | 257    25    579  | 8      3     4    |
+----------------+-------------------+-------------------+
(5)r7c789=r8c789-r8c1=r2c1-r2c35=r13c5 => r7c5<>5

Code: Select all
+---------+---------+---------+
| .  5  5 | .  5  . | 5  5  5 |
| 5  .  5 | 5  .  5 | 5  5  . |
| .  5  5 | .  5  . | 5  5  . |
+---------+---------+---------+
| .  5  . | 5  5  5 | 5  5  5 |
| .  5  . | 5  .  5 | .  .  5 |
| .  5  5 | 5  .  . | 5  5  . |
+---------+---------+---------+
| .  .  5 | 5 -5  5 | 5  5  5 |
| 5  .  5 | 5  .  . | 5  5  5 |
| .  5  5 | 5  5  5 | .  .  . |
+---------+---------+---------+
blue
 
Posts: 573
Joined: 11 March 2013

Next

Return to Advanced solving techniques