The New Sudoku Players' Forum

Website · by **denis_berthier** » Sat Feb 09, 2008 4:56 pm

X2Y2-BELTS

Introduction
This set of five posts was inspired by Steve's beautifully symmetric pattern in his attack on EasterMonster, here: [url]http://forum.enjoysudoku.com/viewtopic.php t=5600&postdays=0&postorder=asc&start=75[/url]
(2=7)r13c2=(2&7-1&6)r56c2=(1&6)r79c2-(1&6)r8c13=(1&6-2&7)r8c45=(2&7)r8c79-(2&7)r79c8=(2&7-1&6)r45c8=(1&6)r13c8-(1&6)r2c79=(1&6-2&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 the other posts, 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&7-1&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.

Several other examples have been produced that satisfy the same "pattern" (without the parasitic cells). AFAIK, this is the complete list as of today - which seems to show that this is a relatively rare pattern (the 178 variations on EM shouldn't really count for 178).
If you know more, it may be a good idea to complete this list.
- EM itself:
100000002090400050006000700050903000000070000000850040700000600030009080002000001

- the 178 variations on the EM core configuration, to be found in Coloin's first post on this page: [url]http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=105[/url]
(in my navigator, they appear in microscopic characters, but you can enlarge them by copying the list in any text editor)

- the 14 from Ocean - not from the 411 list of patterns starting with a fish (normal for ocean) but from another list of 23 here ([url]http://forum.enjoysudoku.com/viewtopic.php?p=48076#p48076[/url]) (thanks ronk for the references). It may be interesting to know that "Their Sudoku Explainer ratings vary from 9.5 to 9.9" (ronk):
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 chains, 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 X-Wings. This is also why I like families of resolution rules of increasing complexities. Even if, someday, someone finds a RuleOfEverything subsuming all 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.

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 rules 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 ring-like.
- 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 x2y2-belts do: they convey constraints, both ways.
- I'm using the prefix "x2y2" because x2y2-belts work much like xy-chains, but on pairs of cells, each pair with 2 left-linking candidates and two right linking candidates.

Website · by **denis_berthier** » Sat Feb 09, 2008 4:57 pm

DEFINING A RESOLUTION RULE FROM AN EXAMPLE

From 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 non-degeneracy condition for Subset rules (Naked, Hidden and Super-Hiddden 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: non-degeneracy 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 x2y2-belts to degenerate into Naked-Quads.

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 xy-chains 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 x2y2-segments). 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 x2y2-belt (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 non-degenerating into Naked-Quads (NQ), it means I observed that a first tentative definition R subsumed NQ and produces NQ eliminations even when NQ was de-activated. 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 non-degeneracy condtion in R.
R doesn't subsume the Hidden or Super-Hidden counterparts of NQ: HQ or SHQ (Jellysfish), but as HQ and SHQ are related to NQ via symmetry and super-symmetr, 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 xy-to-nrczt family.

Finally, this is not a question of generalising the pattern, but it arises naturally: do 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?

Website · by **denis_berthier** » Sat Feb 09, 2008 5:02 pm

FIRST INTERPRETATION of STEVE's EXAMPLE: CROSSES AND BELTS

The building blocks are considered to be "crosses".

Definition: a cross is defined by the following data and conditions:
- a block b1,
- a row r1 that intersects b1,
- a column c1 that intersects b1,
- the intersection of r1 and c1 is called the center of the cross (notice that it doesn't have to be the physial center of block b, it is a conceptual center (in EM it does always appear as the physical center),
- two different rows r1a and r1b that intersect b1,
- two different columns c1a and c1b that intersect b1,
- one of r1a or r1b may be equal to r1,
- one of c1a or c1b may be equal to c1,
- the four "ends of the cross" (r1.c1a, r1.c1b, r1.ac1, c1.bc1) must be different,
- the contents of (i.e. the candidates in) these four ends must be as follows:
r1.c1a = {na1 (nb1) nc1 (nd1)}
r1.c1b = {(na1) nb1 (nc1) nd1}
r1a.c1 = {nc'1 (nd'1) ne1 (nf1)}
r1b.c1 = {(nc'1) nd'1 (ne1) nf1}
where:
- { } means that the content of the cell is completely listed (nothing else allowed),
- na1, nb1, nc1 and nd1 are all different,
- nc'1, nd'1, ne1 and nf1 are all different,
- {nc'1, nd'1} = {nc1, nd1} as sets, i.e. either (nc'1=nc1 and nd'1=nd1) or (nd'1=nc1 and nc'1=nd1),
- na1 and nb1 are called the horizontal outer candidates (they correspond to the values that will be eliminated from row r1),
- ne1 and nf1 are called the vertical outer candidates (they correspond to the values that will be eliminated from column c1),
- nc1, nd1, nc'1, nd'1 are called the inner candidates (they correspond to the values that will be eliminated from block b1).

Notice how the compulsory and the optional candidates are defined.

Notice that, for all the crosses in EasterMonster, all the inner optional candidates are absent and all the outer optional candidates are present. EM is therefore a very special case.

Seen from the outside, inner candidates can be forgotten and the cross can be seen as a transfer mechanism for constraints, working in both directions:
- if none of the vertical candidates in the vertical branch is true, then both horizontal candidates in the horizontal branch are true,
- if none of the horizontal candidates in the horizontal branch is true, then both vertical candidates in the vertical branch are true.

The above cross is associated with the formal auxiliary predicate (defined by all the above conditions): cross(b1, r1, r1a, r1b, c1, c1a, c1b, a1, b1, c1, d1, c'1, d'1, e1, f1).

Definition: row-aligned crosses: two crosses cross(b1, r1, r1a, r1b, c1, c1a, c1b, a1, b1, c1, d1, c'1, d'1, e1, f1) and cross(b2, r2, r2a, r2b, c2, c2a, c2b, a2, b2, c2, d2, c'2, d'2, e2, f2) are said row-aligned if:
- they are in different blocks (b2 <> b1),
- they are centered in the same row (r1 = r2),
- they have the same set of horizontal outer candidates: {na2, nb2} = {na1, nb1} as sets.

By permuting rows and columns, one can define column-aligned crosses. More precisely:
Definition: column-aligned crosses two crosses cross(b1, r1, r1a, r1b, c1, c1a, c1b, a1, b1, c1, d1, c'1, d'1, e1, f1) and cross(b2, r2, r2a, r2b, c2, c2a, c2b, a2, b2, c2, d2, c'2, d'2, e2, f2) are said column-aligned if:
- they are in different blocks (b2 <> b1),
- they are centered in the same column (c2 = c1),
- they have the same set of vertical outer candidates: {ne2, nf2} = {ne1, nf1} as sets.

Definition: a spine for a belt of even length 2l is defined by the following data and conditions:
- a sequence of 2l cells such that, when repeating the first at the end of the list, two consecutive cells are alternatively in the same row and in the same column (these cells define the global structure of the belts to be defined below).
In the EM example, the spine is: r2c2, r2c8, r8c8, r8c2.

Definition: a belt of even length 2l is defined by the following data and conditions:
- a spine for a belt of length 2l,
- for each of the cells in the spine, a cross centered on this cell,
- when repeating the first cross at the end of the list, consecutive crosses are alternatively row-aligned and column-aligned.

Theorem: Given a belt, one can eliminate:
- in each of its blocks: any inner candidate that is not in one of the cells at the ends of the cross,
- in each central row of consecutive row-aligned crosses: any horizontal outer candidate (they are the same for the two crosses) that is not in the horizontal ends of any of the two row-aligned crosses,
- in each central column of consecutive column-aligned crosses: any vertical outer candidate (they are the same for the two crosses) that is not in the vertical ends of any of the two column-aligned crosses.

Proof: I'll write the proof only for belts of length 4
Suppose we start with two row-aligned crosses and let the four crosses be:
(cross b1, r1, r1a, r1b, c1, c1a, c1b, a1, b1, c1, d1, c'1, d'1, e1, f1)
(cross b2, r2, r2a, r2b, c2, c2a, c2b, a2, b2, c2, d2, c'2, d'2, e2, f2)
(cross b3, r3, r3a, r3b, c3, c3a, c3b, a3, b3, c3, d3, c'3, d'3, e3, f3)
(cross b4, r4, r4a, r4b, c4, c4a, c4b, a4, b4, c4, d4, c'4, d'4, e4, f4)

(cells are noted as e.g. r1a.c1b, with a dot between the row and the column)

1) Elimination of inner candidates nc1 and nd1 in block b1:
If neither of nc1, nd1 is in {r1c1a, r1c1b}, we have successively:
{r1.c1a, r1.c1b} = {a1, b1} as sets
neither of na1 or nb1 is in {r2c2a, r2c2b} (remember that n2=n1)
{r2.c2a, r2.c2b} = {ne2, nf2} as sets
neither of ne2, nf2 is in {r3.c3a, r3.c3b} (remember that r3=r2)
{r3.c3a, r3.c3b} = {nc3, nd3} as sets
....
{r1.ac1, r1.bc1} = {nc1, nd1} as sets

Similarly, if neither of nc1, nd1 is in {r1.ac1, r1.bc1}, then {r1c1a, r1c1b} = {nc1, nd1} as sets

So, if none of nc1, nd1 is in any of the two ends of a branch of the cross in b1, then the two are in the ends of the other branch.
Moreover, if nc1 but not nd1 is in a branch, nc1 can't be in the other. Therefore, nd1 must be in the other.
In any case, each of nc1 and nd1 must be in one of the four ends of the cross in b1.
Whence the eliminations of nc1 and nd1 in b1.

2) Elimination of the outer horizontal candidates na1 and nb1 (= na2 and nb2) in row r1
The proof is similar:
If neither of na1, nb1 is in {r1c1a, r1c1b}, then the two must be in {r2c2a, r1c2b} (= {r1c2a, r1c2b})
Similarly, if neither of na1, nb1 is in {r2c2a, r1c2b}, then the two must be in {r1c1a, r1c1b}.

In any case, each of na1 and nb1 must be in one of the four horizontal ends of the two crosses aligned on row r1.
Whence the eliminations of na1 and nb1 in the other cells in r1.

3) Elimination of the outer vertical candidates ne1 and nf1 in column c1
Transpose the previous proof.

Notice that this proof doesn't take full advantage of the xy-transfer principle that will be seen in the next approach.
But, from the point of view of patterns, this is certainly the most beautiful and the easiest to find of the two.
It is also the most efficient in computation time.

Remarks on the shape of the spine:

With belts of length 4, the spine can only be a rectangle. Moreover, as floors and towers can be permuted, there is essentially one spine.

With belts of length 6, the spine can (must) have different shapes (but always with spine ends in different blocks), e.g.:

Code: Select all: I------------------------I I I I I I-------------I I I I I I I----------I

I therefore repeat here my first challenge to puzzle creators: can one build a puzzle with a belt of 6 crosses with the above spine?

Website · by **denis_berthier** » Sat Feb 09, 2008 5:10 pm

SECOND INTERPRETATION of STEVE's EXAMPLE: X2Y2-BELTS

The building blocks are now considered to be "x2y2-segments".
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: x2y2-segment:
An x2y2-segment 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,
- parens mean optional.
For reasons that will appear soon:
- a1 and b1 are called the left-linking candidates,
- c1 and d1 are called the right-linking candidates.

The basic property of an x2y2-segment is that if none of its left-linking candidates is true in any of its two cells, then each of its right-linking candidates must be true in one of its two cells.

An x2y2-segment is associated with the formal predicate x2y2-segment(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 x2y2-segment: Two x2y2-segments x2y2-segment(type1, r1, c1, b1, r'1, c'1, b'1, a1, b1, c1, d1) and x2y2-segment(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 x2y2-segments 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 x2y2-segments is what I call the x2y2-transfer principle (a natural generalisation of the classical xy-transfer principle): if none of the left-linking candidates of the first x2y2-segment is true in any of its two cells, then each of the right-linking candidates of the second x2y2-segment must be true in one of its two cells. This can be extended to seqences of chainable x2y2-segments.

Code: Select all: xy-transfer principle: if not x1 then y1 then not x2 then y2 then not x3 then y3 .... x2y2-transfer 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 x2y2-segment: it is the x2y2-segment(type1, r'1, c'1, b'1, r1, c1, b1, b1, a1, d1, c1)

Definition: x2y2-belt
An x2y2-belt is a sequence of n different x2y2-segments (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 x2y2-belt.

Definition: targets of an x2y2-belt The targets of an x2y2 belt are the targets of each of its couples of consecutive (therefore chainable) x2y2-segments (still setting Sn+1=S1).
A target of two chainable x2y2-segments 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.

x2y2-belts theorem: Given an x2y2-belt, 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 x2y2-tranfer principle in both directions and concluding as in the previous definition of belts and crosses.

Remarks on the shape of the spine:

Given an x2y2-belt, we can define its spine more or less as previously (details are left to the reader or to a future post).

With x2y2-belts 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):

Code: Select all: I----------------------I I----------------------I

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):

Code: Select all: I----I-------------------I I----I--------I I I I I I I----------I with cells in the leftmost block distributed like this: -r1.c1a---------r2.c2a---------r1.c1b- -r1.c1a---------r2.c2a---------r1.c1b- -----------------r2.c2b----------------- or -------------------------------------- -r3.c3a-------------------------r3.c3b- -r3.c3a---------r2.c2b---------r3.c3b-

Moreover we can now have belts of odd length, such as (with the leftmost two segments parallel and in the same block:

Code: Select all: I------------------------I I-------------I I I I I I I----------I with cells in the leftmost block distributed like this: -r1.c1a---------------------------r2.c2a- -r1.c1a-------------------------r2.c2a- ----------------------------------------- or --------------------------------------- -r2.c2a---------r2.c2b------------------ -r2.c2a------------------------r2.c2b-

I therefore repeat here my second challenge to puzzle creators: can one build a puzzle with an x2y2-belt with any of these spines?

by **coloin** » Sat Feb 09, 2008 5:51 pm

- the 178 variations on the EM core configuration, to be found in Coloin's first post on this page:

Actually this is the tip of the iceberg, the underwater bit consisting of 100000 puzzles or more, yes more.

The reason we got the hard ones was related to the fact there were so many puzzles with the 16-clue base - you can see that I used the 8 associated essentially different varients.

There are more of these bases too, giving rise to more hard puzzles, by finding all the ways to complete the central box.

Actually we cheated, we found all the ways to fill the central box, and then we found all the ways to remove all the superfluos clues.

It was a neat one.

C

by **ronk** » Sat Feb 09, 2008 6:44 pm

coloin wrote:
- the 178 variations on the EM core configuration, to be found in Coloin's first post on this page:

Actually this is the tip of the iceberg, the underwater bit consisting of 100000 puzzles or more, yes more.

Indeed. Using just the one template below, I was able to generate 9500+ minimal non-isomorphic puzzles during a few overnight runs.

Code: Select all: 1 . . | . . . | . . 2 . 34589 . | 34589 . . | . 34589 . . . 6 | . . . | 7 . . -------------+---------------+------------- . 34589 . | O O O | . . . . . . | O O O | . . . . . . | O O O | . 34589 . -------------+---------------+------------- 7 . . | . . . | 6 . . . 34589 . | . . 34589 | . 34589 . . . 2 | . . . | . . 1 1) At template cells with digit(s), the puzzle clue must be one of the digits 2) At cells marked 'O', any clue may be added to obtain a minimal puzzle 3) No clues are permitted in other cells

Website · by **denis_berthier** » Sun Feb 10, 2008 9:11 am

ronk wrote:Using just the one template below, I was able to generate 9500+ minimal non-isomorphic puzzles during a few overnight runs.
Code: Select all
1 . . | . . . | . . 2 . 34589 . | 34589 . . | . 34589 . . . 6 | . . . | 7 . . -------------+---------------+------------- . 34589 . | O O O | . . . . . . | O O O | . . . . . . | O O O | . 34589 . -------------+---------------+------------- 7 . . | . . . | 6 . . . 34589 . | . . 34589 | . 34589 . . . 2 | . . . | . . 1 1) At template cells with digit(s), the puzzle clue must be one of the digits 2) At cells marked 'O', any clue may be added to obtain a minimal puzzle 3) No clues are permitted in other cells

