The Empty Rectangle (ER)

Advanced methods and approaches for solving Sudoku puzzles

Re: Empty rectangles

Postby Havard » Mon Jul 03, 2006 9:42 pm

thomas wrote: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


Hi Thomas!

I think you are a bit confused about something here. The * marks the elimination which is at the intersection of "b" and the ERI line. Hence the * will always line up with the "b", since the "b" (partly) decides where "*" goes.

Still confused? You could try this one about strong links: http://forum.enjoysudoku.com/viewtopic.php?t=3326

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

The empty rectangle is an X-Wing

Postby msd1107 » Wed Sep 13, 2006 8:39 pm

I have to admit that I didn't get what the empty rectangle was on first reading. But some time later, I came back and vaguely understood it. When I documented it in my solutions document, then I began to see the implications. Recently, I revised the documentation on X-Wings to include this result, with the result being some new insights into X-Wings.

What follows is an extract from the documentation. Sorry that the format is different from what normally appears here, but I am an old time Fortran programmer. Comments are welcome.

........................

First, a word about conventions. Unknown numbers are denoted by capital letters toward the end of the alphabet, usually X, Y, Z, W, V or U. Each unknown X will be in a row and column, where the row is A, B, C, or D and the column is I, J, K, or L. Row numbering starts at the top left of the grid. Due to the symmetry of Sudoku, a row can be a column and a column can be a row. Thus if X is at A,I (row A, column I), it could also be at I,A (row I, column A).

..........................

Another technique is called X-Wing. Here look for two columns (rows) of a number in different blocks that have just two instances of the number (strongly linked or conjugates), and have them in the same row (column). The numbers will form what looks like a rectangle. You can then exclude other instances of the number occurring in the same row (column).

Here is why. Assume X is in A,I, B,I, A,J, and B,J and columns I and J have only two instances of X (are strongly linked or conjugates). If A,I is X, then B,I is not X (strong link), A,J is not X (only one X in the row), and B,J is X (strong link). If A,I is not X, then B,I is X (strong link), B,J is not X (only one X in a row), and A,J is X (strong link). In each case, X appeared once in row A and once in row B so can be removed from any other column in rows A and B. An X-Wing is a member of the general class of X-Cycles, that of degree 4. That means that it takes four cells in a loop to define the X-Cycle of degree 4. The general theory of X-Cycles is a subset of the conclusions we can draw from X-Wings.

X-Wing can be extended to what is called a Swordfish, a six-sided figure. Assume the number is X, and X is only in rows A and B in column I. Also, X is only in rows B and C in column J. And, finally, X is only in rows A and C in column K. If this is true, extra Xs in the rows A, B, or C but not in columns I, J, or K can be excluded. You can interchange rows and columns. A swordfish is minimally defined by the above described six points, which form a 3X3 grid of points. A swordfish can have the minimum six (of nine) points, or it can have seven points, eight points, or all nine points. But no matter how many points are defined in the 3X3 matrix, the extra X’s in the rows A, B, or C but not in columns I, J, or K can be excluded.

Here is why. Start with the six point Swordfish defined above. Assume X is at A,I. Then X is not at B,I, X is at B,J, X is not at C,J, X is at C,K, and X is not at A,K. If X is not at A,I, X is at B,I, X is not at B,J, X is at C,J, X is not at C,K, and X is at A,K. In either case, there is one X in A, B, and C, so X cannot be in any other column of A, B, or C. If the swordfish has more than six points, then for what ever X in any row A, B, or C and column I, J, or K we pick, it excludes any other Xs in other columns of the row we picked. This reduces the puzzle to an X-Wing that disallows X in any other columns of the rows defining the X-Wing. A Swordfish can be hard to identify. The basic swordfish is also a member of the general class of X-Cycles, that of degree 6.

