Demonstration of Sudoku Pattern Overlay Method. Learn how does pattern overlay method works? Also, learn Multi-Digit Pattern Elimination, Pattern Analysis & Limited Pattern Overlay (LPO)

Pattern Overlay Method

The Pattern Overlay Method, or POM, examines the possible placement of digits in the remaining candidate space. 

When there are still many viable candidates in the grid, this solution procedure should be avoided. This method is also known as a template.

A pattern or template is a feasible configuration for all instances of a single number that does not break the Sudoku rule in the POM context. 

For example, each pattern in a normal Sudoku has nine occurrences. Here’s an illustration:

 There are a total of 46656 patterns to choose from. This number is reduced by a factor of nine with just one placement. 

Only a few patterns remain after a major portion of the puzzle has been solved. 

Human solvers could apply the POM approach without too much effort at that stage.

How does it work?

The first step is to eliminate the single-digit options that remain. In the grid below, we’ll look at the numerous patterns for digit 8.

                    

The six remaining digits 8 can be placed in the unresolved cells that accept this digit using one of seven patterns. They are identified by the letters a through g. 

Each pattern does not require a grid. The pattern identifiers can alternatively be written in a single grid. The patterns utilized by each cell are then shown in this grid.

 

In the case of a single-digit POM analysis, there are two potential deductions:

• The selected digit must be present in all cells that include all pattern IDs.

• Cells with no pattern identifiers are unable to hold the specified digit.

There are three cells in this sample that have no pattern IDs. Therefore, you can delete the eighth digit from these fields.

Multi-Digit Pattern Elimination

Any pattern for another digit that contains all of the cells in the set can be discarded if a group of cells occurs in all patterns for a single digit.

After decreasing the number of potential patterns in this way, the remaining patterns may be subjected to the single-digit POM analysis criteria.

Example

Consider this grid:

 

Candidate 2 has 5 placement patterns (designated a-e), while Candidate 4 has 6 placement patterns (call them A-F). The grid of these designs is as follows:

Cells r4c2 and r9c4 jointly participate in all candidate 4 (A-F) patterns, implying that at least one of the two cells must always be a 4. Both of these cells are also in candidate 2’s pattern d.

As a result, pattern d is impossible and may be rejected. As a result, we have the following pattern grid (* indicates where pattern d was removed):

All of the remaining patterns for candidate 2 include cells r7c4 and r9c9 (abce). As a result, we know that two cells must be a 2.

For candidate 2, the cells r5c9, r7c3, r8c7, and r9c4 no longer appear in any pattern. As a result, we can rule out 2 as a feasible possibility for these cells.

Overlay Method

This technique, devised by Myth Jellies, considers how candidates for a given numeral N might be spread in the remaining spaces.

Every time a digit is entered, it clears off additional spaces in the Row, Column, and box, quickly decreasing the options. It’s a tactic you don’t want to use too early in the puzzle since the number of overlays can be too high, but it’s quite simple to use in the middle and end games.

The First Pattern Overlay

 The first illustration depicts a potential pattern or template. It is the first design given an empty board and a starting position from the top left to the bottom right.

There are 46,656 possible designs on an empty board, so we utilize it when most of the cells are filled. The number of designs is reduced by 9 with each placement of N.

 

Only the three numbers are presented. All threes are illustrated in this pretty simple example. We may begin with the top block, which has just two threes, resulting in a total of two overlays.

 

There are two potential patterns. I’ve colored the two patterns in this picture. Find a different pattern that chooses a 3 for each row, Column, and box. It should be unthinkable.  

 

Using the Overlay, It’s easier to match the candidate number to the patterns “a,” “b,” “c,” and so on. We’re just interested in number 3, thus “a” and “b” are suitable. This is when POM’s magic begins.

We’ve discovered that those cells with “ab” must contain that number. A 3 cannot be found in cells that have no “a” or “b” (marked with a dash).

The solution will return one of two types of elimination sets: “Rule 1” or “Rule 2.”

Rule 1 looks at each number separately. When searching for all potential X patterns, it’s possible that X will not exist in any of them. If a solution is identified, the solver submits a report and exits.

Rule 2 examines all of the patterns for all integers from 1 to 9. All patterns inside each number may desire to occupy certain cells, creating a bottleneck. If that’s the case, such cells aren’t available for other numbers’ patterns to employ.

Although this is more difficult for a person to calculate, it works well for the solver, and we get a lot of them. Patterns are trimmed, and Rule 1 is used to locate the first X, where X does not use any cells. Only the first X is shown; there may be more eliminations from numbers higher than X, but reporting the complete overlap would be too confusing.

Pattern Overlay