Of course, not all the consistent specialisations of this template will have an x2y2-belt, unless you add conditions: modulo a renaming of the digits, you can always put r2c2=9, r2c8=5 (as in EM) but then, if r8c2=3 is chosen, 5 must somehow be eliminated from r1c2, r3c2, r2c1, r2c3. A way of doing this must be chosen. I guess this is what you did in your generation process.

From this template, it also appears that for any x2y2-belt living on the same cells as in EM, no candidate that was not present in EM is possible in the cells belonging to the x2y2-belt (e.g. 2 in r1c2 or 7 in r3c2). This template can't (directly) help answer Q1.

I wonder if, using a smart modification of this template, we couldn't produce an x2y2-belt of length 6: keeping row 1 and column 1 unchanged, deleting the data in blocks 6, 8 and 9 and adding some data in block 5. But there are so many possibilities and I'm so totally unexperienced in puzzle creation that I quickly gave up.

by **ronk** » Sun Feb 10, 2008 12:51 pm

denis_berthier wrote:Of course, not all the consistent specialisations of this template will have an x2y2-belt, unless ...

I have no idea what an x2y2-belt is, but every valid puzzle generated according to the rules of my posted template contains a k-loop (as in the Easter Monster).

Website · by **denis_berthier** » Sun Feb 10, 2008 2:34 pm

