The Hidden Logic of SudokuDenis BerthierOnline Supplementsx2y2belts 
© Denis Berthier. All the material in this page and the pages it gives access to are the property of the author and may not be republished or reposted without his prior written permission. 
1) INTRODUCTIONThe rules presented here were inspired by Steve's beautifully symmetric pattern in his attack on EasterMonster, here: http://www.sudoku.com/boards/viewtopic.php t=5600&postdays=0&postorder=asc&start=75 (2=7)r13c2=(2&71&6)r56c2=(1&6)r79c2(1&6)r8c13=(1&62&7)r8c45=(2&7)r8c79(2&7)r79c8=(2&71&6)r45c8=(1&6)r13c8(1&6)r2c79=(1&62&7)r2c56=(2=&7)r2c13). (OK, the beauty is in the pattern on the grid, not in Steve's syntax!!). Some parts of this introduction may become clearer after you've read further on, but I didn't want to overload the definitions with too many comments. As Steve has not yet provided a formal general definition of his pattern, I'm not sure my definitions correspond to what he meant. Indeed, they clearly don't, if we consider his first definition with all the intermediate cells in the central "tower" and central "floor" (such as (2&71&6)r56c2). Others before me have noticed that these intermediate cells played no role in justifying Steve's eliminations. And, when I speak of beauty, I mean it becomes really beautiful when these parasitic cells have been expurgated from the pattern. EasterMonster (EM) is one of the most famous puzzles. Discovered by JPF and published the 7th of April 2007 on the Sudoku Payer's Forum, it has long been considered as the hardest puzzle and it is still considered as one of the few hardest known puzzles:
In "The Hidden Logic of Sudoku" (HLS), I indicated that EasterMonster cannot be solved by any known set of resolution rules. Several other examples have been produced that satisfy the same "pattern" (without the parasitic cells), e.g.  the 178 variations on the EM core configuration, to be found in Coloin's first post on this page: http://www.sudoku.com/boards/viewtopic.php?t=5591&start=105  the 14 from Ocean  not from the 411 list of patterns starting with a fish (normal for ocean) but from another list of 23 (thanks ronk for the reference), here: http://www.sudoku.com/boards/viewtopic.php?p=48076#48076 It may be interesting to know that their Sudoku Explainer ratings vary from 9.5 to 9.9: 100000002030040050006000700000103000040080090000405000007000100080030040200000006 100000002030040050006000700000104000080070040000508000007000600050030080200000001 100000002030040050006000700000103000040060080000904000007000100050090030200000006 100000002030040050006000700000103000080070030000508000007000600050030080200000001 100000002030040050006000700000104000040070080000905000007000600050090030200000001 100000002030040050006000700000104000080070040000503000002000600040050030700000001 100000002030040050006000700000104000080090040000508000002000100050030080700000006 100000002030040050006000700000103000080050040000409000007000100040030080200000006 100000002030040050006000700000104000050020040000503000002000600040080030700000001 100000002030040050006000700000103000040020030000504000007000600050080040200000001 100000002030040050006000700000103000040070080000405000007000600080050030200000001 100000002030040050006000700000103000050070040000408000002000100040080030700000006 100000002030040050006000700000103000050070080000504000007000600040050030200000001 100000002030040050006000700000104000080020040000508000002000600040030080700000001  and the 3 from gsf's list (including EM) identified by Champagne (thanks Mike for the reference): 500000009020100070008000300040600000000050000000207010003000800060004020900000005 11.4 # # m_b_metcalf 500000009020100070008000300040002000000050000000706010003000800060004020900000005 # StrmCkr 11.4 # 100000002090400050006000700050903000000070000000850040700000600030009080002000001 # JPF 04/07/01 (Easter Monster) 11.4 # I've checked that the two definitions I'll give soon produce the right eliminations in these examples (I'ven't checked the 178 variations though). Now, several interpretations and justifications of Steve's eliminations have already been proposed, in terms of Hidden Pairs Loops, of "double" AICs, of chains of AAAALSs, of matrices,… There's nothing wrong in these interpretations, but considering the beauty of Steve's pattern, none of these explanations is really satisfying  at least for me. What I like in a resolution rule is its being fitted to its purpose: I don't like having to use a hammer to kill a fly. I wouldn't call Jellyfish a pattern that has degenerated into a Swordfish or two XWings. This is also why I like families of resolution rules of increasing complexities. Even if, someday, someone finds a RuleOfEverything subsuming all the known rules, players in the real world will always need the simple specialisations. Of course, even before this, what I like in a rule is its being clearly defined. I'm never satisfied with just a few examples. A few words on vocabulary:  I'm not using the word "loop" for the rules I'm going to define, because it is already too much overloaded (and as it has been used, it conveys the idea that the targets belongs to the pattern, which is never the case in my apprach and can't be the case here).  I'm not using the word "ring", although I did initially, because the patterns I'm going to define are not so rigid as may be suggested by "ring": they may have shapes that are not at all ringlike.  I'm using the word "belt", not thinking of the belt around our waists, but thinking of conveyor belts. Indeed, this is what the following x2y2belts do: they convey constraints, both ways.  I'm using the prefix "x2y2" because x2y2belts work much like xychains, but on pairs of cells, each pair with 2 leftlinking candidates and two right linking candidates  instead of just one of each in the case of xchains. 
2) DEFINING A RESOLUTION RULE FROM AN EXAMPLEFrom a given example, or even from a set of examples, defining a corresponding resolution rule is not obvious. I shall use Steve's pattern to illustrate this. I shall:  give a (non exhaustive) list of questions that must be answered in the process,  give not one but two interpretations of Steve's pattern,  issue three challenges to the puzzle creators. This is at least one positive aspect of using computers in Sudoku solving: when programming a rule, one has to answer each of the following questions. (The logical conditions I'll define for my interpretations can be understood as full formal specifications for an implementation.) Q1: transforming constants into variables Given one or several examples, it may seem easy to replace specific numbers, rows, columns and blocks by generic variables, but the relations they should have may then be ambiguous (e.g. is the fact that two candidates belong to both the same row and the same block meaningful?) Q2: optional and additional candidates A second group of two questions that are not obvious is: which candidates present in the example can be made optional? Which additional candidates can be allowed as optional candidates in each of the cells? I already gave an example in my book (and recently in the "fish" thread) of how to deal with this when I defined the nondegeneracy condition for Subset rules (Naked, Hidden and SuperHiddden or Fish). Even with this elementary example, things were not so obvious as it may seem. The following two interpretations of Steve's pattern I'll give below define both:  which candidates present in the example can be made optional,  which additional candidates can be optionally allowed. In the EM example, all the cells concerned by Steve's pattern have exactly three candidates. With my definitions, they may have 2, 3 or 4. Therefore, each interpretation is already a non obvious generalisation of the example. Q3: nondegeneracy conditions A third question is: what conditions should we put to on the global pattern to ensure that it doensn't degenerate into something else? I'll illustrate this with the condition preventing x2y2belts to degenerate into NakedQuads. Q4: generalising the overall pattern, changing its length A fourth question is: can the overall structure be generalised? Can it be included in a whole family of patterns (e.g. as xychains of different lengths are)? The following two interpretations allow longer belts, each with more different physical shapes than the previous one. None of the examples cited in this forum has longer belts. So this will be my first challenge to puzzle creators: can one build a puzzle with a belt of 6 crosses (see first definition of belts below)? Q5: is the pattern made of repeated building blocks, and which A fifth question, related to the previous one and still less obvious, is: what are the building blocks of the overall structure? The following two interpretations rely on different building blocks (crosses vs x2y2segments). The second is a priori more general than the first. Nevertheless, none of the examples cited in this forum satisfies the second but not the first. I haven't had time to look for examples of the second that wouldn't be examples of the first. This will be my second challenge to puzzle creators: can one build a puzzle with an x2y2belt (see second definition below) that is not a belt of crosses (see examples of possible such patterns below)? Q6: classifying the pattern in some complexity hierarchy A sixth question is: where should the pattern be classified in a complexity hierarchy? Notice that this is not an abstract question independent of the rule formulation. When you want to state the rule precisely, you implicitly have to make such classification decisions. For instance, when I spoke of nondegenerating into NakedQuads (NQ), it means I observed that a first tentative definition R subsumed NQ and produces NQ eliminations even when NQ was deactivated. Therefore, after checking that R was more general than NQ, I had to give R a higher complexity than NQ. But I also had to introduce a nondegeneracy condtion in R. R doesn't subsume the Hidden or SuperHidden counterparts of NQ: HQ or SHQ (Jellysfish), but as HQ and SHQ are related to NQ via symmetry and supersymmetr, R must be given a higher complexity than these rules. Of course, this is not enough to fully classify R, say in my set of rules, but this entails that it has to be above my level L4_0, which reduces the problem to classifying R in relation to the xytonrczt family. Finally, this is not a question of generalising the pattern, but it arises naturally: does the presence of this pattern imply a high ER rating? As all the known examples do, this is my third challenge: can we find a puzzle with this pattern (in either the simpler or more complex forms) with low ER? Or can we prove that it does imply a high ER? 
3) FIRST INTERPRETATION of STEVE's EXAMPLE:

e (f) c' (d') 

a (b) c (d) 
(a) b (c) d 

(e) f (c') d' 
4) SECOND INTERPRETATION of STEVE's EXAMPLE: X2Y2BELTSThe building blocks are now considered to be "x2y2segments". For the purposes of the following definitions, a cell will not be designated as usual (as r1c1) but as r1c1b1 (block coordinate added). Definitions:  a rowblock is the intersection of a row and a block,  a colblock is the intersection of a column and a block,  a segment is either a rowblock or a colblock. Definition: x2y2segment: An x2y2segment is a segment with two distinguished cells C1=r1c1b1 and C'1=r'1c'1b'1 called its ends (although they don't have to be the physical ends, they are the conceptual ends). These data must satisfy the following conditions on their candidates:  the contents of C1 and C'1 are respectively {a1 (b1) c1 (d1)} and {(a1) b1 (c1) d1}, where:  a1, b1, c1, d1 are all different,  parentheses mean optional. For reasons that will appear soon:  a1 and b1 are called the leftlinking candidates,  c1 and d1 are called the rightlinking candidates. The basic property of an x2y2segment is that if none of its leftlinking candidates is true in any of its two cells, then each of its rightlinking candidates must be true in one of its two cells. An x2y2segment is associated with the formal predicate x2y2segment(type1, r1, c1, b1, r'1, c'1, b'1, a1, b1, c1, d1), where type1 is row or col, depending on the type of the underlying segment. Definition: chainable x2y2segment: Two x2y2segments x2y2segment(type1, r1, c1, b1, r'1, c'1, b'1, a1, b1, c1, d1) and x2y2segment(type2, r2, c2, b2, r'2, c'2, b'2, a2, b2, c2, d2) are said chainable if: {c1, d1} = {a2, b2} as sets and eiter of the following sets of conditions is true:  type1=type2=row, r1=r2, b1<>b2,  type1=type2=col, c1=c2, b<>b2,  type1= row, type2=col, b1=b2,  type2= row, type1=col, b1=b2,  type1=type2=row, r1<>r2, b1=b2,  type1=type2=col, c1<>c2, b=b2, Remarks:  if two x2y2segments are chainable, then the reversed segments taken in reversed order are chainable,  notice that the last two cases introduce completely new possibilities that were not available in the "belt of crosses" view. The basic property of chainable x2y2segments is what I call the x2y2transfer principle (a natural generalisation of the classical xytransfer principle): if none of the leftlinking candidates of the first x2y2segment is true in any of its two cells, then each of the rightlinking candidates of the second x2y2segment must be true in one of its two cells. This can be extended to seqences of chainable x2y2segments. Code: xytransfer principle: if not x1 then y1 then not x2 then y2 then not x3 then y3 .... x2y2transfer principle: if neither of x1 x'1 then both of y1 and y'1 then neither of x2 x'2 then both of y2 y'2 then neither of x3 x'3 then both of y3 y'3 .... Reversed x2y2segment: it is the x2y2segment(type1, r'1, c'1, b'1, r1, c1, b1, b1, a1, d1, c1) Definition: x2y2belt An x2y2belt is a sequence of n different x2y2segments (n is called the length of the belt), S1, S2, ..., Sn, all different, such that (setting Sn+1=S1): for each k in {1, 2, ..., n}, Sk and Sk+1 are chainable. Remarks:  notice the circularity condition,  two consecutive rowblocks can be in the same block,  the length n doesn't have to be even,  if one defines the reversed belt as being the sequence of the reversed segments in the reversed order, then it is an x2y2belt. Definition: targets of an x2y2belt The targets of an x2y2 belt are the targets of each of its couples of consecutive (therefore chainable) x2y2segments (still setting Sn+1=S1). A target of two chainable x2y2segments is any of the values c1 and d1 (= a2 and b2) in any cell C that is not an end of either segment such that:  if type1=type2=row, r1=r2, b1<>b2: C belongs to the same row as both segments,  if type1=type2=col, c1=c2, b<>b2: C belongs to the same column as both segments,  if (type1=row & type2=col) or (type1=col & type2=row), b1=b2: C belongs to the same block as both segments,  if (type1=type2=row, r1<>r2, b1=b2) or (type1=type2=col, c1<>c2, b=b2): C belongs to the same block as both segments. x2y2belts theorem: Given an x2y2belt, any of its targets can be eliminated. The proof is essentially the same as for the previous definition of belts. It is based on iterating the x2y2tranfer principle in both directions and concluding as in the previous definition of belts and crosses. Remarks on the shape of the spine: Given an x2y2belt, we can define its spine more or less as previously (details are left to the reader or to a future post). With x2y2belts of length 4, the spine can only be a rectangle, but it can now be flat, as in the following example (the two rows cross the same blocks): II II With belts of length 6, the spine can have new different shapes, e.g. (with the leftmost three segments in the same block, 2 horizontal and one vertical in between): III III I I I I I II with cells in the leftmost block distributed like this: r1.c1ar2.c2ar1.c1b r1.c1ar2.c2ar1.c1b r2.c2b or  r3.c3ar3.c3b r3.c3ar2.c2br3.c3b Moreover we can now have belts of odd length, such as (with the leftmost two segments parallel and in the same block: II II I I I I I II with cells in the leftmost block distributed like this: r1.c1ar2.c2a r1.c1ar2.c2a  or  r2.c2ar2.c2b r2.c2ar2.c2b Question: can one build a puzzle with an x2y2belt with any of these spines? As of today, no example has been found. See the discussion here: http://www.sudoku.com/boards/viewtopic.php?t=5894&postdays=0&postorder=asc&start=0 