Isolated Subpuzzles and Local Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Mon Nov 10, 2008 9:55 pm

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

RedEd, JPF, thanks for these very interesting examples with non isomorphic solutions.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby David P Bird » Tue Nov 11, 2008 2:20 am

RW thanks once again for setting me right on your trail-blazing work and the terms to use.

I've deleted my original post accordingly, and happily accept that none of it was very original.
Last edited by David P Bird on Wed Nov 12, 2008 9:09 am, edited 2 times in total.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby ronk » Tue Nov 11, 2008 2:20 am

Isolated subpuzzles? How about independent subpuzzles instead?

There is at least a mathematical concept for independence.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Tue Nov 11, 2008 3:05 am

David P Bird wrote:By way of explanation, I've currently got time constraints and I find it's often quicker to work from first principles than to try to find previous work. It usually means I get a much better grasp on a topic too.

No problem. I know there's too much stuff hidden in these forums for anyone to know about it all (except perhaps Pat...). And I would recommend everyone to work out these answers themselves instead of just looking for old research, because as you say, you get a much better grasp of the topic that way.

David P Bird wrote:There are some subtleties with reverse bug deductions. Given this pattern in two boxes:
123 12
123 123

We have the inferences that the four cells must contain BOTH a (1) and a (2) because we know that there are no possible 1/3 or 2/3 unavoidable sets. However unless we assume uniqueness we can't rule out twin solutions with a 1/2 unavoidable set.

I'm not sure how this relates to the reverse-BUG... The reverse-BUG does not care about candidates in unsolved cells, it is found by looking at only the solved cells. Anyway, I don't think we should hi-jack this thread for discussion about this, perhaps you can clarify the question in the reverse-BUG thread or a pm.

David P Bird wrote:Did you ever explore unavoidable sets with three cells in each house each with the same three candidates?

Yes, see http://forum.enjoysudoku.com/viewtopic.php?t=4432

more on similar patterns in these threads:
http://forum.enjoysudoku.com/viewtopic.php?t=3056
http://forum.enjoysudoku.com/viewtopic.php?t=3210

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

Postby re'born » Tue Nov 11, 2008 4:59 am

ronk wrote:Isolated subpuzzles? How about independent subpuzzles instead?

There is at least a mathematical concept for independence.


Isolation is also a mathematical concept.:idea:
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ronk » Tue Nov 11, 2008 6:16 am

re'born wrote:
ronk wrote:Isolated subpuzzles? How about independent subpuzzles instead?

There is at least a mathematical concept for independence.

Isolation is also a mathematical concept.:idea:

I googled "math isolation" before my prior post, so was already aware of isolated point ... and thought about writing "independence is at least a common mathematical concept."

Let me put it this way. I first learned of independence, in the mathematical sense, when solving simultaneous equations of independent variables in high school algebra. Through the rest of high school and four plus years in electrical engineering courses, I don't recall encountering isolation anything or isolated anything, in the mathematical sense of course.

IMO independent subpuzzles is more appropriate than isolated subpuzzles.:idea:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Tue Nov 11, 2008 7:42 am

ronk wrote:
re'born wrote:
ronk wrote:Isolated subpuzzles? How about independent subpuzzles instead?

There is at least a mathematical concept for independence.

Isolation is also a mathematical concept.:idea:

I googled "math isolation" before my prior post, so was already aware of isolated point ... and thought about writing "independence is at least a common mathematical concept."

Let me put it this way. I first learned of independence, in the mathematical sense, when solving simultaneous equations of independent variables in high school algebra. Through the rest of high school and four plus years in electrical engineering courses, I don't recall encountering isolation anything or isolated anything, in the mathematical sense of course.

IMO independent subpuzzles is more appropriate than isolated subpuzzles.:idea:


I originally used "isolated" as a descriptive term to describe the fact that the UR portion of the puzzle becomes logically seperated from the rest of the puzzle. The term independent is used widely in mathematics for a number of things as Ronk points out. But in the case of Sudoku logic, sets, and constraints I'm not even sure even how to apply the term.

The independence or isolation I pointed out is between A) the UR region with pieces of all solutions and B) the common part of all solutions that lies outside the UR. The concept of independent solutions does not help me visualize this serperation.

For what its worth.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Red Ed » Tue Nov 11, 2008 8:31 am