ronk wrote:[every valid puzzle generated according to the rules of my posted template contains a k-loop (as in the Easter Monster).

I wasn't sure you were stating this (I modified your first rule accordingly, so that there is no ambiguity).
So, let's say we fix the first row as in EM. This adds no restriction on the puzzles generated, modulo a renaming of 4, 5, 9. We get the following template and rules:

Code: Select all: 1 . . | . . . | . . 2 . . 9 . . | 4 . . | . 5 . . . 6 | . . . | 7 . . -------------+---------------+------------- . 3458 . | O O O | . . . . . . | O O O | . . . . . . | O O O | . 3489 . -------------+---------------+------------- 7 . . | . . . | 6 . . . 3458 . | . . 34589 | . 3489 . . . 2 | . . . | . . 1 1) At template cells with digit(s), there must be a puzzle clue, chosen among the digits 2) At cells marked 'O', any clue may be added to obtain a minimal puzzle 3) No clues are permitted in other cells

From this, it can be seen that, in the first row, 2, 7, 3, 8 must play the same roles in the pattern in this puzzle as in EM.
We also have, in particular:
- 2 doesn't appear in r1c2, 7 doesn't appear in r3c2
- 3 and 8 both appear in r2c1, r2c3, r2c7, r2c9: this is because no other clue can eliminate them.

