Bi-directional cycle + Unique Rectangle Typ 2

Advanced methods and approaches for solving Sudoku puzzles

Bi-directional cycle + Unique Rectangle Typ 2

Postby claudiarabia » Mon May 04, 2009 8:04 pm

This sudoku is solved by SE with 2 forcing chains, an X-Wing, and a Unique Rectangle Typ 4. I instead missed the X-Wing which is produced by the forcing chains only and turned to a lovely rectangular cycle, rectangular in a double way:
Code: Select all
8.......2
....6....
..95.74..
..21..9..
.5.....1.
..7..26..
..64.95..
....3....
1.......8

 *-----------*
 |8..|...|..2|
 |...|26.|8.9|
 |..9|587|4.1|
 |---+---+---|
 |..2|1..|9..|
 |.58|...|21.|
 |.17|..2|6..|
 |---+---+---|
 |.86|419|52.|
 |...|.3.|1.6|
 |1..|.2.|..8|
 *-----------*

 
 *--------------------------------------------------------------------*
 | 8     467-3 #145-3   |#39    #49   #14-3    |#37    567-3   2      |
 | 3457   347   #1345   | 2      6    #13-4    | 8      357    9      |
 | 236    236    9      | 5      8      7      | 4      36     1      |
 |----------------------+----------------------+----------------------|
 | 346    346    2      | 1      457    34568  | 9      378    3457   |
 | 3469   5      8      | 369    479    346    | 2      1      347    |
 | 349    1      7      | 389    459    2      | 6      38     345    |
 |----------------------+----------------------+----------------------|
 | 37     8      6      | 4      1      9      | 5      2      37     |
 | 2457   279   #45     | 78     3      58     | 1      49     6      |
 | 1     79-3   #345    | 67     2      56     |#37    49-3    8      |
 *--------------------------------------------------------------------*


I started my cycle from r9c7 anticlockwise/left with 7

r9c7=7 -> r1c7=3 -> r1c4=9 -> r1c5=4 -> r1c6=1 -> r2c6=3/r1c3=5/r2c3=1 -> r8c3=4 -> r9c3=3 -> r9c7=7

Clockwise/right:

r9c7=3 -> r89c3=45 -> r12c3=13 -> UR2 in r12c6=14-3 -> r1c5=9/r1c4=3 -> r1c7=7 -> r9c7=3

The Unique Rectangle Typ 2 in r12c6 comes from the pair of 13 in r12c3. Here we have also the example of a self-eating chain because in the end of the cycle the pair of 13 in r12c3 can be dissolved. The cycle ends finally up in eliminating the 3 in r1c2368 and in r9c28 and 4 in r2c6. I ramificated the cycle in the upper middle box in order to eliminate the 4 in r2c6 which finally brings the breaking point of the puzzle.

Afterwards an XY-Wing is appearing in r1c27 and r3c8 on the numbers 367.


Code: Select all

 *--------------------------------------------------------------------*
 | 8     *67     15     | 39     49     14     |*37    57-6    2      |
 | 3457   347    1345   | 2      6      13     | 8      357    9      |
 | 23-6  23-6    9      | 5      8      7      | 4     *36     1      |
 |----------------------+----------------------+----------------------|
 | 346    346    2      | 1      457    34568  | 9      378    3457   |
 | 3469   5      8      | 369    479    346    | 2      1      347    |
 | 349    1      7      | 389    459    2      | 6      38     345    |
 |----------------------+----------------------+----------------------|
 | 37     8      6      | 4      1      9      | 5      2      37     |
 | 2457   279    45     | 78     3      58     | 1      49     6      |
 | 1      79     345    | 67     2      56     | 37     349    8      |
 *--------------------------------------------------------------------*


Afterwards the sudoku can be solved easily with locked candidates (Box vs. Line/Line vs. Box)

Claudia
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby PIsaacson » Tue May 05, 2009 3:51 am

Claudia,

An interesting puzzle and an interesting chain. I submitted it to my ALS engine since it looked to me like at least some of the cells formed ALSs and it produced the following continuous ALS chain/loop:
Code: Select all
als+[6x5/6] r1c5.<n49> -9- r1c4.<n39> -3- r1c7.<n37> -37- r9c7.<n37> -3- r89c3.<n345> -5- r1c3456.<n13459>

