Pattern overlay methods, both the computer based POM and the human engineered LPO, depend on finding every pattern for each participating number.  Andrew Stuart’s The Logic of Sudoku,   Chapter 32, gives examples of enumerated patterns which demonstrate that candidates can be removed because they are shown to belong to no pattern. Yet The Logic fails to arm the reader with a practical pattern enumeration technique.

Stuart’s first example,  rendered here on the Systematic Sudoku single X-panel template,  introduces  the enumeration process. Letters letters a, b, c, … are assigned to candidates  to mark the patterns to which they belong.  Andrew‘s letter assignment identifies two patterns a and b:

Clearly every unit is blessed with a candidate of both patterns.  But is there a third pattern?  Andrew offers that “staring at them for a moment will reveal that there are only two ways for a solution to appear.”

You are going to need more than a good hard stare.  One test for complete enumeration in complex cases is to add a new letter to one of the cells of each pattern. The new letter is then required to be present in each unit. If the new letter is forced to remain with the same letter it started with, then these two letters actually represent the same pattern, and no new pattern has been identified.  Try this on the simple example above, adding “c” to an “a” cell, then to a “b” cell.  The test is very easy in this case,  but is it always?

In a second pattern enumeration example in Logic of Sudoku, Andrew identifies two patterns, but does not explain how they are found, or how he knows they are the only patterns.  Below we show how he might have obtained them, by picking r3c7 as a starting point for the first pattern, and r3c9 for the second.

Andrew invites the reader to start with any uncovered candidate and attempt to complete a pattern.  When following this plan, if you see that two letters can be exchanged somewhere, but not everywhere within the pattern, this means a second pattern accompanies the first one.  You then add the second letter with the first in the common cells of the two patterns.  In the example above, If you reverse a and b in NE, the letters reverse everywhere, expressing the same two patterns, and therefore no new patterns are introduced.

On this second example, I made an attempt to introduce letter “c” in SW, only to have all of the uncovered 2 candidates forced into an incomplete “c” pattern. It could  not cover c8 and NE. Starting the at any other 2-candidate leads to the same result, verifying that, indeed, there are only two patterns, and all of the uncovered candidates can be removed.

Generally the verification of complete enumeration by this method could take much more effort, requiring the testing of every uncovered candidate. 

Fortunately for human solvers, there is a much more efficient pattern enumeration technique.  It uses a graphics construction that is easy to visualize and document.  I call it freeform pattern enumeration, after the Freeform shape in MS Office graphics.

The technique is to sweep the rows of candidates, top to bottom, selecting a candidate from each row in a new column and a new box, while drawing a freeform shape through the selected candidates.  Stop when no candidates in the next row qualify. You needn’t bother to skip such a row, because it can never provide a candidate. Every distinct freeform selecting a candidate from each candidate row defines a distinct pattern. Its candidates can be assigned a letter.  Alternate freeform paths along a completed freeform are easy to see.  Try all possible freeform paths from each candidate in the top row, and you’re done.  

You may prefer to sweep columns instead, with freeforms running left to right. The complete set of column sweeping freeforms defines the same complete set of patterns.

Below we have freeform paths, both complete and incomplete, starting on r3 of Stuart’s second example.  First, I invite you to confirm the complete freeforms and note why the incomplete ones stop. Then,  make your own assignment of pattern letters on a 2-panel, working from the complete freeforms below.  Then, you might like to try for the same result, sweeping columns instead of rows, starting with c3.  A checkpoint on that will appear in the next post.

Freeform enumeration works because patterns and complete freeform paths are in one-to-one correspondence.  Every complete pattern clearly provides a candidate for every column as we sweep rows, and a candidate for every row if we sweep columns.  Adversely, on a row sweep, a complete freeform provides a column candidate for every row.  That would be a good definition of “pattern”.

In a third pattern enumeration example, The Logic of Sudoku uses freeform enumeration, but doesn’t explain that the two patterns are the only patterns, or why this is so.   For a checkpoint in the next post, you might like to prove it with your own freeform charts.  Andrew does rows, but shows only the complete freeforms.  You can try rows without looking in The Logic, or go with columns, for comparison.

When you know that a and b mark the only two patterns, what is the effect on the grid? All candidates in the “7” cells are removed.  Also any cell containing all letters, in this case “ab”, is a clue. This is such a big reward for finding the POM pieces (pattern enumeration) that you probably won’t need to compare patterns.

The next post offers a detailed LPO enumeration for Maestro 22. I found no productive XY-chains and no WXYZ wings, no SdC or APE eliminations. The X-panels were equally stubborn, and coloring does not look promising.  Look over your panels and note which ones you would pick for LPO analysis.

To celebrate a year of blogging, and to show what LPO can do,  we’re going to tackle the Andrew Stuart “ Weekly Unsolveable”  of January 29/2012.  Look it up on www.sudokuwiki.org/Weekly_Sudoku.asp  and do the box marking for a checkpoint next week.