Let’s take a look at the unresolved Cells that include a certain candidate and find all feasible final solutions for that candidate (i.e., all patterns in which the candidate appears only once per row, per Column, and Square).

 Pattern Overlay (always “ON”): the candidate must answer every cell in every pattern. Candidate 3 in C1 is included in all conceivable patterns in this case.

Pattern Overlay (always “OFF”): the candidate cannot answer any Cell that is not a part of any pattern.

Candidate 3 in C7 is not a feasible or acceptable pattern in the case.

When there are just a few unresolved Cells for a candidate, this method is best utilized to decrease the number of patterns to evaluate.

Pattern Analysis

A pattern in Sudoku is a group of candidates with the same value that contains one candidate for each row, Column, and box.

A clue of that value doesn’t occupy any unit. Therefore, a candidate for a pattern cannot see another candidate. Some writers refer to patterns as “templates.”

As advanced solving progress, each number usually has several patterns on the grid. 

Andrew Stuart presents a visual way for highlighting patterns in Figure 32.3 in a brief chapter on patterns in his book The Logic of Sudoku. He refers to these interconnected line segments as “overlaid lines.” We call them free forms since they’re called in graphical applications.

 According to logic, the number 7 has two distinct patterns. Candidates that do not fit within these patterns can be eliminated. They’re what I refer to as orphans. Both patterns have three choices that are confirmed as hints.

Two Types of Pattern Analysis

The Pattern Overlay Method, a suggested computer approach for solving any Sudoku with finished candidates, drew the greatest attention to patterns. The goal is to combine patterns of one value with other values.

A pattern cannot be the solution pattern if it contradicts every pattern of another value. These two patterns are solution patterns if a single pattern of one value overlaps a single pattern of another value, which is likely enough to collapse the problem.

When numerous patterns of each value overlap without conflict, there are methods to proceed. Still, the necessity to identify all patterns of all values is enough to eliminate POM as a human solution technique.

In many problems, however, the number of patterns of particular values is manageable, especially when improved approaches have eliminated a large number of them.

As a result, a restricted pattern overlay can be used as a solution approach. These strategies are based on the POM principle, which states that patterns should be eliminated if they clash with patterns of other values. So let’s name them LPO techniques (Limited Pattern Overlay).

Even though Andrew’s pattern analysis chapter is named Pattern Overlay Method and explains LPO, his created Figure 32.3 depicts a very different pattern analysis. It isn’t predicated on a POM disagreement between solution cell values. Rather, there is a conflict between patterns with the same value. Like X-chains and fish, everything is on the X-panel. Let’s name this type of X-pattern Analysis, or XPA, to distinguish it from POM and LPO.

Enumerating Patterns with Freeforms

Both forms of pattern analysis rely on finding all patterns for a given value X given the X-panel of remaining possibilities. Humans can achieve this because of free forms, which are based on the following verifiable facts:

Every n-candidate pattern defines a collection of n vertical free forms that cross the problem from top to bottom and a set of n horizontal free forms that cross the puzzle from left to right.

Andrew encourages the Logic reader to double-check Figure 3.23 by looking for more patterns. Following a legitimate path that inserts a number in each box and Column,” he says. This is a 7-panel with free forms enumeration of all 7-patterns.

Let’s go over this step by step to see how enumeration is done.

To test whether we can reproduce Andrew’s pair and locate any more, we start with a new 7-panel and start patterns from r1c1. We’ll travel from north to south, as Andrew proposes. We’ll also head west before heading east.

By these restrictions, our initial freeform cannot give a candidate for r3. The second fails as well, this time on r7, because candidates for c2, c4, and c8 have already been chosen. We’ll try the last option, a well-known maze exploring approach, to get to the blue pattern above.

Because finding all patterns necessitates a labyrinth route enumeration approach, we return to the remaining untested option, r2. However, instead of using the blind maze technique, we can now see that shifting the freeform in r2 from c8 to c9 necessitates keeping c3 free until we reach r9.

To accomplish so, we must change r5 to c2, then r7 to c4, and finally r7 to c8. Above is the green pattern.

This line exchange approach does not function entirely until all options are between two candidates. However, it is useful for narrowing the search. We continue Andrew’s quest to locate more free forms starting with r1, identifying exactly two patterns, including r1c1.

Before checking below, you might want to satisfy your methodical side by copying some 7-panels and testing it out for yourself. Begin with r1c9 to ensure that the free forms that follow are not in your head. One freeform can get as far as r7 from c3.

When it removes the sole remaining ending column in r9, the dashed one is doomed at r2. Three free forms reach r3, r7, and r9 from c4.

There are two methods to go to r5c3 from c9 and two ways to fail. The failure arises for a different reason; r8 is the final row for two columns, c1 and c5, which must be filled to obtain a candidate. Yes, both methods lead to the final candidate for r9.