This produces 10 eliminations (although r9c8<>3 is from a simple naked pair and shouldn't count):
r1c2<>34, r1c3<>4, r1c8<>3, r2c3<>45, r2c6<>4, r8c1<>4, r9c2<>3, r9c8<>3 - thumbnail 1 below (leftmost)

Adding r2c3 and r2c6 adds an additional 3 eliminations but alters the continuous ALS chain into something else:
r2c1<>3, r2c2<>3, r2c8<>3 - thumbnail 2 below (middle)

Finally, adding the UR logic adds an additional 2 eliminations:
r1c3<>3, r1c6<>3 - thumbnail 3 below (rightmost)

ImageImageImage

Alternative approach: The 3s are subject to 8 eliminations via x-coloring/x-cycles: r1c28<>3, r2c128<>3, r4c69<>3, r9c2<>3 + r9c8<>3 from np {37}

Following either path with your XY-wing completes the puzzle.

So I have to ask: Is this just a knock-out punch from one wicked clever chain, or am I missing the big picture???

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby daj95376 » Tue May 05, 2009 5:40 am

After performing basics:

Code: Select all
 Franken Swordfish c37b2\r129           [r1c28],[r2c128],[r9c2]<>3
 +---------------------------------------------------------------+
 |  8     467-3 *1345  | *39    49   *134   | *37    567-3 2     |
 |  457-3 47-3  *1345  |  2     6    *134   |  8     57-3  9     |
 |  236   236    9     |  5     8     7     |  4     36    1     |
 |---------------------+--------------------+--------------------|
 |  346   346    2     |  1     457   3468  |  9     378   3457  |
 |  3469  5      8     |  369   479   346   |  2     1     347   |
 |  349   1      7     |  389   459   2     |  6     38    345   |
 |---------------------+--------------------+--------------------|
 |  37    8      6     |  4     1     9     |  5     2     37    |
 |  2457  2479   45    |  78    3     58    |  1     49    6     |
 |  1     479-3 *345   |  67    2     56    | *37    49    8     |
 +---------------------------------------------------------------+
 # 86 eliminations remain

 more basics

 XY-Wing  [r1c7]/[r1c2]+[r3c8]       [r1c8],[r3c12]<>6

It's rare to run into an unfinned fish like this anymore.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby storm_norm » Tue May 05, 2009 7:44 am

Code: Select all
.------------------.------------------.------------------.
| 8     3467 G1345 | 39    49    134  | 37   H3567  2    |
|F3457  347   1345 | 2     6     134  | 8     357   9    |
| 236   236   9    | 5     8     7    | 4   I-36    1    |
:------------------+------------------+------------------:
| 346   346   2    | 1     457   3468 | 9     378   3457 |
| 3469  5     8    | 369   479   346  | 2     1     347  |
| 349   1     7    |B389   459   2    | 6    A38    345  |
:------------------+------------------+------------------:
| 37    8     6    | 4     1     9    | 5     2     37   |
|E2457  2479  45   |C78    3    D58   | 1     49    6    |
| 1     3479  345  | 67    2     56   | 37    49    8    |
'------------------'------------------'------------------'

(3=8)A - (8)B = (8)C - (8=5)D - (5)E = (5)F - (5)G = (5-6)H = (6)I; I is not 3
naked pair
then singles.
Last edited by storm_norm on Tue May 05, 2009 4:53 am, edited 1 time in total.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby aran » Tue May 05, 2009 8:36 am

daj95376
That unfinned franken swordfish : very nice
P Isaacson
Just a number of observations on your post
1. The eliminations arising from your loop : I think that most solvers would not deduce as many from the loop.
Firstly it would depend on whether they close the loop using DR avoidance on 13r12c36 to place 4 over r12c6, or whether they use memory of 3r1c4 to place 1 at r1c3.
Then either way, the loop is not straightforward => "weak-links" conjugate rule is not of easy application etc (as I mentioned elsewhere recently).
So I am interested to know if your approach is as follows :
- find a loop
- then do a base/cover set analysis in that context
- then attribute the eliminations arising from base/cover to the loop.
If that is the case, then I wonder if you are not giving too much credit to the loop.
2. Concerning those pictures : it would probably be a good idea to provide a key
eg :
- significance of the color coding (with each picture)
- list of the base sets/cover sets (for the individual pictures)
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Tue May 05, 2009 9:13 am

Here's what I don't like about fishing -- my program finds these things, but I have no idea what to call some of them. My DLX single digit base/cover fishing algorithm "caught" the following:
Code: Select all
do_fishing - starting digit 3 size 3 4960 combinations

do_fishing - reducing r4c9.<3457> by <3> fish[3] c23b9\r49c9b1 2

do_fishing - reducing r1c2.<3467> by <3> fish[3] c37b2\r129 1
do_fishing - reducing r1c8.<3567> by <3> fish[3] c37b2\r129 1
do_fishing - reducing r2c1.<3457> by <3> fish[3] c37b2\r129 1
do_fishing - reducing r2c2.<347> by <3> fish[3] c37b2\r129 1
do_fishing - reducing r2c8.<357> by <3> fish[3] c37b2\r129 1
do_fishing - reducing r9c2.<379> by <3> fish[3] c37b2\r129 1

So I know a fish-3 is some sort of swordfish and I (on a really good day) might have guessed that c37b2\r129 is a franken variety, but what the heck is that first one - c23b9\r49c9b1??? Some kind of teenage mutant ninja turtle or what???
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby PIsaacson » Tue May 05, 2009 9:45 am

Aran,

The loop was discovered by my testbed ALS engine with the following base/cover sets:
Code: Select all
r1c5 -9- r1c4 -3- r1c7 -37- r9c7 -3- r89c3 -5- r1c3456

do_alschains - reducing r1c2.<3467> by <4> - standard elimination
do_alschains - reducing r1c3.<1345> by <4> - duplicate elimination

do_alschains - reducing r1c2.<367> by <3> base/cover
do_alschains - reducing r1c8.<3567> by <3> base/cover
do_alschains - reducing r2c3.<1345> by <4> base/cover
do_alschains - reducing r2c3.<135> by <5> base/cover
do_alschains - reducing r9c2.<379> by <3> base/cover
do_alschains - base/cover {1n34567 8n3 9n37} {1349r1 3r9 45c3 7c7}

do_alschains - reducing r8c1.<2457> by <4> base/cover
do_alschains - base/cover {1n34567 8n3 9n37} {1349r1 3r9 5c3 7c7 4b7}

do_alschains - reducing r2c6.<134> by <4> base/cover
do_alschains - base/cover {1n34567 8n3 9n37} {139r1 3r9 45c3 7c7 4b2}


I should have clarified that the eliminations are not all from the loop itself, but rather from the combined ALS chain eliminations plus the eliminations from the various base/cover sets that can be assigned. That's for the first diagram.

The second includes all the cells involved in Claudia's "lovely rectangular cycle" and again is the result of additional base/cover analysis. Likewise the third diagram considers the addition of not just the cells, but also the UR base sets and the subsequent additional base/cover analysis.

The ALS engine generated the *.sud case file that contained the various positions for Xsudo to display, but I forgot to post the detail. I promise to do a better job in the future of including the full set/link-set descriptions. My bad...

Cheers,
Paul

P.S. Sorry, I forgot to answer question 1 in full. I first find some interesting structure, ALS chain, Death Blossom, nrczt chain, URs etc. I perform the standard eliminations. I then generate the base set for the given position and optionally try all possible combinations of base/cover sets or just find all the possible cover sets. The solution log contains all the eliminations and associates base/cover eliminations with the appropriate base/cover set. So if I don't include the full solution log (as I didn't in my first posting), then it looks like the eliminations are all due to the initial structure. This can be very misleading, especially when there are various sub-structures uncovered by the base combination generator.

