Isolated Subpuzzles and Local Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Postby RW » Wed Nov 12, 2008 12:32 pm

Red Ed wrote:Is the following what's meant by "isolated subpuzzle" ...:?:
(Assumption: the original puzzle has >0 solutions.)

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.

Wouldn't this be true for the unsolved cells in any puzzle with >0 solutions, also those with an unique solution?'

To me it seems an ISP is simply a deadly pattern or a collection of intersecting deadly patterns.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Red Ed » Wed Nov 12, 2008 1:16 pm

RW wrote:Wouldn't this be true for the unsolved cells in any puzzle with >0 solutions
Yes. Let C be a set of cells and all the candidates within them, and let ~C be all the other cells and their candidates. Your statement is a direct consequence of the fact that C is an ISP (by my definition) iff ~C is an ISP, together with the observation made two posts ago that the collection of solved cells is an ISP. [EDIT: erm, that "fact" assumes that ~C has been cleared of C-candidates.]
, also those with an unique solution?
I don't understand the distinction you're trying to draw there.

To me it seems an ISP is simply a deadly pattern or a collection of intersecting deadly patterns.
No. Or at least, not by the definition that I proposed and you quoted above. By that definition at least, any individual solved cell is an ISP in its own right but is obviously not a deadly pattern.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Wed Nov 12, 2008 1:52 pm

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.

Back in 2006, RW wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Allan Barker » Wed Nov 12, 2008 3:04 pm

Glyn wrote:coloin I'm sure Allan will be flexible as to what is discussed here. The focus on one aspect in Denis' thread was causing it to bloat.

Yes, think of me as an isolated sub-moderator for this thread.

Glyn wrote:Allan Barker DPB? --- Pierre?:)

Seems uniqueness has not been guaranteed.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby DonM » Wed Nov 12, 2008 4:22 pm

Allan Barker wrote:
Glyn wrote:coloin I'm sure Allan will be flexible as to what is discussed here. The focus on one aspect in Denis' thread was causing it to bloat.

Yes, think of me as an isolated sub-moderator for this thread.

Glyn wrote:Allan Barker DPB? --- Pierre?:)

Seems uniqueness has not been guaranteed.


Then bring down the hammer O Great & Wondrous Isolated Sub-Moderator!:D
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby Allan Barker » Wed Nov 12, 2008 5:26 pm

To me it seems an ISP is simply a deadly pattern or a collection of intersecting deadly patterns.
No. Or at least, not by the definition that I proposed and you quoted above. By that definition at least, any individual solved cell is an ISP in its own right but is obviously not a deadly pattern.[/quote]

This is exactly one of my observations, looking at the logical structure (set, constraints, or what), a single and a UR have the same properties, once uncovered they both clear all rows, cols, boxes, and cells that they sit in, and thereafter they are isolated from the puzzle. They both represent "solutions" to a puzzle. Referring only to multiple soltuion puzzles, in this picture, before and after a puzzle is solved we have:

single ---> assigned candidate
UR ----> isolated UR region (e.g. multiple 'assigned' candidates)

Then how to relate this to the use of uniqueness? (here I am very much an amateur).
Imagine two URs from two puzzles, the one on the left has 1 solution, and the one on the right has 2 solutions. Before the puzzles are solved, the potential URs are connected to lots of other logic

Code: Select all
   1 solution    2 solution (C = some candidates)
  --------------------------
    C C            C
    C UR           C UR C
    C C  C           C  C


What is the logical difference in the environments surrounding the two different potential URs? Does this relate to "local uniqueness"? Can UR1.1, a good example of local uniqueness, be discussed or recast in the view?

PS. I have changed the thread title to" isolated subpuzzles and local uniqueness" That seems broad enough to burn up some neurons. In that light I would hope David could return some of his thoughts and arguments as they fit this subject better. I apologize, my internet access is somewhat restricted right now, and out of sync as I'm on the other side of the globe (I assume).
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby RW » Wed Nov 12, 2008 8:12 pm

Red Ed wrote:
, also those with an unique solution?
I don't understand the distinction you're trying to draw there.

I was thinking of what Allan said in the first post:
Allan Barker wrote: 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", then it would make more sence with the rest of the first post in this thread and the rest of the discussion. This definition is not true for the unsolved cells in a puzzle with an unique solution.

Allan Barker wrote:
Code: Select all
   1 solution    2 solution (C = some candidates)
  --------------------------
    C C            C
    C UR           C UR C
    C C  C           C  C
What is the logical difference in the environments surrounding the two different potential URs? Does this relate to "local uniqueness"?

The first UR-pattern has max 3 true candidates and min 5 false candidates (candidates that cause a contradiction and leave the puzzle with 0 solutions). The false candidates may be removed by logic. The second UR-pattern has 8 true candidates and no false candidates.

Also, the first pattern must have at least one true candidate y (not part of the UR) in one of the cells. In the second pattern, all candidates except the two UR-digits are false and can be removed by logic.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby denis_berthier » Wed Nov 12, 2008 9:24 pm

What about these purely factual definitions:

