## The Empty Rectangle (ER)

Advanced methods and approaches for solving Sudoku puzzles
I'm out the door, but really quick consider:
Code: Select all
`+------------------+---------------+------------------+ |    56   56     8 |  39    2  349 |    7   349     1 | |    12    3     4 |   6    7   19 |    5     8    29 | |     9   12     7 |   8    5  134 |   26   346   234 | +------------------+---------------+------------------+ |   148  178   369 |   2 *369    5 |   69    14    47 | |  3456 *569     2 |   7    1  -69 |    8  3456   346 | |  1356   17  3569 |   4 *369    8 |  269  1356  2367 | +------------------+---------------+------------------+ |    28   28    69 |  39    4  369 |    1     7     5 | |   356 *569  3569 |   1  *69    7 |    4     2     8 | |     7    4     1 |   5    8    2 |    3    69    69 | +------------------+---------------+------------------+ `

This is a classic finned X-wing. There is a strong link in column 2. In column 5 there are three cells with 9 - not a strong link and thus not a skyscraper. However r4c5 and r6c5 are in the same box, they can be treated as a group. In this case [r4c5|r6c5] and r8c5 make a grouped strong link. The algorithm proceeds as before except that cancellations now require that a cell be buddies with r5c2 and all cells of [r4c5|r6c5]. Thus the 9 can be eliminated from r5c6. I talked briefly about grouped strong links earlier in this topic. Also check http://forum.enjoysudoku.com/viewtopic.php?t=2384. The advantage is where the skyscraper would not have resulted in an elimination the "grouped skyscraper" does which allows your strong linked approach to be applied to all double implication strong X-cycles (strong statement probably need to justify it more). My kids are awaiting. I'm off until next week.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote:The algorithm proceeds as before except that cancellations now require that a cell be buddies with r5c2 and all cells of [r4c5|r6c5]. Thus the 9 can be eliminated from r5c6.

Or one can color using the strong link(s) of empty rectangle(s) ...
Code: Select all
` . . . | B . B | . b .  . . . | . . b | . . B  . . . | . . . | . . .  - - - + - - - + - - -  . . A | . a . | 9 . .  . a . | . . A | . . .  . . A | . a . | 9 . .  - - - + - - - + - - -  . . a | a . a | . . .  . A a | . A . | . . .  . . . | . . . | . B b `
[edit: coloring: corrected box 2, added box 3 & 9]

... and note with two As in row 8 that color A cannot represent true.

Ron
Last edited by ronk on Thu Mar 09, 2006 6:08 am, edited 1 time in total.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Ronk, I don't think that an empty rectangle is needed. It seems that boxes 4, 5, 7, & 8 can use simple coloring with groups to make the same deduction.

Also there is a slight error there. You can't color box 2 with that scheme because r1c4 does not have a conjugate link with r7c46. It is just a converse link, which isn't quite good enough as the following starred set of cells will show.

Code: Select all
` . . . |*A . a | . 9 .  . . . | . . a | . .*9  . . . | . . . | . . .  - - - + - - - + - - -  . . A | .*a . | 9 . .  .*a . | . . A | . . .  . . A | . a . |*9 . .  - - - + - - - + - - -  . . a | a .*a | . . .  . A*a | . A . | . . .  . . . | . . . | .*9 9 `
Myth Jellies

Posts: 593
Joined: 19 September 2005

Myth Jellies wrote:I don't think that an empty rectangle is needed. It seems that boxes 4, 5, 7, & 8 can use simple coloring with groups to make the same deduction.

Agreed, but I think one is applying the strong links of ERs when coloring these boxes ... even if one isn't using the term. Besides, it kept me on topic.

Myth Jellies wrote:You can't color box 2 with that scheme because r1c4 does not have a conjugate link with r7c46.

Thanks, I'll edit my post. Not making sure that an "about to be colored" cell sees all of its conjugately colored mates is certainly a hazard of grouped coloring.

Ron
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Just thought I would show the three different ways two connected Empty Rectangles can interact with eachother and one strong link:

example 1: (skyscraper style)
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | . . . | * + .------+-------+------. . . | . . . | . * .. . a-----------b . .. . . | . . . | . * .------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

example 2: (x-wing style)
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . +*| * * * | . +*.------+-------+------. . * | . . . | . * .. . a-------------b .. . * | . . . | . * .------+-------+------. . * | . . . | . * .. . * | . . . | . * .. . * | . . . | . * .notice how the ERI's are also eliminated! `

example 3: (fishy style)
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | . . . | . + .------+-------+------. . a | . . . | . . .. / . | . . . | . . .b . . | . . . | . * .------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