I've pretty much become a base/cover convert. Blame Allan...
Last edited by PIsaacson on Tue May 05, 2009 6:10 am, edited 1 time in total.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby aran » Tue May 05, 2009 10:06 am

PIsaacson wrote:I should have clarified that the eliminations are not all from the loop itself, but rather from the combined ALS chain eliminations plus the eliminations from the various base/cover sets that can be assigned. That's for the first diagram

Paul
As I thought:)
My point or further point being that base/cover sets will do all that work in the first place without ever needing to call upon the ALS.
Similar to a recent point where I noted that you used dual-linked ALS then base/cover to make elims which the base/cover would have found alone.
Prompting the tentative conclusion that base/cover does stronger work than any other mechanism.
We had recently Allan demonstrating that base/cover solves the Easter Monster in one fell swoop.
The question then is : at what point to call upon base/cover ? or even why call upon anything else ?
PIsaacson wrote:I promise to do a better job in the future of including the full set/link-set descriptions. My bad...

It wasn't a criticism as I am sure you know. I just wouldn't want people to think that those pictures are subway maps:)
aran
 
Posts: 334
Joined: 02 March 2007

Postby PIsaacson » Tue May 05, 2009 10:38 am

Aran,

Why do anything other than base/cover indeed? I've been asking myself that very question lately, and the only comment I have is that you still need some way of finding "interesting" base sets.