The extension of this Swordfish 3X3 grid to a 4X4 grid is called a Jellyfish. Here, two, three, or four numbers are on common rows (columns) and aligned on common columns (rows). The extra numbers in the columns (rows) can be excluded. Jellyfish are even harder to identify than Swordfish, and much more rare. The last extensions are a 5X5 grid called a Squirmbag, a 6X6 grid called a Whale, and a 7X7 grid called a Leviathan. Don’t bother looking for these. By the time you have filled in all the numbers that are highlighted red, these fishy configurations will have disappeared. And also, if there is a fishy pattern of degree N, there is another fishy pattern of degree 9-N (and minus the number of cells filled in for this number). So that implies that the largest pattern to look for is four, and this decreases depending on the number of cells filled in.

Another technique is called a modified X-Wing. A true X-Wing has four examples of a number X in the corners of a rectangle, with the Xs in either the columns or rows being the only two instances of that number (strongly linked or conjugates). The Xs can be in either two or four blocks.

Modified X-Wing Type A. If the pattern is such that the four Xs are in four different blocks, two columns (rows) have just two instances of X, then there is a modified X-Wing if the fourth instance of X is in a different row (column) than the first X. (The first three Xs are in A,I, B,I, A,J as an example, and the fourth X is in C,J where row C in the same group of rows in the block that contains row B). If this situation holds, then Xs in the block that holds B,I in row C can be removed, as well as the Xs in the block that holds C,J in row B. Here is why. Assume X is in B,I. Then X cannot be in row C of the block that contains X in row B, nor can X be in row B in the block that contains X in row C. And if X is not in B,I, then it is in A,I, it is not in A,J, and thus is in C,J. This excludes X in row C in the block that contains A,I as well as excluding X in row B in the block that contains C,J. In either case, the same Xs can be excluded.

There is a modified Swordfish Type A also. Taking the swordfish example above, assume the number is X, and X is only in rows A and B in column I. Also, X is only in rows B and C in column J. And, finally, X is only in rows A and D in column K where C and D are in the same block. Then extra Xs can be excluded in rows A and B, in row C in the block that has the X in row D, and in row D in the block that contains the X in row C.

Here is why. If X is at A,I, then X is not at A,J or B,I, X is at C,J and B,K and X is not at D,K. If X is not at A,I, X is at A,J and B,I, X is not at C,J or B,K and X is at D,K. In both instances there is one X in row A and B. If the third X is in row C (C,J), it excludes Xs in row C the block containing D,K as well as in row D of the block containing C,J. If the third X is in row D (D,K), it excludes Xs row D in the block containing C,J as well as in row C of the block containing D,K. Both cases are the same.

Jellyfish and Sqirmbags can appear in the Type A configuration also.

Modified X-Wing Type B. This pattern has the four Xs in two blocks, with two Xs in each of two rows (columns), but not necessarily in the same columns (rows). (Instead of a rectangle, the pattern looks like a trapezoid.) If this holds, then Xs in the third row (column) of both blocks can be removed. Here is why. If X is the first row (column) of the first block, then it is on in the second row (column) of the second block and vice versa. But because there is always an X in each block, there can be no Xs in the third row (column) of either block, so they can be removed. Note that because there has to be an X in the first and second row (column) of the two blocks, the third block can have Xs in only its third row (column), which would have forced the removal of the Xs in row (column) three of the first and second block.

Modified X-Wing Type C. This is called a finned X-Wing. In this case, there are the four Xs at the corners of a rectangle. One column (row) has only the two Xs, so is strongly linked. The other column (row) has one or more Xs in the same column (row) but in different row(s) (column(s)) in the same block as one of the Xs. If this is true, Xs in the row (column) and in the block that contains the extra Xs can be excluded. For instance, X is at A,I, A,J, B,I, and B,J, there are no extra Xs in column I, but there are possibly Xs in C,J and/or D,J where B, C, and D are in the same block. Then Xs at B,K and B,L where K and L are in the same block as J can be excluded. However, no Xs can be removed from row (column) A. And also, the X at B,J is optional. If it does not exist, the pattern is called a sashimi X-Wing (And note that this is a Type A X-Wing if there is one cell in the fin. A Type A X-Wing allows for more exclusions than a Type C X-Wing).

Here is why. Assume X is at A,I. Then X is not at A,J, and X has to be at one of B,J, C,J or D,J (X has to appear in the column). But then X cannot be at B,K or B,L. If X is not at A,I, then it is at B,I and thus cannot be at B,K or B,L. Both these cases are the same, so X can be excluded from B,K and B,L. Note that if the Xs are only in the B row and J column of the finned block this may become a Type D X-Wing.