Now with three connected ER's you get (not surprisingly...):
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | . . . | . + .------+-------+------. . . | . . . | X . X. . * | . . . | . + .. . . | . . . | X . X------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

and finally with four:
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | * * * | . + .------+-------+------. . * | . . . | . * .. . * | . . . | . * .. . * | . . . | . * .------+-------+------X X . | . . . | X . X. . + | * * * | . + .X X . | . . . | X . X`

edit: said some wrong stuff...
havard
Havard

Posts: 378
Joined: 25 December 2005

Havard wrote:example 1: (skyscraper style)
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | . . . | * + .------+-------+------. . . | . . . | . * .. . a-----------b . .. . . | . . . | . * .------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

How is the elimination at r3c7 valid?

TIA, Ron
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:
Havard wrote:example 1: (skyscraper style)
Code: Select all
`X X . | . . . | X . XX X . | . . . | X . X. . + | . . . | * + .------+-------+------. . . | . . . | . * .. . a-----------b . .. . . | . . . | . * .------+-------+------. . . | . . . | . . .. . . | . . . | . . .. . . | . . . | . . .`

How is the elimination at r3c7 valid?

If you just completly ignore the ER in box 3, it becomes a normal ER elimination!

Havard
Havard

Posts: 378
Joined: 25 December 2005

Hi,

I discovered this technique a few weeks ago, before I found this post. I find this technique extremely useful and a lot easier to find than techniques like coloring and chaining. Because it is a pattern based technique I think it is nicer too. It is a nice addition to the arsenal of my little program!

Thank
henk

Posts: 18
Joined: 30 December 2005

### ER cracks Nightmare!

For a good ER example, take a look at the Sudo Cue Nightmare of April 17, 2006.

http://www.sudocue.net/forum/viewtopic.php?t=114

The ER is in B1, the strong link is in R4, eliminating <9> in R3C9.

Best wishes,
Keith
keith
2017 Supporter

Posts: 221
Joined: 03 April 2006

Rectangle of Empty Rectangles -- This is the only rectangle of four ERs I've seen that survives the application of other techniques. It's from #901 of the top1465.

Code: Select all
`000000042581000000000860000000400905000003000068007000053020084000000007200000100 6   #379 #79   |*137  #137  5    | 8    4    2 5    8    1    |#37    4    2    | 37   9    6#37   24   24   | 8     6    9    | 357  1357 13----------------+-----------------+--------------- 13   237  27   | 4     18   68   | 9    167  5 149  79   5    | 126   19   3    | 247  1267 8 149  6    8    | 1259  159  7    | 234  123  13----------------+-----------------+---------------#79   5    3    |#79    2    1    | 6    8    4 8    1    469  | 3569  359  46   | 235  235  7 2   #47  #467  |*3567 #3578 468  | 1    35   9 *   a   a   |*B/b B   .   | *   *   * .   .   .   | b   .   .   | 7   .   . A   .   .   | .   .   .   | 7   7   . -------------+-------------+------------  *   7   7   | *   .   .   | 7   . *   7   .   | *   .   .   | 7   7   . *   .   .   | *   .   7   | .   .   . -------------+-------------+------------  d   .   .   | C   .   .   | .   .   . .   .   .   | .   .   .   | .   7 *   D   D   |*C/c  c   .   | *   *   * for r1c4<>7 and r9c4<>7`

It is probably better viewed as an application of the Constraint (Sub)Sets technique. The candidates in four units of set A (b1, b2, b7, b8) are covered by four units of set B (r1, r9, c1, c4). If there were any, the candidates within set B not covered by set A could be excluded. The candidates in the intersection of set B units may also be excluded (r19c14).

Key steps in order to get to the above:
Code: Select all
`1. simple coloring: excludes 9 from r5c4 = 12692. ALS xz-rule: excludes 3 from r4c8 = 12367ALS sets A={r6c9}={13}, B={r6c8,r8c8,r9c8}={1235}, x=1, z=33. ALS xz-rule: excludes 2 from r5c2 = 2479ALS sets A={r1c3,r4c3}={279}, B={r1c2,r3c2,r4c2,r9c2}= {23479}, x=9, z=24. ALS xz-rule: excludes 4 from r5c2 = 479ALS sets A={r7c1,r9c2}=479 and B={r4c1,r5c1,r6c1,r4c2,r4c3}=123479, x=9, z=45. finned swordfish: excludes 7 from r4c1 = 1376. finned swordfish: excludes 7 from r5c1 = 1479`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

