The Empty Rectangle (ER)

Advanced methods and approaches for solving Sudoku puzzles

Postby Mike Barker » Wed Mar 08, 2006 3:49 pm

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

Postby ronk » Wed Mar 08, 2006 4:41 pm

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

Postby Myth Jellies » Thu Mar 09, 2006 9:07 am

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

Postby ronk » Thu Mar 09, 2006 10:02 am

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

Postby Havard » Thu Mar 09, 2006 7:27 pm

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 . X
X X . | . . . | X . X
. . + | . . . | * + .
------+-------+------
. . . | . . . | . * .
. . a-----------b . .
. . . | . . . | . * .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .


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


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


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


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



edit: said some wrong stuff...
havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Thu Mar 09, 2006 8:56 pm

Havard wrote:example 1: (skyscraper style)
Code: Select all
X X . | . . . | X . X
X 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

Postby Havard » Thu Mar 09, 2006 9:07 pm

ronk wrote:
Havard wrote:example 1: (skyscraper style)
Code: Select all
X X . | . . . | X . X
X 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: 377
Joined: 25 December 2005

Postby henk » Fri Mar 17, 2006 8:10 pm

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!

Postby keith » Mon Apr 17, 2006 2:18 am

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: 212
Joined: 03 April 2006

Postby ronk » Tue May 09, 2006 8:35 pm

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 = 1269

2. ALS xz-rule: excludes 3 from r4c8 = 12367
ALS sets A={r6c9}={13}, B={r6c8,r8c8,r9c8}={1235}, x=1, z=3

3. ALS xz-rule: excludes 2 from r5c2 = 2479
ALS sets A={r1c3,r4c3}={279}, B={r1c2,r3c2,r4c2,r9c2}= {23479}, x=9, z=2

4. ALS xz-rule: excludes 4 from r5c2 = 479
ALS sets A={r7c1,r9c2}=479 and B={r4c1,r5c1,r6c1,r4c2,r4c3}=123479, x=9, z=4

5. finned swordfish: excludes 7 from r4c1 = 137
6. finned swordfish: excludes 7 from r5c1 = 1479
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Thu May 11, 2006 12:03 am

wow! Nice find Ronk!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Thu May 11, 2006 6:05 pm

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

Postby ronk » Thu May 11, 2006 7:21 pm

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

Postby Havard » Mon May 29, 2006 10:39 am

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: 377
Joined: 25 December 2005

Empty rectangles

Postby thomas » Mon Jul 03, 2006 8:53 pm

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

Return to Advanced solving techniques