Mirrored from Sudopedia, the Free Sudoku Reference Guide


Pattern Overlay Method

The Pattern Overlay Method or POM analyzes the way digits can be placed in the remaining candidate space. This solving technique should be avoided when there are still a large number of available candidates in the grid.

Another name for this technique is templating.

Within the POM context, a pattern or template is a possible configuration for all instances a single digit that does not violate the Sudoku rule. For a standard Sudoku, there are 9 instances in each pattern. Here is an example:

X . .
. . .
. . .
. . .
X . .
. . .
. . .
. . .
X . .
. X .
. . .
. . .
. . .
. X .
. . .
. . .
. . .
. X .
. . X
. . .
. . .
. . .
. . X
. . .
. . .
. . .
. . X

There are 46656 different patterns. A single placement reduces this number by a factor 9. When a large part of the puzzle is solved, only a handful of patterns remain. At that point, the POM technique could be used by human solvers without too much effort.

How it works

The first step is to isolate the remaining candidates for a single digit. In the following grid, we will analyze the possible patterns for digit 8.

image:POM1.png

There are 7 patterns that can place the 6 remaining instances of digit 8 in the unsolved cells that allow this digit. They are identified by the letters a through g.

image:POM2.png

You do not need a separate grid for each pattern. It is also possible to write the pattern identifiers in a single grid. This grid then immediately shows the patterns used by each cell.

image:POM3.png

There are 2 possible deductions that you can make for a single-digit POM analysis:

In this example, there are 3 cells without any pattern identifiers. You can remove digit 8 from these cells.

Multi-Digit Pattern Elimination

Where a set of cells together appears in all patterns for a single digit, any pattern for another digit that contains all of the cells in the set can be eliminated. After reducing the set of possible patterns in this way, one can apply the single-digit POM analysis rules to the remaining patterns.

Example

Consider this grid:

.------------------------.------------------------.------------------------.
| 2       13      4      | 378     137     178    | 5       69      69     |
| 7       5       38     | 6       9       4      | 238     28      1      |
| 6       9       138    | 35      2       15     | 348     48      7      |
:------------------------ ------------------------ ------------------------:
| 8       12467   126    | 9       1457    156    | 27      2567    3      |
| 49      2467    5      | 3478    347     678    | 1       26789   269    |
| 3       167     169    | 578     157     2      | 789     56789   4      |
:------------------------ ------------------------ ------------------------:
| 5       34      239    | 27      6       79     | 49      1       8      |
| 49      246     269    | 1       8       3      | 2479    479     5      |
| 1       8       7      | 24      45      59     | 6       3       29     |
'------------------------'------------------------'------------------------'

There are 5 placement patterns for the candidate 2 (call them a-e) and 6 placement patterns for the candidate 4 (call them A-F). Here is the grid of these patterns:

.------------------------.------------------------.------------------------.
| .       .       .      | .       .       .      | .       .       .      |
| .       .       .      | .       .       .      | abc     de      .      |
| .       .       .      | .       .       .      | A       BCDEF   .      |
:------------------------ ------------------------ ------------------------:
| .       adBC    b      | .       ADEF    .      | e       .       c      |
| ADE     ceF     .      | B       C       .      | .       ab      d      |
| .       .       .      | .       .       .      | .       .       .      |
:------------------------ ------------------------ ------------------------:
| .       AD      d      | abce    .       .      | BCEF    .       .      |
| BCF     bE      ace    | .       .       .      | dD      A       .      |
| .       .       .      | dACDEF  B       .      | .       .       abce   |
'------------------------'------------------------'------------------------'

Taken together, cells r4c2 and r9c4 participate in all patterns for candidate 4 (A-F), meaning that at least one of the two cells must always be a 4. Both of these cells are also in pattern d for candidate 2. Pattern d thus is impossible and can be discarded. Doing so leaves us with this pattern grid (* shows where pattern d was removed):

.------------------------.------------------------.------------------------.
| .       .       .      | .       .       .      | .       .       .      |
| .       .       .      | .       .       .      | abc     *e      .      |
| .       .       .      | .       .       .      | A       BCDEF   .      |
:------------------------ ------------------------ ------------------------:
| .       a*BC    b      | .       ADEF    .      | e       .       c      |
| ADE     ceF     .      | B       C       .      | .       ab      *      |
| .       .       .      | .       .       .      | .       .       .      |
:------------------------ ------------------------ ------------------------:
| .       AD      *      | abce    .       .      | BCEF    .       .      |
| BCF     bE      ace    | .       .       .      | *D      A       .      |
| .       .       .      | *ACDEF  B       .      | .       .       abce   |
'------------------------'------------------------'------------------------'

Cells r7c4 and r9c9 participate in all of the remaining patterns for candidate 2 (abce). Thus, we know that those two cells must be a 2.

Cells r5c9, r7c3, r8c7, and r9c4 no longer occur in any pattern for candidate 2. We can therefore eliminate 2 as a possible candidate for these cells.

This page was last modified 05:35, 11 January 2008.