Definition: 2 disjoint sets of candidates are uncoupled if no candidate of one is nrc-linked to any candidate of the other.
Remarks:
This definition implies that the two sets lie in disjoint sets of cells.
As usual in my approach, solved values play no direct role in these definitions. They are supposed to be used to eliminate all the candidates nrc-linked to them. Similarly, singles are supposed to produce a solved value. This allows to eliminate uninteresting cases.
It is obvious that, if two sets are uncoupled, then the corresponding parts of the puzzle can be solved independently.


Definition: a non-empty set of candidates is isolated if it is uncoupled with the set of all the other candidates.
Definition: a non-empty pattern of non-single candidates is absolutely isolated if, whenever it appears in a partiallly solved puzzle, it is uncoupled with the set of all the other candidates.


This definition of absolute isolation obviously applies to the following usual pattern with 4 cells in two rows, 2 columns and 2 blocks:
12 12
12 12

and to the following one (6 cells in 3 rows, 3 columns, 3 blocks, 1 tower), already mentioned in a post above:
12 12.....
.....12 12
12......12



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?
- does any case of uncoupled non-empty sets of candidates contain an absolutely isolated pattern?
- is any case of uncoupled non-empty sets of candidates made only of absolutely isolated patterns?
- does absolute isolation always imply multiple solutions?
- in this case, how are different solutions related? is it always by mere local (independent) renamings within each of the isolated sets of candidates?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Red Ed » Wed Nov 12, 2008 9:38 pm

RW wrote:
Allan Barker wrote: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).

My take on "cleared" is:
  • Say that a "solution" to the ISP is any way of assigning exactly one candidate in each of its cells.
  • A candidate outside of the ISP is "cleared" if and only if the same value is seen by that candidate in every solution of the ISP.
In particular, consider UR1.1 with candidates {1,2} in r1c1, r1c4, r2c1 and {1,3} in r2c4. This clears {1,2} from the rest of r1 but clears nothing from r2, so is not (by my understanding) an ISP.

Allan, I'm disappointed that you didn't comment on my precise definition which I still believe coincides with your notion of ISP:
Red Ed wrote: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:?:
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Wed Nov 12, 2008 9:39 pm

PS: Denis, just seen that you posted. Sorry, out of time to reply this morning:(

PPS: okay, a quick question. "nrc-linked" means ... what?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby denis_berthier » Wed Nov 12, 2008 10:06 pm

Red Ed wrote:PS: Denis, just seen that you posted. Sorry, out of time to reply this morning:(

PPS: okay, a quick question. "nrc-linked" means ... what?


"nrc-linked" defines the purely factual situation corresponding to the existence of a direct contradiction between 2 candidates. It is the main super-symmetric auxiliary predicate built on the basic ones.

Definition: two candidates n1r1c1 and n2r2c2 are nrc-linked if they are different and:
- either n1=n2 and the 2 rc-cells r1c1 and r2c2 see each other
- or n1 <> n2 and r1c1 = r2c2
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby RW » Thu Nov 13, 2008 2:14 am

denis_berthier wrote: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!
denis_berthier wrote:- does any case of uncoupled non-empty sets of candidates contain an absolutely isolated pattern?
- is any case of uncoupled non-empty sets of candidates made only of absolutely isolated patterns?

Not sure if I undestand these questions correctly,but if I do, then the answer is Yes.

denis_berthier wrote:- does absolute isolation always imply multiple solutions?

Yes.
denis_berthier wrote:- in this case, how are different solutions related? is it always by mere local (independent) renamings within each of the isolated sets of candidates?

No. It is by swapping the digits within the different units. If there is more than 2 digits, this cannot be done by only renaming:
Code: Select all
1 2 3     2 3 1
-----  =  -----
2 3 1     1 2 3


Red Ed wrote: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).

Sorry the unclearness. When I say " all false candidates are cleared", I mean that all candidates that may be shown to lead to an invalid puzzle (0 solutions) using whatever brute force method available are eliminated. If this is done and you are still left with unsolved cells, then these cells make up an ISP.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Thu Nov 13, 2008 2:58 am

RW wrote:However, the amount is huge!

I think that is understating it !
We know the 2-clue unavoidable situation at least.........

This is the pencil mark problem.......of "how" to remove the invalid candidates which lead to a zero solution. I refered to them as "virtual" candidates [as opposed to real candidates] they are indeed false. They cannot be removed by simple techniques in many cases.

OT but of note.

The SK loop was first described in the Easter Monster puzzle. It can be described as the removal of the "virtual" candidates in the pm grid of the 16 clue base subpuzzle of the EM Puzzle. Thats why the 16 clue base of the EM puzzle [empty central box] has ~0.5 million sols and not 4 million. here
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby RW » Thu Nov 13, 2008 3:15 am

coloin wrote:This is the pencil mark problem.......of "how" to remove the invalid candidates which lead to a zero solution. I refered to them as "virtual" candidates [as opposed to real candidates] they are indeed false. They cannot be removed by simple techniques in many cases.

If nothing else works, list all solutions and remove all candidates that don't appear in any of them.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Red Ed » Thu Nov 13, 2008 4:52 am

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.
      I wonder which interpretation, if either, Allan meant?

      Allan seemed to say that any single was an ISP. That's true in my definition, but not in yours.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to Advanced solving techniques