Also note that Swordfish, Jellyfish, and Sqirmbags can be finned.

Modified X-Wing Type D. This is usually called the empty rectangle (and has been called a hinge pattern), but is actually a form of X-Wing. The following definition proceeds from the original work on empty rectangles. At the end, it shows how to use modified X-Wings to more easily identify the cell to exclude.

An empty rectangle is four cells in a block that do not contain X and are in the shape of a rectangle. From this nothingness beginning, it may be possible to exclude an X elsewhere in the puzzle.

Let us start with a block which contains rows A, B, and C and columns I, J, and K. There are three general forms of an empty rectangle in the block. The first form of an empty (of X that is) rectangle is empty cells at A,I, A,J, B,I, and B,J together with their three rotations and reflections. The second form of an empty rectangle is empty cells at A,I, A,K, B,I, and B,K together with their three rotations and reflections. The third form of an empty rectangle is empty cells at A,I, A,K, C,I, and C,K.

Now draw two perpendicular lines through the block such that neither line goes through an empty cell and remember the cell where the lines intersect. In the first case above, the lines are in row C and column K and the intersecting cell is at C,K. In the second case above, the lines are in row C and column J and the intersecting cell is at C,J. In the third case above, the lines are in row B and column J and the intersecting cell is at B,J. Each of these perpendicular lines must contain an X in the block with the empty rectangle and there must be at least two Xs in the block, but X does not have to appear in the intersecting cell. Following X-Wing terminology, the Xs in the block not at the intersecting cell are fins. If the intersecting cell does not contain X, it is the Sashimi version.

Assume the intersecting cell is at B,J, although the technique works for any configuration (Note that there does not have to be an X at B,J). Next, look in all the cells of column J (or row B) for X. For each X found, look across its row (column) for a strong link on X. If such a strong link is found, look in its column (row) for an X at row B (column J). If such a configuration is found, then we can exclude a cell. Starting at B,J, assume we found an X at B,L, another X in a strong link in column L at D,L, and the last X at D,J. Now, this looks like an X-Wing but with two fins in the last box. But instead of excluding Xs outside the rectangle, we will exclude an X in the rectangle, the X at D,J.

Here is why. Assume D,J is not X, The link between D,J and B,J is not strong, so any X in column (row) J in the box could be X. Likewise, the link between D,J and D,L is not strong so that D,L could be X or not. Then the strong link at B,L could be X or not, and any of the cells in row (column) B in the block could be X. Now assume D,J is X. Then X cannot be in column (row) J in the box. D,L is not X so B,L is X (strong link). Then X cannot be in row (column) B in the box either. This means that there are no Xs in the box, which is impossible. Thus D,J is not X and can be excluded. This is a lot of work to exclude one digit.

Possibly an easier way to recognize this is to look for four Xs in a rectangle in four boxes. If two Xs are strongly linked, look on the other side of the rectangle for Xs in an +, T, or L (or their rotated forms) shape in the box. If you find this then the other X opposite the strong link is the candidate for elimination. Or even more general, look for a strong link on X. Find a third cell with X on a common row or column, and another box with the Xs only on the row of one X and the column of another X. Then exclude the X opposite the strong link.

Now, after all this, it turns out Type D and some Type C X-Wings are the same. Look at the Type C X-Wing. If there are extra Xs in the block with the fin other than the fin and the row (column) that sees the other X in the strong link, then this analysis does not hold. As before, whether X is at A,I or B,I, X cannot be at B,K or B,L. If the cell at A,J is X, then X is not at B,J, C,J or D,J. And A,I is not X, B,I is X (strong link), and X cannot be in B,J, B,K, or B,L. So X cannot be in the block containing B,J which is impossible so X is not in A,J either. Now look at the Type D X-Wing. If X is at D,L, then X is not at D,J and one of A,J, B,J, or C,J must be X. But then X cannot be at B,I or B,K. And if X is not at D,L it is at B,L so X cannot be in B,I or B,K which is the same as before. As before, X is not at D,J. So both Type D and some Type C X-Wings can have the single cell in the weak link opposite the strong link excluded, as well as the two (possible) Xs in the fin in line with the second cell of the strong link.