I started a thread in the programming section on how to execute base/cover logic, but to my chagrin, there's been no interest. I guess the problem is there's no burning need for base/cover without a super technique that subsumes all others and finds the shortest and most productive solution in minimal time. For now, that appears to be in the domain of the human brain. But I'm working on it...

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby aran » Tue May 05, 2009 11:09 am

PIsaacson wrote:Why do anything other than base/cover indeed? I've been asking myself that very question lately, and the only comment I have is that you still need some way of finding "interesting" base sets

That sounds reasonable. Once an interesting base is found (eg a loop), then in a sense the computer solver should bypass the loop eliminations and go directly to base/cover mode.
The human solver could do the same. That is he could acquire the reflex to say : this is a loop, possibly a complex one. Whatever eliminations I can find by analysing the loop, I will find at least as many and probably more by going into base/cover mode.
To do that, obviously he needs a solid grasp of base/cover (=>some work) and a method for usefully noting/describing the base and cover, without having to draw pictures:)
Which I do think is achievable.
aran
 
Posts: 334
Joined: 02 March 2007

Postby hobiwan » Tue May 05, 2009 12:24 pm

PIsaacson wrote:So I know a fish-3 is some sort of swordfish and I (on a really good day) might have guessed that c37b2\r129 is a franken variety, but what the heck is that first one - c23b9\r49c9b1??? Some kind of teenage mutant ninja turtle or what???

To classify the fish you have to have an equal number of base and cover sets. c9 in your example above is one to many, base candidate r7c9 is uncovered and thus a fin.
Without c9 you have cols and blocks in the base set and rows and blocks in the cover set which means Franken Fish. You have three base sets, so Swordfish and one uncovered base candidate so Finned Fish:
Finned Franken Swordfish: 3 c23b9 r49b1 fr7c9 => r4c9<>3

Edit:
HoDoKu finds this variety first:
Finned Franken Swordfish: 3 r47b4 c19b6 fr4c6 efr4c1 efr4c2 => r4c9<>3
(Cannibalistic with two endo fins and one exo fin)
I must really have screwed up my fish sorting...
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby aran » Tue May 05, 2009 1:18 pm

PIsaacson wrote:So I know a fish-3 is some sort of swordfish and I (on a really good day) might have guessed that c37b2\r129 is a franken variety, but what the heck is that first one - c23b9\r49c9b1??? Some kind of teenage mutant ninja turtle or what???

Seen from a fin perspective, as Hobiwan points out <3>r4c9 is eliminated under either of the only possibilities (fin true/fin false).
Back in base/cover terms, you would think of it as
base : c2 c3 b9
cover : b1 r4 r9 c9 (or r7c9)
rank=1
3r7c9 if true reduces the rank to -1 (removing r4 c9).
Hence <3>r7c9.
Opposite sides of a coin. The fin finds the elimination; the elimination finds the rank.
Hobiwan wrote:HoDoKu finds this variety first:
Finned Franken Swordfish: 3 r47b4 c19b6 fr4c6 efr4c1 efr4c2 => r4c9<>3
(Cannibalistic with two endo fins and one exo fin)
I must really have screwed up my fish sorting...

I have noticed before that you come up with bases that have overlapping truths eg here r4 and b4 does not necessarily have two truths.
Question : is this a good idea ?
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Tue May 05, 2009 1:31 pm

hobiwan wrote:HoDoKu finds this variety first:
Finned Franken Swordfish: 3 r47b4 c19b6 fr4c6 efr4c1 efr4c2 => r4c9<>3
(Cannibalistic with two endo fins and one exo fin)