wow! Nice find Ronk!

Havard
Havard

Posts: 378
Joined: 25 December 2005

Just to show how small a world we live in. I think I have my Frankenfish finder functioning. When trying it against the 4-ER puzzle guess what I found? A Frankenfish eliminating the same candidates! This is not generally true, but it is in this case.
Code: Select all
`+----------------+------------------+----------------+|    6 *379  *79 |  -137  *137    5 |    8     4   2 ||    5    8    1 |    37     4    2 |   37     9   6 ||   37   24   24 |     8     6    9 |  357  1357  13 |+----------------+------------------+----------------+|   13 *237  *27 |     4    18   68 |    9   167   5 ||  149  *79    5 |   126    19    3 |  247  1267   8 ||  149    6    8 |  1259   159    7 |  234   123  13 |+----------------+------------------+----------------+|   79    5    3 |    79     2    1 |    6     8   4 ||    8    1  469 |  3569   359   46 |  235   235   7 ||    2  *47 *467 | -3567 *3578  468 |    1    35   9 |+----------------+------------------+----------------+`

So I guess Frankenfish also eat empty rectangles.

P.S. I wonder if we can somehow distinguish between Empty Rectangles, the technique, from empty rectangles, the box/box grouped stronglink. I know I was confused when I first looked at Ron's puzzle.
Mike Barker

Posts: 458
Joined: 22 January 2006

Mike Barker wrote:I think I have my Frankenfish finder functioning. When trying it against the 4-ER puzzle guess what I found? A Frankenfish eliminating the same candidates!

You've found a smaller and simpler combo of constraint sets that I haven't coded yet ... and didn't see either.

Mike Barker wrote:
Code: Select all
`+----------------+------------------+----------------+|    6 *379  *79 |  -137  *137    5 |    8     4   2 ||    5    8    1 |    37     4    2 |   37     9   6 ||   37   24   24 |     8     6    9 |  357  1357  13 |+----------------+------------------+----------------+|   13 *237  *27 |     4    18   68 |    9   167   5 ||  149  *79    5 |   126    19    3 |  247  1267   8 ||  149    6    8 |  1259   159    7 |  234   123  13 |+----------------+------------------+----------------+|   79    5    3 |    79     2    1 |    6     8   4 ||    8    1  469 |  3569   359   46 |  235   235   7 ||    2  *47 *467 | -3567 *3578  468 |    1    35   9 |+----------------+------------------+----------------+`

The candidates in set A (c2, c3, c5) are covered by set B (r1, b4, r9). Therefore, candidates in set B not covered by set A may be excluded.

Weve seen this before in this generalized form ...
Code: Select all
` . . . | . | . | X  X  *  . . . | . | . | X  X  *  . . . | . | . | X  X  * -------+-------+---------  . . . | . | . | |  |  .  * * * | * X * | X  X  *  . . . | . | . | |  |  . -------+-------+---------  . . . | . | . | |  |  .  * * * | * X * | X  X  *  . . . | . | . | |  |  . `
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

An example of how ER's can interact with grouped strong links, taken from Myth Jellies POM challenge:

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   . | .   2   . | .   2   2 | +-----------+-----------+-----------+ | .   .   . | .   .   . | 2   .   . | | .   .   . | 2   .   . | .   .   . | | 2   .   . | .   .   . | .   .   . | +-----------+-----------+-----------+ `

These eliminations can be showed with 2 ER's and one grouped strong link like this:
Code: Select all
`+-----------+-----------+-----------+ | .  -2-  2 | .   2   2 | .   2   2 | | .  -2-  2 | .   2   2 | .   2   2 | | .   b   b-------a   . | .   .   . | +-----------+-----------+-----------+ | X   2   X | X   2   X | .   2   2 | | .   2+  2 | .   2+  2 | .   2   2 | | X   2   X | X   2   X | .   2   2 | +-----------+-----------+-----------+ | .   .   . | .   .   . | 2   .   . | | .   .   . | 2   .   . | .   .   . | | 2   .   . | .   .   . | .   .   . | +-----------+-----------+-----------+ `

Havard
Havard

Posts: 378
Joined: 25 December 2005

### Empty rectangles

Hi, a question about them, i understand in the original diagrams by Havard that "a,b" must be a strong link but not why "b" and "*" need to be in the same row as well, the diagrams are from the empty rectangle link in the chopsuey e-mail at the top of the collection of solving techniques. I was asked to add my email to the original thread and hopefully ive managed to do that! Thanks Thomas
thomas

Posts: 5
Joined: 14 February 2006

PreviousNext