Such specifities are less clear for the other cells of the pattern. But given the restrictions on the clues in your rules, they seem likely to be true.

In relation to my question Q2, and to make it simple, would your algorithm be able to find a puzzle among those it generates, in which the pattern had a cell with 2 or 4 candidates? (This is allowed by the general logic of x2y2-belts - whose definition you can find in a previous post).

by **ronk** » Sun Feb 10, 2008 7:15 pm

denis_berthier wrote:So, let's say we fix the first row as in EM. This adds no restriction on the puzzles generated, modulo a renaming of 4, 5, 9.

Being aware of that "trick", I'm not sure why I didn't use it here.

In relation to my question Q2, and to make it simple, would your algorithm be able to find a puzzle among those it generates, in which the pattern had a cell with 2 or 4 candidates?

Alas, I have no simple way to do this within a generator.

by **coloin** » Mon Feb 11, 2008 12:38 pm

Maybe this will help - to try to find the puzzle......with the double sk-loop
EM

Code: Select all: +---+---+---+ |1..|...|..2| |.9.|4..|.5.| |..6|...|7..| +---+---+---+ |.5.|9.3|...| |...|.7.|...| |...|85.|.4.| +---+---+---+ |7..|...|6..| |.3.|..9|.8.| |..2|...|..1| +---+---+---+