If you eliminate the redundant 3r4, you have a finned franken x-wing ... better known as the empty rectangle technique.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Tue May 05, 2009 5:26 pm

PIsaacson wrote:do_fishing - reducing r4c9.<3457> by <3> fish[3] c23b9\r49c9b1 2

..., but what the heck is that first one - c23b9\r49c9b1??? Some kind of teenage mutant ninja turtle or what???

As Hobiwan pointed out, traditional fish have the same number of base sectors as cover sectors; i.e., NxN. However, Obi-Wahn posted an article about the arithmetic of fish where he presented Nx(N+k) fish. These fish don't have traditional names assigned to them.

Your first fish is an Nx(N+1) fish. Cell [r4c9] is covered twice by [r4] and [c9], but is not contained in any base sectors. According to Obi-Wahn's arithmetic, you can eliminate the candidate in this cell.

===== ===== =====

What you need to be concerned about is that your fishing logic missed these simpler fish for the same elimination. The first being an Empty Rectangle.

Code: Select all
2-Fish r7b4\c19                 fF 101\020  <> 3  [r4c9]
2-Fish r7b4\r4c1                fm 101\110  <> 3  [r4c9]

And various Jellyfish for [r4c6]<>3.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Tue May 05, 2009 6:05 pm

ronk wrote:If you eliminate the redundant 3r4, you have a finned franken x-wing ... better known as the empty rectangle technique.

You are right of course and I was not precise in my wording. I should have said: HoDoKu finds this variety first when looking for Swordfishes for that elimination.
aran wrote:I have noticed before that you come up with bases that have overlapping truths eg here r4 and b4 does not necessarily have two truths.
Question : is this a good idea ?

Not in this case, where an easier fish is available. Thats what I meant, when I said I screwed up my sorting: The search code finds all possible base/cover set combinations but it should present the simplest first, which it doesnt. But there are cases where no fish with the same size would be possible without overlap.

Take the following grid for example:
Code: Select all
.----------------------.-------------------.-----------------.
|  12369   4     12369 | 8     29    7     | -23    5    169 |
|  7      *1239  5     | 134   6     349   |  8    #24   19  |
|  12369   8     12369 | 1345  2459  23459 | -234   7    169 |
:----------------------+-------------------+-----------------:
|  1245    125   124   | 7     3     8     |  6     9   *245 |
|  8       39    39    | 2     45    6     |  7     1    45  |
| *2456   *256   7     | 9     1     45    | @245   8    3   |
:----------------------+-------------------+-----------------:
|  23456   7     2346  | 3456  2459  23459 |  1     24   8   |
| *2469    69    8     | 46    7     1     | *245   3   *245 |
|  12345   1235  1234  | 345   8     2345  |  9     6    7   |
'----------------------'-------------------'-----------------'

Finned Franken Jellyfish: 2 r268b6 c1279 fr2c8 efr6c7 => r13c7<>2

Without the overlap r6b6 you need a Squirmbag:
Code: Select all
.---------------------.---------------------.-----------------.
| 12369  4     *12369 | 8     *29     7     | -23    5    169 |
| 7      1239   5     | 134    6      349   |  8    #24   19  |
| 12369  8     *12369 | 1345  *2459  *23459 | -234   7    169 |
:---------------------+---------------------+-----------------:
| 1245   125   *124   | 7      3      8     |  6     9   *245 |
| 8      39     39    | 2      45     6     |  7     1    45  |
| 2456   256    7     | 9      1      45    | #245   8    3   |
:---------------------+---------------------+-----------------:
| 23456  7     *2346  | 3456  *2459  *23459 |  1    *24   8   |
| 2469   69     8     | 46     7      1     |  245   3    245 |
| 12345  1235  *1234  | 345    8     *2345  |  9     6    7   |
'---------------------'---------------------'-----------------'

Finned Franken Squirmbag: 2 c3568b6 r13479 fr2c8 fr6c7 => r13c7<>2

I realize of course that fishes that size are of practically no use for a manual solver.

PS: In HoDoKu overlapping base sets can be disabled by setting the number of endo fins to 0.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Next

Return to Advanced solving techniques

cron