...............................
msd1107
 
Posts: 1
Joined: 12 September 2006

Question on ERs - for whoever

Postby mona187 » Mon Sep 25, 2006 5:20 pm

Hi, there. I know I’m coming into this late, but I have been trying to acquire a few new techniques and some of the exchanges in this forum are obviously intended for people who already know what they’re talking about. This is the first I’ve read about empty rectangles that contained an explanation – thanks Havard, I’ve read your postings before and really appreciate them – so I wanted to give it a try on a puzzle I’ve been stuck on.

One thing the example didn’t address is if, in identifying the ER, it matters that the correct value for the cell has already been determined. Also, can the candidate eliminated be in the same block as the ER?

Below are the top blocks of the puzzle in question. I’m looking only at 2s here. There are 2 strong links, Aa and Bb. In ER1, I know the value in r1c7 is 9. Can it still be a part of the ER? If so, then can I eliminate the 2 in r1c8 based on the Aa link?

Same situation in ER2, with the known value being r2c9. I get 2 eliminations this way, in r2c8 and r1c6 (based on Bb). Is this correct?

Thanks for your help!


Code: Select all

ER1

A126     7     158   |  126     236     1234   |  *9    -234   *158
a126     689   4     |  1269    2369    5      |   68   +23     7
 3       569   159   |  7       8      B1249   |  *56   b24    *156
-----------------------------------------------------------------


ER2

A126     7     158   |  126     236    -1234   |   9    +234    158
a126     689   4     |  1269    2369    5      |  *68   -23    *7
 3       569   159   |  7       8      B1249   |  *56   b24    *156
-----------------------------------------------------------------



Aa, Bb   conjugate pairs/strong links on 2
*        empty rectangle (2)
+        Empty rectangle intersection
-        2 candidates to be eliminated
mona187
 
Posts: 4
Joined: 20 March 2006

Postby Havard » Mon Sep 25, 2006 10:01 pm

hi Mona!

Thanks for your kind words!

your *'s marking the empty rectangle is correct. (the point of the whole concept is to see the cells that does NOT contain the number you are looking at, in this case a 2) However, you can't eliminate in the same block as you have, so no, your examples are not correct. But you have understood the concept perfectly, so good luck with finding these little critters!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Tue Sep 26, 2006 12:42 am

Hi Mona,

While all four corner cells of a rectangle must be void of candidate X, candidate X must exist in at least two rows and at least two columns of the remaining cells.

Code: Select all
|  *  X  *
|  .  X  .
|  *  X  *
+----------
... is not an empty rectangle


|  *  .  *
|  X +X  .
|  *  X  *
+----------
... IS an empty rectangle

This pattern was first known as a hinge ... which better communicated the above requirement.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Tue Sep 26, 2006 2:47 pm

ronk wrote:Hi Mona,

While all four corner cells of a rectangle must be void of candidate X, candidate X must exist in at least two rows and at least two columns of the remaining cells.

Code: Select all
|  *  X  *
|  .  X  .
|  *  X  *
+----------
... is not an empty rectangle


|  *  .  *
|  X +X  .
|  *  X  *
+----------
... IS an empty rectangle

This pattern was first known as a hinge ... which better communicated the above requirement.


