The New Sudoku Players' Forum

by **ronk** » Mon Jan 16, 2006 6:23 pm

Carcul wrote:Consider the following:

If I have used a technique (which uses the set of cells "A") to elimininate candidate "x" from cell "B" (which can belong or not to A), then this would imply that making B=x leads to some sort of contradiction in/with the set A.

Sorry, we engineers aren't very good with questions in the abstract, until after we've seen an actual example or two.

Have you got one?

Ron

by **ronk** » Mon Jan 16, 2006 8:02 pm

Carcul wrote:
Ronk wrote:I don't know how to do a formal proof,

The most important proof is simply to make the substitution: translating this to a given notation (loops, ALS, etc) is another problem.

One can always list the possible cases:

Code: Select all: 6 2459 124 | 28 149 3 | 245 1458 7 245 2345 7 | 268 14 68 | 9 13458 1458 249 8 1234 | 7 5 19 | 234 6 14 ----------------------+----------------------+-------------------- 3 2479 24 | 59 6 5789 | 1 2489 489 12 269 8 | 3 19 4 | 7 259 569 1479 4679 5 | 89 2 1789 | 46 489 3 ----------------------+----------------------+-------------------- B45 1 346 | 4569 8 2 | 3456 7 4569 A2457 A23457 9 | 456 C37 56 | 8 1345 1456 8 A3457 46 | 1 C37 569 | 456 3459 2 Set B is either 4 or 5 .... and r8c5 and r9c5 of set C are either 3 or 7. Listing the four possible cases, we can determine the "remainder" in set C. set A "remainder" r7c1 r8c5 r9c5 r8c1 r8c2 r9c2 r8c1,r8c2,r9c2 45 37 37 2457 23457 3457 23457 4 3 7 257 257 35 2357 4 7 3 25 235 57 2357 5 3 7 247 247 34 2347 5 7 3 24 234 47 2347

At this point the "remainder" of the classical 'Sue De Coq' would be a locked set, 3 candidates for three cells. In this (yet to be proven, I guess) grouped 'Sue De Coq', the remainder is an almost-locked-set instead. That's a bit bothersome to me.

By inspection of the possibilities table above, we see that whenever r7c1<>4, the remainder includes a 4 ... and whenever r7c1<>5, the remainder includes a 5. But because it's not a locked set, this doesn't convincingly prove the eliminations r7c3<>4 and r9c3<>4. That my approach solved this particular puzzle could be just a 'happy accident'.

In any case, the table indicates no eliminations are possible based on the 37 of set C and. since it's a grouped set, that's not surprising to me. And it's entirely possible the 37 is in the remainder for the same reason *without* invalidating the 45 eliminations in box 7. But if that's the case, I don't know how to prove it ... which is where I was when starting this post. Deja vu all over again.

by **bennys** » Mon Jan 16, 2006 8:06 pm

Carcul wrote:

Consider the following:

If I have used a technique (which uses the set of cells "A") to elimininate candidate "x" from cell "B" (which can belong or not to A), then this would imply that making B=x leads to some sort of contradiction in/with the set A.

Its true assuming the "current" candidate list .

by **Carcul** » Tue Jan 17, 2006 11:57 am

Another Example of a Type 3 AUR

In this post I will illustrate an example of a continuous nice loop that includes a type 3 AUR. Consider the puzzle

Code: Select all: . 3 8| . . .| 9 . . . 7 .| . 8 .| . . . 6 . .| . 3 9| 8 . . ------+------+------- 9 . .| 7 . .| . 4 . . . .| 3 . 1| . . . . 2 .| . . 8| . . 6 ------+------+------- . . 4| 1 7 .| . . 9 . . .| . 5 .| . 2 . . . 6| . . .| 3 1 .

(this is "unlimited077" from Angus) and let's jump to the point where Simple Sudoku gets stuck:

Code: Select all: 45 3 8 | 2456 1 7 | 9 56 24 145 7 9 | 2456 8 245 | 1245 356 1234 6 14 2 | 45 3 9 | 8 57 147 -------------+---------------+---------------- 9 168 135 | 7 26 25 | 125 4 1238 48 468 57 | 3 2469 1 | 257 579 278 134 2 1357| 459 49 8 | 157 3579 6 -------------+---------------+---------------- 2 5 4 | 1 7 3 | 6 8 9 138 189 13 | 89 5 6 | 47 2 47 7 89 6 | 2489 249 24 | 3 1 5

Here we have a type 3 AUR in cells r8c24/r9c246 which can be used in two loops. First, a discontinuous loop:

[r6c1]=3=[r8c1]-3-[r8c3]-1-[r8c2]=1|2,4=[r9c4|r9c6]-2,4-[r9c5]-9-[r6c5]-4-[r6c1], => r6c1<>4.

Next, a continuous loop:

[r4c9]=3=[r4c3]-3-[r8c3]-1-[r8c2]=1|2,4=[r9c4|r9c6]-2,4-[r9c5]-9-[r9c2]-8-[r4c2]=8=[r4c9]

which implies

r6c3<>3
r8c1<>1
r9c4<>9
r8c2<>8
r5c2<>8
r4c9<>1,2.

From here, the puzzle can be solved, for example, with a simple nice loop.

Carcul

by **ronk** » Tue Jan 17, 2006 1:09 pm

Carcul wrote:this is "unlimited077" from Angus

I was unable to find an "unlimited pack" at angusj.com. Do you have a link for that? TIA, Ron

by **Carcul** » Tue Jan 17, 2006 1:31 pm

Hi Ronk.

Now that you mention that, I don't remember where I found the pack. Perhaps someone can give an indication on that. If not, I can send them by email to you, if you like. The pack is a colection of puzzles with which the SS program gets stuck at some point, and so they are very good for applying some advanced techniques. Some of them also provide very good examples of useful AURs.

Regards, Carcul

by **Wolfgang** » Tue Jan 17, 2006 2:38 pm

ronk wrote:I was unable to find an "unlimited pack" at angusj.com. Do you have a link for that? TIA, Ron

If i remember right, it is included in the simple sudoku program.

by **ronk** » Tue Jan 17, 2006 8:57 pm

Carcul wrote:Consider the puzzle ... (this is "unlimited077" from Angus) and let's jump to the point where Simple Sudoku gets stuck: ...

I used your grid as the take-off point for a post on the Identification of forcing chains thread ... describing one way to arrive at the elimination r2c6<>5.

I think AUR grids have a lot more potential than BUG grids, simply because there are usually fewer non-AUR candidates than non-BUG candidates. I suppose that's offset by the fact that fewer puzzles have AURs, but hey, we can't have everything.

Regards, Ron

Postscript:

Wolfgang wrote:If i remember right, [ronk edit: an "unlimited pack"] is included in the simple sudoku program.

I could not find it there, but I did PM Angus requesting he post a link here IF he has such a package available for "public consumption".

by **ronk** » Wed Jan 18, 2006 5:38 am

Hi Carcul,

Here is a variant of the type 2 AUR, which has the two non-AUR candidates in the same cell instead of two different cells. After basic techniques, a "sticking point" for puzzle #272 of the top1465 is ...

Code: Select all: 368 36 68 | 5 2 1 | 79 4 79 1 4 2 | 3 ^79 ^79 | 5 8 6 9 7 5 | 46 48 68 | 3 2 1 -------------------+-------------------+------------------ 36 369 4 | 8 679 2 | 79 1 5 2 5 ^69 | 1 ^4679 ^79 |^48 3 4789 7 8 1 | 49 3 5 | 24 6 249 -------------------+-------------------+------------------ 5 69 *689 | 2 1 4 |^68 7 3 468 1 3 | 7 5 68 | 2468 9 248 468 2 7 | 69 89 3 | 1 5 48

Using the AUR (79) in r25c56, there exists the nice loop:

[r7c3]-9-[r5c3]-6-[r5c5]-4-[r5c7]-8-[r7c7]=8=[r7c3] => r7c3<>9

which solves the puzzle. Although r5c5 *is* effectively a bivalue, the AUR's impact in the nice loop is obscure and perhaps better written:

[r7c3]-9-[r5c3]-6-(AUR:[r5c5]=6|4=[r5c5])-4-[r5c7]-8-[r7c7]=8=[r7c3] => r7c3<>9

Regards, Ron

P.S. After basic techniques could no longer advance the puzzle, my software program found 31 puzzles in the top1465 with this variant of the type 2 AUR. They are puzzle numbers:

Code: Select all: 134, 272, 410, 512, 525, 606, 613, 632, 653, 695, 743, 804, 853, 882, 883, 891, 923, 989, 1011, 1062, 1076, 1100, 1116, 1120, 1131, 1180, 1269, 1302, 1327, 1358, 1381

This puzzle (#272) is the only one I've looked at so far.

by **Carcul** » Wed Jan 18, 2006 9:52 am

Hi Ronk.

That is an excellent example. If you don't mind, I am going to add it to the original post. Good work.

BTW, both your loops are OK.

Regards, Carcul

by **Jeff** » Fri Jan 20, 2006 4:37 am

Carcul wrote:The most important proof is simply to make the substitution: translating this to a given notation (loops, ALS, etc) is another problem. Consider the following:

If I have used a technique (which uses the set of cells "A") to elimininate candidate "x" from cell "B" (which can belong or not to A), then this would imply that making B=x leads to some sort of contradiction in/with the set A.

Hi Carcul and all lords of logic, I would like to add this statement to the definition list of forcing chains. I need suggestion for a name for this back substitution technique, and definition wordings to reflect how this technique is related to forcing chains and nets. Could you help?

by **ronk** » Fri Jan 20, 2006 5:46 am

Jeff wrote:
Carcul wrote:The most important proof is simply to make the substitution: translating this to a given notation (loops, ALS, etc) is another problem. Consider the following:

If I have used a technique (which uses the set of cells "A") to elimininate candidate "x" from cell "B" (which can belong or not to A), then this would imply that making B=x leads to some sort of contradiction in/with the set A.

I need suggestion for a name for this back substitution technique, and definition wordings ...

Although "backtesting" is normally used for to develop a trading strategy, I suggest "Backtesting Eliminations". A convincing illustration of Carcul's statement is this xy-wing example:

P.S. I tried a clickable thumbnail but the "clicked image" was terribly fuzzy.

by **Carcul** » Fri Jan 20, 2006 10:17 am

Hi Jeff and Ronk.

Jeff wrote:I need suggestion for a name for this back substitution technique, and definition wordings to reflect how this technique is related to forcing chains and nets. Could you help?

Ronk wrote:Although "backtesting" is normally used for to develop a trading strategy, I suggest "Backtesting Eliminations".

I suggest "Logic Test for Networks" or "Logic Test for Forcing Chains".

Regards, Carcul

by **angusj** » Fri Jan 20, 2006 1:49 pm

ronk wrote:I could not find it there, but I did PM Angus requesting he post a link here IF he has such a package available for "public consumption".

Hi ronk. I didn't get your PM (unless you're rkral in the Programmer's Forum in which case I replied to you several days ago

).

Anyhow, here are the links to several of my more advanced puzzle packs which aren't currently visible on my webpage ...

http://angusj.com/sudoku/ss_xywing_1.zip
http://angusj.com/sudoku/ss_multicolor_1.zip
http://angusj.com/sudoku/ss_multicolor_2.zip

And some very challenging puzzles which tend to get progressively harder (but still don't require forcing chains etc) -
http://angusj.com/sudoku/ss_undefined_1.zip
http://angusj.com/sudoku/ss_undefined_2.zip

These puzzles require strategies beyond Simple Sudoku's current solving matrix ...
http://angusj.com/sudoku/ss_unlimited_1.zip

by **ronk** » Fri Jan 20, 2006 2:37 pm

angusj wrote:here are the links to several of my more advanced puzzle packs which aren't currently visible on my webpage ...

Hi Angus, thanks for the links, Ron

The New Sudoku Players' Forum

Almost Unique Rectangles: description and use in nice loops