At first glance, it looks like we start with an empty grid, and then we toss in the given clues, and then many of us start using data from all over the grid to pencilmark in all these possible digits in the unsolved cells. Given that there are issues of complexity when we consider various techniques, this begs the question, is the placement of these pencilmark candidates a legitimate act?
I would claim that it is a legitimate tactic, because you don't have to start from an empty grid. Instead, you can start from what I like to call an initial Candidate-Space grid. Imagine, if you will, that each cell in the grid contains nine Booleans, one for each digit n. Each Boolean indicates whether it is possible to place digit n in that cell. The initial grid in Candidate Space is a constant with every Boolean in every cell set true. As you place the given candidates, you can follow two very simple rules for setting Booleans false.
1. When a digit n is placed in cell A, then every other non-n Boolean in cell A is set false.
2. When a digit n is placed in a cell A, then every other n Boolean in other cells that share a group with cell A is set false.
When all given digits are placed, the pencilmark candidates just indicate which Booleans are still set true. From here, all of our candidate-based rules can be applied and we can solve the puzzle (or at least make a valiant attempt).
So good, we can use candidates. Phew! I'll bet you were really worried there.
The real point of this post is to put forward the idea that Candidate-Space is not your only option. There is another space where every cell contains a fixed number of Booleans, the initial grid is a constant, and there are some simple rules for resetting those Booleans as you fill in the given clues.
POM-Space
The Pattern Overlay Method (POM) as well as templating uses complete patterns, or rookeries, as its basic unit. A pattern or rookery is a particular legal arrangement of nine instances of a particular digit in a sudoku grid. For example, here are three different patterns for the digit 1...
- Code: Select all
*--------------------------* *--------------------------* *--------------------------*
| 1 . .| . . .| . . .| | 1 . .| . . .| . . .| | 1 . .| . . .| . . .|
| . . .| . 1 .| . . .| | . . .| . 1 .| . . .| | . . .| . 1 .| . . .|
| . . .| . . .| . . 1| | . . .| . . .| . . 1| | . . .| . . .| . . 1|
|--------+--------+--------| |--------+--------+--------| |--------+--------+--------|
| . . .| 1 . .| . . .| | . . .| 1 . .| . . .| | . . .| 1 . .| . . .|
| . . .| . . .| . 1 .| | . . .| . . .| . 1 .| | . . .| . . .| . 1 .|
| . . 1| . . .| . . .| | . 1 .| . . .| . . .| | . . 1| . . .| . . .|
|--------+--------+--------| |--------+--------+--------| |--------+--------+--------|
| . . .| . . .| 1 . .| | . . .| . . .| 1 . .| | . . .| . . .| 1 . .|
| . 1 .| . . .| . . .| | . . 1| . . .| . . .| | . . .| . . 1| . . .|
| . . .| . . 1| . . .| | . . .| . . 1| . . .| | . 1 .| . . .| . . .|
*--------------------------* *--------------------------* *--------------------------*
It turns out there are (9*4)**3 legal patterns for every digit in a sudoku grid. If we assign a unique label to each pattern, we can define the next step. There are many ways of labeling these patterns. I like the following which is based on the position of the digits on the grid.
- Code: Select all
*--------------------------*
|u0 1 2| x . .| . . .|
| 3 4 5| . 0 1| . . .|
| 6 7 8| . 2 3| . . .|
|--------+--------+--------|
| . . .|v0 1 2| y . .|
| . . .| 3 4 5| . 0 1|
| . . .| 6 7 8| . 2 3|
|--------+--------+--------|
| z . .| . . .|w0 1 2|
| . 0 1| . . .| 3 4 5|
| . 2 3| . . .| 6 7 8|
*--------------------------*
My labels have six digits. The three most significant digits (u, v, w) of the label range from 0-8, and just represent the cell the digit lies in for boxes 1, 5, and 9, respectively. The three least significant digits (x, y, z) of the label range only from 0-3, and are defined relative to the intersection points of the three most significant digits in blocks 2, 6, and 7. Start right and down (cyclically) from the intersection point and continue to define your four label value locations. The grid above shows the xyz labels for uvw = 000. The grid below shows the xyz labels for uvw = 246...
- Code: Select all
*--------------------------*
| . . u| . x .| . . .|
| . . .| 1 . 0| . . .|
| . . .| 3 . 2| . . .|
|--------+--------+--------|
| . . .| . . .| . 2 3|
| . . .| . v .| y . .|
| . . .| . . .| . 0 1|
|--------+--------+--------|
| 0 1 .| . . .| . . .|
| 2 3 .| . . .| . . .|
| . . z| . . .| w . .|
*--------------------------*
From this, you can tell that the first three grids in this post are labels 000000, 000001, and 000002. Note that every label from 000000 to 888333 is a valid pattern.
Now we can define our POM-Space Booleans. For each digit in each cell, a pattern label Boolean is set true if the pattern can exist and it uses that cell. Each pattern starts off with 81 true Booleans, 9 for each digit. Each cell starts off with 36**3, or 46,656 true Booleans; 5184 for each digit. Here is a representation of the initial POM-Space constant for the grid, before any given clues are placed. Asterisks indicate that any value for that label digit is allowed for that cell. Square brackets enclose allowed values for that label digit for that cell. Each cell has 5184 patterns initially set true.
Initial POM-Space Grid
- Code: Select all
Block 1
0***** 1***** 2*****
3***** 4***** 5*****
6***** 7***** 8*****
Block 2
[678][258]*0** [678][036]*0** [678][147]*0**
[678][147]*1** [678][258]*1** [678][036]*1**
[345][258]*2** [345][036]*2** [345][147]*2**
[345][147]*3** [345][258]*3** [345][036]*3**
[012][258]*0** [012][036]*0** [012][147]*0**
[012][147]*1** [012][258]*1** [012][036]*1**
[678][258]*2** [678][036]*2** [678][147]*2**
[678][147]*3** [678][258]*3** [678][036]*3**
[345][258]*0** [345][036]*0** [345][147]*0**
[345][147]*1** [345][258]*1** [345][036]*1**
[012][258]*2** [012][036]*2** [012][147]*2**
[012][147]*3** [012][258]*3** [012][036]*3**
Block 3
[345]*[147][01][02]* [345]*[036][01][13]* [345]*[036][01][02]*
[345]*[258][01][13]* [345]*[258][01][02]* [345]*[147][01][13]*
[678]*[147][23][02]* [678]*[036][23][13]* [678]*[036][23][02]*
[678]*[258][23][13]* [678]*[258][23][02]* [678]*[147][23][13]*
[012]*[147][23][02]* [012]*[036][23][13]* [012]*[036][23][02]*
[012]*[258][23][13]* [012]*[258][23][02]* [012]*[147][23][13]*
[678]*[147][01][02]* [678]*[036][01][13]* [678]*[036][01][02]*
[678]*[258][01][13]* [678]*[258][01][02]* [678]*[147][01][13]*
[012]*[147][01][02]* [012]*[036][01][13]* [012]*[036][01][02]*
[012]*[258][01][13]* [012]*[258][01][02]* [012]*[147][01][13]*
[345]*[147][23][02]* [345]*[036][23][13]* [345]*[036][23][02]*
[345]*[258][23][13]* [345]*[258][23][02]* [345]*[147][23][13]*
Block 4
[147][345]**[01][02] [036][345]**[01][13] [036][345]**[01][02]
[147][678]**[23][02] [036][678]**[23][13] [036][678]**[23][02]
[258][345]**[01][13] [258][345]**[01][02] [147][345]**[01][13]
[258][678]**[23][13] [258][678]**[23][02] [147][678]**[23][13]
[147][012]**[23][02] [036][012]**[23][13] [036][012]**[23][02]
[147][678]**[01][02] [036][678]**[01][13] [036][678]**[01][02]
[258][012]**[23][13] [258][012]**[23][02] [147][012]**[23][13]
[258][678]**[01][13] [258][678]**[01][02] [147][678]**[01][13]
[147][012]**[01][02] [036][012]**[01][13] [036][012]**[01][02]
[147][345]**[23][02] [036][345]**[23][13] [036][345]**[23][02]
[258][012]**[01][13] [258][012]**[01][02] [147][012]**[01][13]
[258][345]**[23][13] [258][345]**[23][02] [147][345]**[23][13]
Block 5
*0**** *1**** *2****
*3**** *4**** *5****
*6**** *7**** *8****
Block 6
*[678][258]*0* *[678][036]*0* *[678][147]*0*
*[678][147]*1* *[678][258]*1* *[678][036]*1*
*[345][258]*2* *[345][036]*2* *[345][147]*2*
*[345][147]*3* *[345][258]*3* *[345][036]*3*
*[012][258]*0* *[012][036]*0* *[012][147]*0*
*[012][147]*1* *[012][258]*1* *[012][036]*1*
*[678][258]*2* *[678][036]*2* *[678][147]*2*
*[678][147]*3* *[678][258]*3* *[678][036]*3*
*[345][258]*0* *[345][036]*0* *[345][147]*0*
*[345][147]*1* *[345][258]*1* *[345][036]*1*
*[012][258]*2* *[012][036]*2* *[012][147]*2*
*[012][147]*3* *[012][258]*3* *[012][036]*3*
Block 7
[258]*[678]**0 [036]*[678]**0 [147]*[678]**0
[147]*[678]**1 [258]*[678]**1 [036]*[678]**1
[258]*[345]**2 [036]*[345]**2 [147]*[345]**2
[147]*[345]**3 [258]*[345]**3 [036]*[345]**3
[258]*[012]**0 [036]*[012]**0 [147]*[012]**0
[147]*[012]**1 [258]*[012]**1 [036]*[012]**1
[258]*[678]**2 [036]*[678]**2 [147]*[678]**2
[147]*[678]**3 [258]*[678]**3 [036]*[678]**3
[258]*[345]**0 [036]*[345]**0 [147]*[345]**0
[147]*[345]**1 [258]*[345]**1 [036]*[345]**1
[258]*[012]**2 [036]*[012]**2 [147]*[012]**2
[147]*[012]**3 [258]*[012]**3 [036]*[012]**3
Block 8
*[147][345][02]*[01] *[036][345][02]*[01] *[036][345][02]*[01]
*[147][678][02]*[23] *[036][678][02]*[23] *[036][678][02]*[23]
*[258][345][13]*[01] *[258][345][13]*[01] *[147][345][13]*[01]
*[258][678][13]*[23] *[258][678][13]*[23] *[147][678][13]*[23]
*[147][012][02]*[23] *[258][012][02]*[23] *[036][012][02]*[23]
*[147][678][02]*[01] *[258][678][02]*[01] *[036][678][02]*[01]
*[258][012][13]*[23] *[036][012][13]*[23] *[147][012][13]*[23]
*[258][678][13]*[01] *[036][678][13]*[01] *[147][678][13]*[01]
*[147][012][02]*[01] *[258][012][02]*[01] *[036][012][02]*[01]
*[147][345][02]*[23] *[258][345][02]*[23] *[036][345][02]*[23]
*[258][012][13]*[01] *[036][012][13]*[01] *[147][012][13]*[01]
*[258][345][13]*[23] *[036][345][13]*[23] *[147][345][13]*[23]
Block 9
**0*** **1*** **2***
**3*** **4*** **5***
**6*** **7*** **8***
Using the table above, pattern 536121 would be initially set true in the following cells marked with a 'T'.
- Code: Select all
*--------------------------*
| . . .| . . .| . . T|
| . . T| . . .| . . .|
| . . .| . . T| . . .|
|--------+--------+--------|
| . . .| . . .| . T .|
| . . .| T . .| . . .|
| T . .| . . .| . . .|
|--------+--------+--------|
| . T .| . . .| . . .|
| . . .| . T .| . . .|
| . . .| . . .| T . .|
*--------------------------*
Initial POM-Space Rules for given clues
So, just like Candidate-Space, POM-Space starts out with an initial, though much bigger, constant. Also similar to Candidate-Space, POM-Space has some simple rules to follow as you fill in given candidates.
1. When a digit n is placed in cell A, then the only n-pattern Booleans that can be true are the ones in cell A. All other n-pattern Booleans are set false in all the cells throughout the entire puzzle.
2. When a digit n is placed in a cell A, then every non-n Boolean in cell A is set false in all the cells throughout the entire puzzle.
3. If no potential patterns Booleans are true for a particular candidate in a particular cell A, then that particular candidate can be removed as a possible candidate for cell A
These simple initial rules can rapidly whittle down the number of true potential patterns for a digit. Note that you can apply these rules at any stage of a partially solved puzzle. You can wait until you have solved the puzzle as far as you can using other methods before converting over to POM-Space (which is often a good idea--fewer remaining potential patterns to deal with).
A little trick:
Since carrying around a great bunch of 6-digit pattern identifiers would be excessively unwieldy, it is common to form a one-to-one mapping from each remaining pattern to another set of symbols--say letter characters, for example. Thus, instead of having patterns 4(000000), 4(000001), and 4(000002) remaining true in a cell; you could map them to 4a, 4b, and 4c; or even 4abc as a more terse notation.
Also, there are other ways of deriving the remaining potential patterns for a digit. You don't have to start from the initial POM-Space constant in many cases (but you always can, and it always works).
Benefits of Operating in POM-Space
There are many benefits when you operate in POM-Space. The first benefit you may notice is that just the act of converting to POM-Space automatically finds every single-digit reduction possible at that point in the puzzle. All locked candidates, x-wings, swordfish, jellyfish, finned fish, simple coloring, strong links, multi-coloring, grouped multi-coloring, x-cycles, grouped x-cycles, and franken-fish reductions for any converted digits are found.
Once you have your possible POM pattern identifiers in each cell, a number of POM techniques may be employed. Here is a brief listing of some of them.
POM Technique 1 - Pattern Exclusion Principle
If a pattern occupies cells containing all of the patterns for any other digit, then that pattern must be invalid. Obviously, if that pattern were true, then there would be no valid placements for that other digit on the grid. You can often find these reductions by inspection.
POM Technique 2 - Combined Candidate/POM Pattern Logic
POM effectively divides candidates into a finer grained resolution. Because of this, many candidate techniques can be applied to the potential POM patterns. For example, say you have a nice loop or AIC that ends on the same digit in two different cells. You can then eliminate all POM patterns for that digit that do not reside in one of those two cells. You can apply this combo logic to ALS's and uniqueness patterns as well. One nifty POM uniqueness reduction is the following. If you have a uniqueness rectangle containing abc in all four cells, then you can eliminate any patterns for a, b, and c that do not show up in those four cells. Strong inferences exist where two cells contain all of the potential patterns for a digit. Weak inferences exist where two cells, or two groups of cells, do not share a pattern for a digit.
POM Technique 3 - Pattern Equations
One huge benefit you get in POM-Space is a convenient "NOT" which can be applied anywhere, and not just where you have reduced things to a binary choice. If you have 4abc as your potential patterns, NOT pattern 4a is all of the other remaining potential patterns for the digit 4, i.e. 4bc. Thus from every cell, you get a Boolean algebraic equation for every candidate in that cell. NOT the patterns for one candidate equals the remaining patterns in the cell. These equations can be combined with the equations in other cells to isolate patterns that must be false. Note that all multi-digit coloring, xy-cycle, Nice Loop, ALS, and/or AIC reductions can be made from the POM pattern equations derived from the cells that make up the pattern in Candidate-Space (provided they do not use Uniqueness).
POM Technique 3A - Substitution Duplication Eliminations
You can use the POM pattern equations to make a substitution or a series of substitutions in another cell on the grid. After you make a substitution, if any patterns are duplicated in the cell, you can eliminate them from consideration (they are false) both from the grid and from any equations you have generated.
Options exist for partial, or incomplete POMing as well. POM techniques may be difficult, but they are possible without a computer. One additional benefit I have found from working in POM-Space is that you discover how many of the other candidate-based techniques really work and where they tend to be most effective. I've only scratched the surface of POM techniques. As Vidar showed with his take on a POM solver, there is a lot more to discover here.
Other Spaces?
Are Candidate-Space and POM-Space our only sudoku options? Probably not. I do not know enough about travelling pairs and braiding to come up with anything, but it might be possible to define an NZ-Space, for example, as an aid for some of those techniques. Sometimes all it takes is the equivalent of a shift in coordinate systems or a Fourier transformation to make very difficult deductions much easier to see.
Some related POM posts:
http://forum.enjoysudoku.com/viewtopic.php?t=2932
http://forum.enjoysudoku.com/viewtopic.php?t=2793
http://www.sudoku.org.uk/discus/messages/2/231.html?1127247239
