by 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.
...............................