sorry ronk, but I would disagree. Both examples you gave are perfectly good ER's. (it does not matter WHERE the candidates are in an ER, as long as they NOT are in the empty-bit. (we both know that ER's are really grouped strong links within a box, and you can think of the grouping in your first example as the middle column vs. the middle row (saying the box is in the top left corner: r2c2 = r2c13) ) However, it is not a useful ER since it is also a box-line. (but for people who want to look for ER's before box-line you would have to allow it):)
Havard
 
Posts: 377
Joined: 25 December 2005

Postby mona187 » Tue Sep 26, 2006 4:38 pm

Darn! I was really hoping my example was correct, since I was able to solve the puzzle with those eliminations! Must have been fluke, so back to square 1 – both figuratively and literally!

How about the candidate in my example ER2 in r1c6…can I eliminate it based on the Bb link, or must the strong link be entirely outside the block with the ER?
mona187
 
Posts: 4
Joined: 20 March 2006

Postby ronk » Tue Sep 26, 2006 7:21 pm

Havard wrote:
ronk wrote:
Code: Select all
|  *  X  *
|  .  X  .
|  *  X  *
+----------
... is not an empty rectangle

sorry ronk, but I would disagree. Both examples you gave are perfectly good ER's.

Sorry, Havard, but I would disagree. Just because a degenerate pattern B is the same as pattern A ... doesn't mean pattern A is properly called pattern B.

Using your logic many x-wings would be called swordfish instead ... even though it's a degenerate swordfish.

[edit: typo corrected]
Last edited by ronk on Tue Sep 26, 2006 7:51 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Tue Sep 26, 2006 10:40 pm

ronk wrote:Sorry, Havard, but I would disagree. Just because a degenerate pattern B is the same as pattern A ... doesn't mean pattern pattern A is properly called pattern B.

Using your logic many x-wings would be called swordfish instead ... even though it's a degenerate swordfish.


I generally agree with your statement, however, in this case, it is the definition of an ER we are talking about. The definition is: "if you can make a rectangle out of four squares in a Box that does NOT contain a spesific candidate, you have an empty rectangle. And hence both examples fit the definiton.:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Wed Sep 27, 2006 2:24 pm

Havard wrote:The definition is: "if you can make a rectangle out of four squares in a Box that does NOT contain a spesific candidate, you have an empty rectangle. And hence both examples fit the definiton.

No thanks. I'll stick with Rod Hagglund's original definition here for the hinge. He clearly described two "arms" ... one row arm and one column arm.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Wed Sep 27, 2006 8:23 pm

ronk wrote:
Havard wrote:The definition is: "if you can make a rectangle out of four squares in a Box that does NOT contain a spesific candidate, you have an empty rectangle. And hence both examples fit the definiton.

No thanks. I'll stick with Rod Hagglund's original definition here for the hinge. He clearly described two "arms" ... one row arm and one column arm.


whatever suits you best my friend!:)
There is however nothing original about Rod Hagglund's hinge, since grouped strong links was defined a long, long time before that.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby wapati » Wed Sep 27, 2006 8:53 pm

If Hinge covers all "usefull" cases of Empty Rectangle, then "Hinge"
would seem to take precedence .

If it does not...


Edited to add "usefull".
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby ronk » Tue Oct 03, 2006 2:30 pm

Havard wrote:There is however nothing original about Rod Hagglund's hinge, since grouped strong links was defined a long, long time before that.

I searched and found no posts before Dec 2005 -- on either this forum or the Programmers' Forum -- that contain the words "grouped" and "strong". However, that doesn't mean much since Rod Hagglund didn't use either of those words when defining his hinge.

So would you be so kind as to provide a link or two to that definition(s) made a long, long time ago?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Tue Oct 03, 2006 5:20 pm

Interesting with a bit of sudoku history! I found a post that inspired Jeff to write up about grouped X-cycles dating back to 9. august 2005. http://forum.enjoysudoku.com/viewtopic.php?p=6451 , and I would also mention Carcul's post here: http://forum.enjoysudoku.com/viewtopic.php?t=2384. Both beat Rod to it, one by a little less than a month, and the other by almost 5. I guess that must be said to be quite a lot in this very young and very quickly evolving science.:)
Havard
 
Posts: 377
Joined: 25 December 2005

A little off topic?

Postby keith » Fri Oct 06, 2006 12:05 am

While we all are doing searches on Sudoku history and granting credit:

This is, to me, the same as the hinge vs. empty rectangle debate.

"Strong Links for Beginners" names a "skyscraper". I saw a previous post, which I cannot now find, that called it a "fork".

Has someone researched the history of this pattern, two strong links that line up at one end?

Thank you,

Keith
keith
2017 Supporter
 
Posts: 215
Joined: 03 April 2006

Previous

Return to Advanced solving techniques