Matching minirows analysis

Everything about Sudoku that doesn't fit in one of the other sections

Matching minirows analysis

Postby Serg » Thu Jan 21, 2021 11:17 pm

Hi, all!
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.]
Serg
2018 Supporter
 
Posts: 732
Joined: 01 June 2010
Location: Russia

Re: Matching minirows analysis

Postby dobrichev » Fri Jan 22, 2021 2:54 pm

Hi Serg,

Once dpbobelisk pointed that Grid Momentum approach overlaps Braid Analysis. Not sure if this happens again, but you can check.
dobrichev
2016 Supporter
 
Posts: 1807
Joined: 24 May 2010

Re: Matching minirows analysis

Postby Serg » Fri Jan 22, 2021 4:06 pm

Hi, Mladen!
dobrichev wrote:Once dpbobelisk pointed that Grid Momentum approach overlaps Braid Analysis. Not sure if this happens again, but you can check.

Thank you for new information, but some of that information is unavailable. The first link points to the post with link to dpbobelisk post, but that link is broken. Link "Braid Analysis" shows empty page. But I saw your "Grid Momentum" approach. This information is new to me. "Spin" has definitely something in common with "orientation". But I think "orientation" concept is supplementary in my analysis. I think, my main result is the following statements.

There are 2 band types only.
Full-matched band can be produced by partioning 9 digits to three 3-digit sets.
Half-matched band can be produced by partioning 9 digits to three 2-digit sets (6 "paired" digits) and 3 "unpaired" digits.

So, "orientation" concept is useful for me, but not necessary.

Serg
Serg
2018 Supporter
 
Posts: 732
Joined: 01 June 2010
Location: Russia

Re: Matching minirows analysis

Postby Serg » Sat Jan 23, 2021 10:38 am

Hi, all!
It turns out, my "Matching minirows analysis" is similar to "Braid Analysis", so it is not new.
Thanks to Mladen for his hint.

Nevertheless, I want to post final remark.
It is sufficient to compare 2 independent minirows only to determine not only band's type, but also all digits' orientations. (We can say about digit's orientation, because it participates some minirow triple, which has some orientation.)

Suppose we compare 2 independent minirows, say - M11 and M22.
If minirows have 0 common digits - band is full-matched and all digits have antidiagonal orientation.
If minirows have 1 common digits - band is half-matched, all paired digits have antidiagonal orientation, all unpaired digits have diagonal orientation.
If minirows have 2 common digits - band is half-matched, all paired digits have diagonal orientation, all unpaired digits have antidiagonal orientation.
If minirows have 3 common digits - band is full-matched and all digits have diagonal orientation.

Serg
Serg
2018 Supporter
 
Posts: 732
Joined: 01 June 2010
Location: Russia


Return to General