Yes there are many templates with 16 clues

I dont think we systematically explored them all !!!!

The hardest puzzles came from 16-subpuzzle templates with around 400000-800000 solutions.

Exchanging two clues and row swapping in a corner box modifies the template.

Code: Select all: a.......a .a..B..a. ..a...a.. ...XXX... .B.XXX.B. ...XXX... ..a...a.. .a..B..a. a.......a is different from a.......a .a..B..a. ..a...a.. ...XXX... .B.XXX.B. ...XXX... ..a.....a .a..B..a. a.....a..

The solitary clues in the boxes 2,4,6 and 8 can be anywhere - but this dramatically influences the solutions for the 16-template.

If you are saying that the positions of the B clues are integral for the pattern then this reduces the options. If not then.....

Moving the solitary B clues around has the effect of changing the shape of a corner boxe.

Isomorphic symmetry is induced if the solitary clues are the same value, or if the solitary clues are in the same row.

It is quite possible that the template exists, if it has more than 1M grid completions the number of puzzles will be less, but it might have THE puzzle.

As you say these may be the options

Code: Select all: 1 . . | . . . | . . 2 . . 9 . . | 4 . . | . 5 . . . 6 | . . . | 7 . . -------------+---------------+------------- . 3458 . | O O O | . . . . . . | O O O | . . . . . . | O O O | . 3489 . -------------+---------------+------------- 7 . . | . . . | 6 . . . 3458 . | . . 34589 | . 3489 . . . 2 | . . . | . . 1

