I want to talk about any band's (stack's) structure of 9 x 9 traditional Sudoku solution grids. I'am not sure this info is new.
Everyone knows that some special type of solution grid's band can exist, having 3 sets of minirow digits being repeated 3 times each in minirows. Here is an example of such band.
- Code: Select all
Example 1
529 814 367
367 259 148
418 763 529
As you can see, sets of digits S1={2,5,9}, S2={1,4,8} and S3={3,6,7} are repeated in 3 minirows each. What other types of bands (without repeated minirows) do exist?
I'll talk about bands only, although stacks (with minicolumns) have the same properties. I'll use this notation for band's minirows:
- Code: Select all
r1 M11 M12 M13
r2 M21 M22 M23
r3 M31 M32 M33
Let's consider r1 and r2 rows of some band. Compare pairwise all minirows of r1 row (M11, M12, M13) with all minirows of r2 row (M21, M22, M23). How many common digits will have each minirow pair (M11-M21, M11-M22, etc.)? Result (numbers of common digits) can be shown in the 3 x 3 minirow matching matrix. Here is minirow matching matrix for Example 1 (see example of band above).
- Code: Select all
M11 M12 M13
M21 0 0 3
M22 3 0 0
M23 0 3 0
One can see, that for r1/r3 and r2/r3 row pairs results will be similar - any two compared minirows of Example 1 have either 0 or 3 common digits. I call such type of band full-matched.
Definition 1
Minirows located in the same band are called mutually independent (or simply - independent) if they don't share box or row.
Definition 2
A band has full-matched type if any pair of independent minirows of this band has 0 or 3 common digits.
Property 1
It can be easily proved, that if one pair of independent minirows has 0 or 3 common digits, then all other pairs of independent minirows of this band have 0 or 3 common digits too, i.e. band has full-matched type.
Let's consider now Example 2.
- Code: Select all
Example 2
274 685 913
653 941 782
891 372 654
We can calculate minirow matching matrix for r1/r2 row pair:
- Code: Select all
M11 M12 M13
M21 0 2 1
M22 1 0 2
M23 2 1 0
You can see, that for r1/r3 and r2/r3 row pairs matrices will be the same - any two compared independent minirows will have either 1 or 2 common digits. (Minirows have 0 common digits if they are not independent, i.e. both compared minirows share the same box). I call such type of band half-matched.
Definition 3
A band has half-matched type if any pair of independent minirows of this band has 1 or 2 common digits.
Property 2
It can be proved, that if one pair of independent minirows has 1 or 2 common digits, then all other pairs of independent minirows have 1 or 2 common digits too, i.e. band has half-matched type.
Since any pair of independent minirows of 9 x 9 Sudoku band may have 0, 1, 2 or 3 common digits, other band types don't exist.
Definition 4
Triple of minirows is a set of 3 mutually independent minirows.
Here is an example of {M11,M23,M32} minirow triple.
- Code: Select all
r1 M11 - -
r2 - - M23
r3 - M32 -
There are 6 minirow triples. Three of them are told as having diagonal orientation, the rest are told as having antidiagonal orientation.
Definition 5
Triples of minirows {M11,M22,M33}, {M12,M23,M31}, {M13,M21,M32} are called triples with diagonal orientation, triples of minirows {M13,M22,M31}, {M12,M21,M33}, {M11,M23,M32} are called triples with antidiagonal orientation.
- Code: Select all
Diagonally oriented triples Antidiagonally oriented triples
M11 - - - M12 - - - M13 - - M13 - M12 - M11 - -
- M22 - - - M23 M21 - - - M22 - M21 - - - - M23
- - M33 M31 - - - M32 - M31 - - - - M33 - M32 -
Property 3 (evident)
For any full-matched band all minirow triples, formed by minirows containing 3 common digits with each other, have the same orientation (diagonal or antidiagonal).
Here are all minirow triples, formed by minirows containing 3 common digits with each other, for Example 1.
- Code: Select all
Example 1
529 ... ... ... 814 ... ... ... 367
... 259 ... ... ... 148 367 ... ...
... ... 529 418 ... ... ... 763 ...
As you can see, all 3 triples have diagonal orientation.
Property 4
For any half-matched band minirow pairs, containing 2 common digits with each other and participating the same minirow triple, have the same common digits (pair of digits).
Property 5
For any half-matched band all minirow triples, formed by minirows containing 2 common digits with each other, have the same orientation O1 (diagonal or antidiagonal). All minirow triples of the same band, formed by minirows containing 1 common digit with each other, have opposite orientation O2.
- Code: Select all
Example 2
274 685 913
653 941 782
891 372 654
Triples, formed by minirows containing 2 common digits (all triples have antidiagonal orientation):
27. ... ... ... 6.5 ... ... ... 91.
... ... 7.2 65. ... ... ... 9.1 ...
... .72 ... ... ... 65. .91 ... ...
Triples, formed by minirows containing 1 common digit (all triples have diagonal orientation):
..4 ... ... ... .8. ... ... ... ..3
... .4. ... ... ... .8. ..3 ... ...
... ... ..4 8.. ... ... ... 3.. ...
Property 6
Permutation of 2 band's rows (swapping) changes all tripples' orientations to opposite. Cyclical shift of band's rows doesn't change tripples' orientations.
Property 7
Permutation of 2 band's boxes (stacks) changes all tripples' orientations to opposite. Cyclical shift of band's boxes doesn't change tripples' orientations.
So, there are 2 band types only.
Full-matched band can be produced by partioning 9 digits to three 3-digit sets. Then we should select orientation of constructed band. Each 3-digit set must be assigned to one of three possible minirow triples.
Half-matched band can be produced by partioning 9 digits to three 2-digit sets (6 "paired" digits) and 3 "unpaired" digits. Then we should select orientation of paired digits. Each 2-digit set must be assigned to one of three possible minirow triples with selected orientation. Each unpaired digit must be assigned to one of three possible minirow triples with opposite orientation.
Minlex form of every full-matched band contains the following starting 12 digits (all minirow triples have antidiagonal orientation).
- Code: Select all
123 456 789
456 ... ...
... ... ...
Minlex form of every half-matched band contains the following starting 12 digits (triples for paired digits have antidiagonal orientation, triples for unpaired digits have diagonal orientation).
- Code: Select all
123 456 789
457 ... ...
... ... ...
Saying about band (stack) type's frequency - Monte-Carlo modelling (see, for example, well-known Michael Deverin's paper "Soduko: Minlex Form and Chaining") shows, that about 25% of all solution grids contain at least one full-matched band (or stack). So, 75% of all solution grids contain half-matched bands and stacks only.
Serg
[Edited. I added examples for bands' minlex forms and exact name of Michael Deverin's paper.]