We confirmed that Figure 32.3 only shows the two seven patterns that Andrew’s free forms detect after covering all beginning points in r1.

However, based on this experience, r1 may not be the greatest of the four options for a starting line.

So, which option is ideal for a freeform starting line? We should be directed toward the side with the simpler to refute beginning cells, keeping in mind that every pattern must be found.

There are four possible starting cells in the first line and two to three-second cells in the second line while going north to south.

Compare West to East, which has two beginning cells and three-second pathways in each.

Unsurprisingly, it contains eight failures, including three more from r8c1 and two patterns. It’s worth noting that the patterns are the same; however, the free forms change significantly from the North to South study.

C9 is the finest freeform beginning line. Out of the first three lines, the S-> N r9 has six options, but the E->W c9 has just three.

This prediction is proven below, where choosing the optimal starting cell order pays off. The first is r1c9 because it only has one exit, r8c1. Because the first three columns have just one option, r9c9 is next. Because r8c5 has already caused the exit to be r1, r1c4 is not an option.

Last but not least, r2c9 discovers the green pattern and only has one option.

Andrew Stuart’s freeform depiction of patterns is transformed into a sharp instrument for a human solution by our intrinsic capacity to solve a basic maze.

Following that, we show how to utilize it in certain Sysudoku XPA and LPO applications.

X-Pattern Analysis

Returning to the X-panels and looking along the sides for limited numbers of beginning cells is a good initial step in pattern analysis.

For example, the 5-panel of puzzle 36 in “The World’s Hardest Sudoku” shows that candidate 5r1c9 is an orphan, according to a review. If you can find one, a sashimi swordfish will suffice.

The 6-panel in a second XPA example, GM 95 in XaqPitkow’s Hard to Extreme Sudoku, is impacted by a previously applied coloring cluster. As a result, the panel colors are derived from the fact that r9c9 is blue.

For beginning cells and East to West free forms, c9 is the obvious choice. Starting with blue, r9c9 produces four designs without tying the blue pattern down into four columns. The green freeform beginning in r5c9, on the other hand, has just one exit, and adding r1c1 leaves c3 without a candidate. GM 95 falls as Blue is verified.

Limited Pattern Overlay (LPO)

LPO exploits cell conflicts in overlay patterns of a collection of values to make candidate deletions.

The POM process can sometimes be maintained to a human scale of operations by restricting overlays to variables with the fewest patterns.

For example, prior deletions limit patterns on the grid in Andrew Stuart’s examples in The Logic of Sudoku. Still, it’s also feasible to undertake a conflict analysis when problems are uneven across values, with a monstrous fog in some panels but many fewer candidates in others with potential conflicts.

An example from the French journal Su-doku Maestro, Niveau 8-9, July-September 2009, # 22 illustrates such a circumstance. The marking of a swordfish discovered on the fourth line has been left on the line designated grid to mark the following rows.

The outcome of a freeform examination of the X-panel is shown below. Panels 1, 5, 7, and 9 are a starting point for a pattern and candidate elimination overlay.

For example, 6 patterns are on panels 1 and 9, 4 on panel 5, and 2 on panel 7. Unfortunately, one set of patterns that have been enumerated has left an orphan. 4r3c3 does not fit into any pattern in panel 4. When the removal is inconclusive, LPO overlays the good patterns.

While free forms are beneficial for enumerating patterns, the overlay is simpler with a different type of pattern representation.

Each pattern is allocated a letter that occurs in each of the pattern’s cells. In logic pattern analysis examples, Andrew employs this form. It’s known as lettering in Sudoku.

The four pattern sets in the lettering representation are as follows:

A pattern of one value conflicting with all patterns of another value is a definitive consequence of pattern overlay. Matching the two smallest groups of patterns, the 7-patterns with the four 5-patterns has the highest probability of happening.

For example, in r5c1, pattern 7b clashes with 5a and 5c, while in r7c5, pattern 7b clashes with 5band 5d. Because all five patterns are present, 7b cannot be true.

To demonstrate, do the standard follow-up marking of the 7a clues, noting the effect of each removal on the free-from panels, and then re-examining the panels. Finally, NE8 and NW2 wipe off the finned swordfish, and the collapse begins with a long but simple XY-chain ANL.

Candidate removals do result in freeform removals and orphans, but the expanding bv field is a better option in this scenario. Unfortunately, this is a common occurrence. LPO dispute resolution demands work, is more difficult than traditional procedures, and should only be utilized when other methods fail.

This was the simplest of overlays, but it demonstrates how brain-based pattern analysis tools, such as free forms and letters, may escape the computer algorithmic pattern overlay’s blind backtracking search.