I do have a program which will identify different and equivalent subpuzzles.

Here the the 8 different templates assoc with EM

Code: Select all: 1.......2.9.4...5...6...7...5.......................4...2...6...3...9.8.7.......1 - 676286 sol. 1.......2.9.4...5...6...7...5.......................4...7...6...3...9.8.2.......1 - 691248 sol. 6.......2.9.4...5...1...7...5.......................4...2...6...3...9.8.7.......1 - 708196 sol. 6.......2.9.4...5...1...7...5.......................4...7...6...3...9.8.2.......1 - 682164 sol. 1.......2.9.4...5...6...7...5.......................4.7.....6...3...9.8...2.....1 - 678104 sol. [ EM] 1.......7.9.4...5...6...2...5.......................4.7.....6...3...9.8...2.....1 - 696188 sol. 6.......2.9.4...5...1...7...5.......................4.2.....6...3...9.8...7.....1 - 688096 sol. [04/13-1600] 6.......2.9.4...5...1...7...5.......................4.7.....6...3...9.8...2.....1 - 685046 sol.

Have you any intuition as to which template it might be ?

As a complete punt in the dark.....have a look in this puzzle !

Code: Select all: 6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1 # 60691 FNP C21.m/M2.1.505197 coloin-04/13-1600# ER 11.4 [it took 10 hours]

C

Website · by **denis_berthier** » Mon Feb 11, 2008 1:50 pm

Indeed, I thought we could start from another core pattern than that used for EM, e.g. a pattern with clues given in the blocks where the crosses making the x2y2-belt live, e.g. in some diagonals of these blocks (and perhaps additional data outside these blocks).
(Here, we can discard any condition on number of clues, ER, even minimality).

Code: Select all: X . . | . . . | . . X . X . | . . . | . X . . . X | . . . | X . . ------------+-------------+------------- . . . | . . X | X . . . . . | . X . | . X . . . . | X . . | . . X ------------+-------------+------------- . . X | X . . | . . . . X . | . X | . . . X . . | . . X | . . .

But I couldn't find manually values for these places consistent with the x2y2 constraints.

Perhaps the diagonals in the blocks should be chosen with different orientations.

by **ronk** » Mon Feb 11, 2008 1:56 pm

coloin wrote:As you say these may be the options
Code: Select all
1 . . | . . . | . . 2 . . 9 . . | 4 . . | . 5 . . . 6 | . . . | 7 . . -------------+---------------+------------- . 3458 . | O O O | . . . . . . | O O O | . . . . . . | O O O | . 3489 . -------------+---------------+------------- 7 . . | . . . | 6 . . . 3458 . | . . 34589 | . 3489 . . . 2 | . . . | . . 1

I do have a program which will identify different and equivalent subpuzzles.

Here the the 8 different templates assoc with EM
Code: Select all
[edit: first four deleted] 1.......2.9.4...5...6...7...5.......................4.7.....6...3...9.8...2.....1 - 678104 sol. [ EM] 1.......7.9.4...5...6...2...5.......................4.7.....6...3...9.8...2.....1 - 696188 sol. 6.......2.9.4...5...1...7...5.......................4.2.....6...3...9.8...7.....1 - 688096 sol. [04/13-1600] 6.......2.9.4...5...1...7...5.......................4.7.....6...3...9.8...2.....1 - 685046 sol.

The last three can be morphed to put clues 1, 2, 6 and 7 in the same cells ... while keeping an identical row 2 as well. IOW all four fit the template above.

