The New Sudoku Players' Forum

[re'born]

What about these purely factual definitions...

Perhaps someone with some more graph theory background could correct me, but couldn't we rephrase Denis' definition in terms of graphs. At any given state of the puzzle, the vertices would be the candidates and two vertices have an edge between them if they are nrc-linked.

Two disjoins sets of candidates are uncoupled is then the same things as saying they lie in different connected components of the graph.

An isolated set of candidates is just a connected component of the graph. So singles, being nrc-linked to nothing, are always isolated.

A non-empty set of non-single candidates is absolutely isolated if whenever it appears in a partially solved puzzle, it is a connected component of the graph.

Is this interpretation correct?

[RW]

RW, thanks. If I understood you correctly then our proposals are:

• Ed-ISP iff:
  1. it's a set of cells, C, in a puzzle-in-progress, P, such that
  2. for each unit (row, column or box) of the grid, there are as many different cells in C as there are candidate-values in C.
  • RW-ISP iff:
    1. it's a set of multi-candidate cells, C, in a puzzle-in-progress, P (that has >0 solutions), such that
    2. assigning any individual candidate in C still leaves P with >0 solutions.

Yes, that is what I meant. Very good explanation of my version by the way, hadn't thought of putting it that way!

Allan seemed to say that any single was an ISP. That's true in my definition, but not in yours.

I guess my problem with this is that I don't like calling a single a "puzzle"...

RW

[Red Ed]

Definition: a non-empty set of candidates is isolated if it is uncoupled with the set of all the other candidates

This is nearly equivalent to my "Ed-ISP" proposal originally made about 12 hours earlier. My proposal assumes >0 solutions; Denis' does not. Denis' proposal assumes that the candidates outside of the isolated set have been "cleared"; mine does not. Denis' proposal is a better match for the English-language definition of "isolated"; mine is more like a "closed system" (to quote RW from 2006). But it seems that basically Denis and I are on the same page.

Two disjoins sets of candidates are uncoupled is then the same things as saying they lie in different connected components of the graph.

I don't think that's right. Consider A=1@r1c1, B=1@r1c9, C=1@r9c1. B is uncoupled from C, but they are in the same connected component.

[Allan Barker]

First, I would like to apologize to all that my focus is being affected by other urgent matters these last few days, in addition to the nomal time zone lag. My responsiveness is thererfore pretty bad.

Allan, I'm disappointed that you didn't comment on my precise definition which I still believe coincides with your notion of ISP:

ISP if and only if:

• it's a set of cells, C, and all the candidates within them;
• for each unit (row, column or box) of the grid, there are as many different cells in C as there are candidate-values in C.

What do you think

I sometimes have trouble between 2D and 3D. A simple unique rectangle occupies 4 cells, has 8 candidates, Just as the 8 candidates occupy 4 cells, the same 8 candidates occupy 4 row sets, 4 column sets, and 4 box sets. Thus, each of 16 sets has 2 candidates. Note in 2D, 2 different digits in a row occupy 2 row sets.

Does this tally with yours?

After an ISP clears its sets of other candidates, it no longer has any logical connection with the rest of the puzzle."

This definition is a bit vague, what is a "logical connection"? I think it should have said "After all false candidates in an ISP are cleared, no cells in the ISP are solved"

Hmm, I doubt that.

You and Allan are both guilty of imprecision in use of the phrases "clears its sets of other candidates" and "all false candidates in an ISP are cleared". "Cleared" needs a definition. You need to specify which candidates are eliminated (done, I think) and how (absolutely not done).

Definition: clears = eliminates.

As for how, I guess I'm guilty of more sink or swim explanations. Here is description of how. Look back at the first of the two images I posted, at the left structure, which has 8 bars and 8 candidates. These 8 candidates are part of a DR. They are positioned at the corner of a cube. The left diagram is a simple continuous nice loop made of 4 bivalve sets (colored) and 4 weak links (white). This will eliminate candidates in the 4 weak links. I can now draw 3 more nice loops among the same 8 candidates. Eventually all 16 sets occupied by the 8 candidates will be a weak link of same nice loop. This will eliminate all candidates that are in the 16 sets that are occupied by the 8 candidates that make up the DR. All 8 DR candidates remain intact. The 8 candidates in the DR now cannot see any other candidates in the puzzle. It is logically disconnected. A sinlge is exactly the same way.

I will go over more posts in the morning. Again apologies.

[re'born]

Two disjoins sets of candidates are uncoupled is then the same things as saying they lie in different connected components of the graph.

I don't think that's right. Consider A=1@r1c1, B=1@r1c9, C=1@r9c1. B is uncoupled from C, but they are in the same connected component.

Ah, yes. Thank you, Ed. Of course, nrc-linkage is not transitive.

[Edit: Deleted some nonsense...but RedEd saw it too quickly ]

[Red Ed]

Right then Allan, I'm convinced that your notion of "isolated sub-puzzle" coincides with Denis' definition (green) below:
(warning: my attempt at paraphrasing him)

• Denis-ISP if and only if:
  1. it's a set of cells, C, in a puzzle-in-progress, P, such that
  2. for each candidate in C, there is none of the same value in the same unit (row, column or box) outside of C.
  • Ed-ISP if and only if:
    1. it's a set of cells, C, in a puzzle-in-progress, P, such that
    2. for each unit (row, column or box) of the grid, there are as many different cells in C as there are candidate-values in C.
    • RW-ISP if and only if:
      1. it's a set of multi-candidate cells, C, in a puzzle-in-progress, P (that has >0 solutions), such that
      2. assigning any individual candidate in C still leaves P with >0 solutions.
      Now the $6.67e21 question: so what?
      If you were looking for a characterisation of "deadly patterns" or uniqueness tricks then, sadly, this ain't it.

[Red Ed]

I think isolated and absolutely isolated still make sense as I rephrased them.

Well certainly your "isolated" component is a well-defined concept, but I don't think it is strongly related to what Allan was trying to explain at the start of this thread.

[Allan Barker]

I have now had time to freshen up and take a better look. I think the right answers were posted even before my last hasty post.

Hey, RW, why didn't you say? Your notion of "closed system" seems to be exactly the same as Allan's "ISP". I like the terminology.

Closed implies that no patterns outside this system could affect the numbers within the system, and no numbers within the system could affect any numbers outside the system.

I took a look at RWs old post. This is exactly the same concept that I tried to express in terms of constraint set arrangements. Closed system is perhaps the best term of all. Sheesh, 2006, half way back to the big Su-Bang.

Right then Allan, I'm convinced that your notion of "isolated sub-puzzle" coincides with Denis' definition (green) below:
(warning: my attempt at paraphrasing him)

• Denis-ISP if and only if:
  1. it's a set of cells, C, in a puzzle-in-progress, P, such that
  2. for each candidate in C, there is none of the same value in the same unit (row, column or box) outside of C.
  • Ed-ISP if and only if:
    1. it's a set of cells, C, in a puzzle-in-progress, P, such that
    2. for each unit (row, column or box) of the grid, there are as many different cells in C as there are candidate-values in C.
    • RW-ISP if and only if:
      1. it's a set of multi-candidate cells, C, in a puzzle-in-progress, P (that has >0 solutions), such that
      2. assigning any individual candidate in C still leaves P with >0 solutions.

Of these 3 views I prefer Red Ed's as it is easy (for me) to see what makes these structures into closed systems. I.e., overlapping locked multiples that are locked in all their rows, columns, boxes. This is indeed a clear picture.

Now the $6.67e21 question: so what?
If you were looking for a characterisation of "deadly patterns" or uniqueness tricks then, sadly, this ain't it.

Well, yes, I initially pointed out this property as I thought it might relate or lead to ways of testing/observing local uniqueness. This is precisely addressed in RWs 2006 thread. Perhaps you can remit the money, $6.67e21, to him.

Pure musing (I guess I have not learned my lesson)

- can we make a list of all the possible cases of absolutely isolated patterns?

This has been done up to a certain size of unavoidable sets. I guess there must exist a limited amount of possible sets, so theoretically they could all be listed. However, the amount is huge!

but I've seen at least one example of a minimal unavoidable set (and therefore "deadly pattern") that has all nine digits in it! It covered 55 cells.

even 60 cellshere...
JPF

As the ISPs grow in size, would not a blank grid (no givens) be the ultimate closed system, described by the clear definitions given in this thread? Then, how many givens does it take to be able to prevent the formation of a closed system, or destroy the closed system? (We already know this to be 17?)

For the theoretically minded, perhaps using the clear definitions presented here, can it be shown that 16 candidates are not sufficient to prevent a closed system? Has this already been proved, or does it remain an observable fact?
.

[Myth Jellies]

Isolatable Pair

Isolatable Pairs always come in pairs. An Isolatable Pair equals two paired Isolatable Sets

Isolatable Set

An Isolatable Set consists of a set of cells and their solved and unsolved candidates.

Two Isolatable Sets that form an Isolatable Pair are defined by having the following two properties....

1) The Isolatable Pair forms an entire puzzle.

2) No candidate digit in one Isolatable Set shares a group with a candidate of the same digit in the other Isolatable Set.

