Searching for Orphans in LPO


This post illustrates the search for orphans in my Limited Pattern Overlay method.  Orphans are what we going to call candidates not belonging to any completed pattern.  Orphans are found by means of the freeform diagrams, as illustrated in Pattern Enumeration for POM and LPO, the post of 8/14/12.

Unsolvable 40 was reduced by LPO to one of two possible colors of a cluster, involving patterns of four numbers.  In the post  of two weeks ago, a solution was found in two trials.  There are two ways we could have continued with LPO, however.  We could have searched specifically for orphans, and we could have updated  freeforms as candidates were eliminated, to determine when another number was reduced to a sufficiently low number of patterns to be added to the LPO set.   Here we consider the orphans.

Orphans are rare, and I am not saying we should have searched for orphans before doing LPO with the patterns we had.  The initial set of patterns is enough in most cases.  But when we reached the point where we did the green and blue trials, we could have looked for orphans.  

Yes, we had already used freeforms to count  patterns defined until they  exceeded our limit, which drifted up to six.  But we did not continue with the search for orphans.  What if we discovered that, as in Stuart’s 7-candidate  example reviewed in my Pattern Enumeration post, many of the 3-candidates are orphans? 

Patterns for numbers 5, 6, 8, and 9 were used in the LPO. The freeforms drawn to count patterns for numbers 1, 2, 4, and 7 are shown below. Each had 10 or more patterns. 

The panels illustrate a systematic  method for counting patterns.  Each candidate on the starting line is assigned a separate color, and branches from the main freeform are given distinct dash styles.  Freeforms are supplemented by curves in especially congested areas.  In my case, the freeform insertions are done at a 200% zoom level.  This kind of effort is warranted when you consider the contribution that one more pattern set would make to solving a monster like Unsolvable 40.  Also, from my Pattern Enumeration post,  you can now appreciate how imperceptible a limited pattern is to a casual observer.  Note that freeform drawing stops when the number of patterns exceeds the desired limit.

When the time came to look for orphans,  numbers 1, 2 and 4 received an immediate pass, since every candidate was included in a “counting” pattern.  In the panel for number 7,  only one candidate in the starting row was enumerated,  and symmetry was invoked to double the number of patterns for the count.  This approach left six potential orphans.  Patterns for these candidates were easily found,  without completing the enumeration.  However, you should determine why at least four new patterns were necessary to eliminate orphans.

This leaves only the locust swarm of  number 3 candidates for possible orphans.  We can forget about systematically counting patterns, and go immediately to the method described with the small examples of  the Pattern Enumeration post.  We draw new freeforms passing through uncovered candidates until we can see that no uncovered candidates remain.   But in a case like this,  where it becomes difficult to find our way through a maze of freeforms, we can work in stages.

To take advantage of restrictions imposed by columns 2 and 3, freeforms were drawn horizontally,  left to right.  Freeforms were drawn from all c1 candidates, with solid lines for r123 and dashed lines for r789. Color coding and dashed lines helped me follow patterns through the tangle.  I could add diversions to existing patterns to cover uncovered candidates, diverting the pattern later to compensate for the diversion. This process becomes much more clear if you can try it yourself.

After starting a set of patterns from every candidate in c1, I could see where the restrictions were, and how to work through them.  I made a copy of the panel, shaded all uncovered candidates, and then erased the freeforms already drawn.  Then I drew new freeforms to pass through  uncovered candidates, using any of the already covered candidates that I needed.  It was easy to confirm that there are no orphans , as the right panel above shows.

OK, no orphans found.  What next, besides the color trials detailed in the 9/25 post?  My next post explores the issue of using the conflict logic of the pattern sets to find new patterns sets, from the numbers whose freeform patterns were reviewed for orphans in this post.

Advertisements

About Sudent

My real name is John Welch. I'm a happily married, retired professor (computer engineering), timeshare traveling, marathon running father of 3 wonderful daughters and granddad to 7 fabulous grandchildren. The blog is about Sudoku solving. It covers how to start, basic solving to find candidates efficiently, and advanced solving methods in an efficient order of battle. It is about human solving methods, not computer solving.
This entry was posted in Extreme Solving and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s