morph wrote:
Code: Select all
1.......2.9.4...5...6...7...5.......................4.7.....6...3...9.8...2.....1 - 678104 sol. [ EM] 1.......2.9.4...5...6...7...5.......................8.7.....6...3...8.4...2.....1 - 696188 sol. 1.......2.9.4...5...6...7...8.......................3.7.....6...3...8.4...2.....1 - 688096 sol. [04/13-1600] 1.......2.9.4...5...6...7...4.......................8.7.....6...8...9.3...2.....1 - 685046 sol.

So in what way do they appear different to you?

by **coloin** » Tue Feb 12, 2008 3:16 am

Sorry, Ronk, but although they have the same template, they each have a different number of grid solutions.

You cant morph them into one another, if you could the grid solutions would be the same.

checking the grid solutions

Code: Select all: 676286 sol. 691248 sol. 708196 sol. 682164 sol. 678104 sol. 696188 sol. 688096 sol. 685046 sol.

here are the minlex versions of the subpuzzles [using gsfs prog] confirming all different.

Code: Select all: 000000000000000001000002000000030040000500600001007002000060030000400500070008009 000000000000000001000002000000030040000500600001007002000040030000600500070008009 000000000000000001000002000000030040000500600001007002000060050000400300070008009 000000000000000001000002000000030040000500600001007002000040050000600300070008009 000000000000000001000002000000030040000500600001007002000060500000400030070008009 000000000000000001000002000000030040000500600001007002000040500000600030070008009 000000000000000001000002000000030040000500600001007002000040300000600050070008009 000000000000000001000002000000030040000500600001007002000060300000400050070008009

EDIT - Indeed ronk - I do appreciate that the "different" template doesnt advance any towards what DB is attempting.

I perhaps see where you where going with the new configuration
B1245 and B5689....with a sk-loop
I couldnt find a puzzle with 3 solitary clues in B357.

Code: Select all: +---+---+---+ |1..|..6|...| |.2.|.5.|...| |..3|4..|...| +---+---+---+ |..6|..1|..7| |.5.|...|.8.| |4..|3..|9..| +---+---+---+ |..8|..9|3.6| |...|.8.|.2.| |...|7..|..1| +---+---+---+ SE 10.4

Code: Select all: +---+---+---+ |1..|4..|.7.| |.2.|.5.|...| |..3|..6|...| +---+---+---+ |4..|3..|..7| |.5.|...|.8.| |..6|..1|9..| +---+---+---+ |...|..9|1..| |...|.8.|.2.| |6..|7..|..3| +---+---+---+ SE 9.8

How far are these off ??

C

Website · by **denis_berthier** » Tue Feb 12, 2008 2:38 pm

As an example of an x2y2-belt with spine of length 6 on blocks 1 3 6 5 8 7, consider the following variant of EM:

Code: Select all: 100040600 090003050 006000001 080200006 400090080 000007100 700001040 050030009 002600000

After elementary propagation of constraints, we get a belt of 6 crosses:

Code: Select all: 1_______237_____3578____ | 4789____4_______2589____ | 6_______2379____2378 28______9_______478_____ | 178_____12678___3_______ | 2478____5_______2478____ 2358____2347____6_______ | 5789____2578____2589____ | 234789__2379____1_______ _________________________|__________________________|_________________________ 359_____8_______13579___ | 2_______15______45______ | 34579___379_____6_______ 4_______12367___1357____ | 135_____9_______56______ | 2357____8_______2357____ 23569___236_____359_____ | 3458____568_____7_______ | 1_______239_____2345____ _________________________|__________________________|_________________________ 7_______36______389_____ | 589_____258_____1_______ | 2358____4_______2358____ 68______5_______148_____ | 478_____3_______248_____ | 278_____1268____9_______ 389_____134_____2_______ | 6_______578_____4589____ | 3578____137_____3578____

Inner candidates:
- in blocks 1 3 6 8: 2 and 7
- in blocks 5 and 7: 1 and 6

Outer candidates:
- horizontal:
in blocks 1 and 3 : 4 and 8
in blocks 6 and 5: 3 and 9
in blocks 8 and 7 : 4 and 8
- vertical:
in blocks 3 and 6 : 3 and 9
in blocks 5 and 8 : 5 and 8
in blocks 7 and 1 : 3 and 4

The only problem with this example is that it degenerates when singles are applied. Nevertheless, I think it should illustrate the idea.
The question of finding a nondegenerate case is still open.