IMHO, "isolated" is fine. Just like the rest of us, ronk has no vote on what terminology you choose for your concept. You don't need me to say it (but I will anyway) - do as you please, Allan!:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby David P Bird » Tue Nov 11, 2008 12:05 pm

Deleted
Last edited by David P Bird on Wed Nov 12, 2008 9:11 am, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby re'born » Tue Nov 11, 2008 12:56 pm

ronk wrote:I googled "math isolation" before my prior post, so was already aware of isolated point ... and thought about writing "independence is at least a common mathematical concept."

Let me put it this way. I first learned of independence, in the mathematical sense, when solving simultaneous equations of independent variables in high school algebra. Through the rest of high school and four plus years in electrical engineering courses, I don't recall encountering isolation anything or isolated anything, in the mathematical sense of course.

IMO independent subpuzzles is more appropriate than isolated subpuzzles.:idea:

I suppose it depends on what you mean by common. Being in the mathematical community, I have a skewed sense of what is common. But, at least among mathematicians, isolated is a very common word/notion. For those who couldn't be bothered to read the wiki entry, an isolated point is a term from topology. The way to think of it is as a point around which you can draw a small circle that contains no other points of your space.

Another related mathematical term that seems relevant comes from graph theory where you have connected components of graphs.

For me, isolated subpuzzle makes the most sense mathematically and aesthetically. Disconnected subpuzzle isn't too far off. In linear algebra, a list of vectors is independent if there is no non-trivial linear combination of the vectors that equals 0. That doesn't really describe this situation very well.

Here is a question: Does the term subpuzzle already have an established meaning. If not, this seems to be the perfect term.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ronk » Tue Nov 11, 2008 1:08 pm

Gee, it's a good thing I didn't suggest my first choice ... orthogonal subpuzzles.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby coloin » Tue Nov 11, 2008 3:55 pm

re'born wrote:Here is a question: Does the term subpuzzle already have an established meaning. If not, this seems to be the perfect term.

JPF defined minimal puzzles and subpuzzles here ........

not to be confused with grid solution and subgrid etc
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby re'born » Tue Nov 11, 2008 7:51 pm

coloin wrote:
re'born wrote:Here is a question: Does the term subpuzzle already have an established meaning. If not, this seems to be the perfect term.

JPF defined minimal puzzles and subpuzzles here ........

not to be confused with grid solution and subgrid etc


Thank you for the reference, coloin. The definition of subpuzzle is not what I had imagined it would be. As it is, none of isolated, independent, disconnected or orthogonal (:D) subpuzzle make any sense as a subpuzzle refers to a 9x9 grid with digits removed. How can it be isolated, etc. from the rest of the puzzle? It is the puzzle!

What if we define a subgrid of a grid G to be any subset of the cells of G? Of course, now we run into trouble when we remove digits from the cells in the subgrid. Since a subpuzzle is what you get when you remove digits from a grid, what should you get what when you remove digits from a subgrid? A sub-sub-puzzle? Probably, subpuzzle should be renamed puzzle and then we would recapture subpuzzle for when you remove digits from a subgrid. At this point, Allen's isolated subpuzzle terminology would make sense again and the definition of subpuzzle would match the more intuitive definition (subset of the puzzle).

...just an idea.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Red Ed » Tue Nov 11, 2008 10:14 pm

Go on then, I'll give up the moral high ground so that I can play too.

My preference: isolated pencilmarks.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Wed Nov 12, 2008 3:00 am

I can see where you are going with the pencil marks !

The pm grid of these subpuzzles..... it can be problematic to maximally complete these subpuzzles.

However....
coloin wrote:not to be confused with grid solution and subgrid etc


re'born has fallen for it !

These are the states for when you start removing clues.......

grid = 81 clue valid grid solution - maximally completed puzzle.
subgrid - a grid with some n clues removed - but still 1 solution - [if some clues are superfluos - non-minimal "puzzle" ]

minimal puzzle -:D [valid and unique]

subpuzzle - a valid puzzle with a necessary clue[s] removed - therefore more than 1 grid solution

- minimal subpuzzle
- non-minimal subpuzzle
- maximal subpuzzle


in a subpuzzle - the pm grid will tend to contain invalid pms
in a maximal subpuzzle the pm grid will have no invalid pms

Where does the isolated subpuzzle come in ?

C
coloin
 
Posts: 1637
Joined: 05 May 2005

PreviousNext

Return to Advanced solving techniques