Theorem: If a puzzle can be split into an Isolatable Pair, then each Isolatable Set of the pair must resolve down to a valid unique solution all by itself for the puzzle to resolve into a unique solution.

The proof of this is pretty simple--I'll leave it go for now. From here the uniqueness pantheon can be worked out fairly easily. Rename as you wish; I'm just using these as reference labels.

By the way, it really should be RW's UR1.1 pattern.

[RW]

but I've seen at least one example of a minimal unavoidable set (and therefore "deadly pattern") that has all nine digits in it! It covered 55 cells.

even 60 cells here...
JPF

As the ISPs grow in size, would not a blank grid (no givens) be the ultimate closed system, described by the clear definitions given in this thread? Then, how many givens does it take to be able to prevent the formation of a closed system, or destroy the closed system? (We already know this to be 17?)

Yes, a blank grid would fulfill those definitions. However, the 55 and 60 cells examples by Red Ed and JPF are special, because they are minimal unavoidable sets. (Don't know if the term minimal closed system is neccessary, or if it even could be used here.) This means that if you assign any valid value to any one cell in the set, the rest of the cells will be solved. Trying to put it as Red Ed would:

• Minimal unavoidable set if and only if:
  
  1. it's a set of multi-candidate cells, C, in a puzzle-in-progress, P (that has >0 solutions), such that
  2. assigning any individual candidate in C leaves P with exactly 1 solution.

RW

[denis_berthier]

Right then Allan, I'm convinced that your notion of "isolated sub-puzzle" coincides with Denis' definition (green) below:
(warning: my attempt at paraphrasing him)

• Denis-ISP if and only if:
  1. it's a set of cells, C, in a puzzle-in-progress, P, such that
  2. for each candidate in C, there is none of the same value in the same unit (row, column or box) outside of C.
  This is almost equivalent. But my definitions differ from this on three points:
  - they consider only candidates; as usual in Sudoku, decided cells play no part in them;
  - they exclude trivial cases; in particular, a blank grid or a pair are not absolutely isolated patterns;
  - they apply only after the trivial eliminations and assertions (singles) have been done.
  As a result, they focus the search on interesting cases.
  
  Vocabulary: I don't like "subpuzzle", because, as was already said by others, it's been used with different meanings.
  
  

  Questions (some of them may be obvious, I've not had time to think of them).
  - can we make a list of all the possible cases of absolutely isolated patterns?

  
  This has been done up to a certain size of unavoidable sets. I guess there must exist a limited amount of possible sets, so theoretically they could all be listed. However, the amount is huge!

  
  RW, if your answer remains unchanged after the above precisions, how can we hope to write all the rules?

[RW]

Questions (some of them may be obvious, I've not had time to think of them).
- can we make a list of all the possible cases of absolutely isolated patterns?

This has been done up to a certain size of unavoidable sets. I guess there must exist a limited amount of possible sets, so theoretically they could all be listed. However, the amount is huge!

RW, if your answer remains unchanged after the above precisions, how can we hope to write all the rules?

Not sure what rules you wish to write...

I believe we could write rules that define a large part of all possible minimal unavoidable sets, actually most of them are already defined. But to list all varieties would be as smart as trying to list all possible forcing chains - it would make such a huge list that in the end it would be totally useless.

RW

[denis_berthier]

Questions (some of them may be obvious, I've not had time to think of them).
- can we make a list of all the possible cases of absolutely isolated patterns?

This has been done up to a certain size of unavoidable sets. I guess there must exist a limited amount of possible sets, so theoretically they could all be listed. However, the amount is huge!

RW, if your answer remains unchanged after the above precisions, how can we hope to write all the rules?

Not sure what rules you wish to write...
I believe we could write rules that define a large part of all possible minimal unavoidable sets, actually most of them are already defined. But to list all varieties would be as smart as trying to list all possible forcing chains - it would make such a huge list that in the end it would be totally useless.
RW

Indeed, I meant all the rules, based on absolutely isolated patterns and allowing eliminations.
I don't know if this is equivalent to all the rules you're mentioning.

[RW]

Indeed, I meant all the rules, based on absolutely isolated patterns and allowing eliminations.
I don't know if this is equivalent to all the rules you're mentioning.

By my definition of ISP, it is equivalent.

I don't think we can ever make a comprehesive list of all possible eliminations related to uniqueness technique (which is essentially the same as your question, right?). This is also the reason why these techniques always have been my main interest. As they cannot all be defined, there is always something new to find. For each new unavoidable set defined, or even better, each pattern of cells that is proven to contain at least one unavoidable set, a whole new arsenal of techniques is defined. This is because uniqueness technique is essentially very different from other techniques. Other techniques define ways of spotting contradictions. Uniqueness technique defines new contradictions.

RW

[denis_berthier]

Other techniques define ways of spotting contradictions. Uniqueness technique defines new contradictions.

In all the cases, you have to define the patterns that lead to contradictions and then you have to spot these patterns.

It's probably true that there are more rules for uniqueness, but they may also be so specific that trying to use them all would be very counter productive.