Allowing so called Validity Preserving Transformations (transpose, bands exchange, rows in a band exchange, relabel), each valid grid can be transformed to one of the 5472730538 Essentially Different Grids.
This means that this space is disconnected, and consists of 5472730538 disjoint partitions.
What happens if extending the allowed transformations to permutation of digits within a (minimal, irreducible) unavoidable set?
Transforming grids in such way preserves cells out of the UA set and their mutuality.
Also this is a possibile alternative to define a metric in grids space (how close 2 grids are).
Is this space connected? How to classify the grids and obtain partitions?
Let "Spin" of the cell within a chute of the sudoku solution grid be the relative position of the same digit in the next box.
Take a band from a valid grid.
Take a digit.
Trace the row change of the digit in the next box, moving from left to right.
If the next row is one row down (or two up when overlapping), then the spin for this digit is +1.
Othervise the spin is -1.
Example:
This is the SF grid.
- Code: Select all
123 456 789
456 789 123
798 231 564
234 675 918
815 943 276
967 812 435
379 164 852
582 397 641
641 528 397
Spin for all digits of band 1 is -1 as all they move upwards.
Spin for digits in band 2 is:
- Code: Select all
digit spin
===== ====
1 +1
2 -1
3 +1
4 +1
5 -1
6 +1
7 +1
8 +1
9 -1
Let "Chute momentum" be the absolute value of the sum of the digit spins within the chute.
Let "Grid momentum" be the sum of all 6 chutes (3 bands + 3 stacks) momentum.
Exchanging 2 rows within a band reverses the spin of all digits but is invariant to chute momentum.
Exchanging 2 stacks (2 boxes within a band) reverses the spin of all digits but is invariant to chute momentum.
Exchanging bands and stacks doesn't affect the grid momentum.
Rotating the grid doesn't affect the grid momentum.
Lelabeling (permuting symbols) doesn't affect the chute or grid momentum. We can replace "digit" with the "value of the cell n", where n is either number of the cell within the first box or within the first row.
Therefore, the Grid Momentum is invariant under Validity Preserving Transformations.
Possible values for chute momentum are (1,3,5,7,9):
- Code: Select all
abs(9 * +1 + 0 * -1) = 9
abs(8 * +1 + 1 * -1) = 7
abs(7 * +1 + 2 * -1) = 5
abs(6 * +1 + 3 * -1) = 3
abs(5 * +1 + 4 * -1) = 1
abs(4 * +1 + 5 * -1) = 1
abs(3 * +1 + 6 * -1) = 3
abs(2 * +1 + 7 * -1) = 5
abs(1 * +1 + 8 * -1) = 7
abs(0 * +1 + 9 * -1) = 9
Note: Some of the combinations may be impossible.
Let calculate the momentum of SF grid.
- Code: Select all
Band 1: abs(sum(-1,-1,-1,-1,-1,-1,-1,-1,-1)) = 9
Band 2: abs(sum(+1,-1,+1,+1,-1,+1,+1,+1,-1)) = 3
Band 3: abs(sum(+1,+1,+1,+1,+1,+1,+1,+1,+1)) = 9
Stack 1: abs(sum(-1,+1,+1,+1,-1,+1,+1,-1,+1)) = 3 (assuming moving top-down a position change to left gives +1)
Stack 2: abs(sum(+1,+1,-1,-1,-1,-1,-1,+1,-1)) = 3
Stack 3: abs(sum(-1,+1,+1,-1,+1,-1,-1,+1,-1)) = 1
SF Grid Momentum = sum(9,3,9,3,3,1) = 26
This is Pt grid.
- Code: Select all
123 456 789
457 189 326
689 327 154
231 645 897
745 891 632
896 732 541
318 264 975
574 918 263
962 573 418
- Code: Select all
Band 1: abs(sum(+1,-1,-1,-1,-1,+1,+1,-1,-1)) = 3
Band 2: abs(sum(+1,-1,-1,-1,-1,+1,+1,-1,-1)) = 3
Band 3: abs(sum(+1,+1,-1,-1,+1,+1,+1,+1,-1)) = 3
Stack 1: abs(sum(+1,+1,+1,-1,-1,+1,-1,+1,+1)) = 3
Stack 2: abs(sum(+1,-1,-1,-1,-1,-1,-1,+1,+1)) = 3
Stack 3: abs(sum(+1,-1,-1,+1,+1,-1,+1,+1,+1)) = 3
Pt Grid Momentum = sum(3,3,3,3,3,3) = 18
Now we know that Grid Momentum varies from grid to grid.
What happens with U4 (unavoidable rectangle, unavoidable set of size 4) permutation?
Back to SF grid. It has U4 at r3c7,r6c9 for digits 4 and 5.
- Code: Select all
U4 mask SF UA swapped
=========== =========== ===========
... ... ... 123 456 789 123 456 789
... ... ... 456 789 123 456 789 123
... ... *.* 798 231 564 798 231 465
... ... ... 234 675 918 234 675 918
... ... ... 815 943 276 815 943 276
... ... *.* 967 812 435 967 812 534
... ... ... 379 164 852 379 164 852
... ... ... 582 397 641 582 397 641
... ... ... 641 528 397 641 528 397
The band momentum remains unchanged for all three bands.
Stacks 1 and 2 are not touched.
In stack 3 digit 4 reverts spin from -1 to +1, but also digit 5 reverts spin from +1 to -1, leaving stack momentum unchanged.
- Code: Select all
SF Stack 3 momentum: abs(sum(-1,+1,+1,-1,+1,-1,-1,+1,-1)) = 1
SF UA swapped Stack 3 momentum: abs(sum(-1,+1,+1,+1,-1,-1,-1,+1,-1)) = 1
Applying Validity Preserving Transformations, every U4 can be transformed to occupy the same cells.
So, the Grid Momentum is invariant under U4 permutations.
Therefore, it is impossible to transform SF grid to Pt grid by any sequence of U4 permutations because they differ in Grid Momentum.
On the other hand, it is obviously that allowing only U4 permutations keeps space disconnected since there are much grids without U4 at all.
Let see what happens with U6. SF has one at r1c1, r1c4, r1c7, r2c1, r2c4, r2c7. Swap 1 and 4 in box 1; 4 and 7 in box 2; 1 and 7 in box 3.
- Code: Select all
U6 mask SF UA swapped
=========== =========== ===========
*.. *.. *.. 123 456 789 423 756 189
*.. *.. *.. 456 789 123 156 489 723
... ... ... 798 231 564 798 231 564
... ... ... 234 675 918 234 675 918
... ... ... 815 943 276 815 943 276
... ... ... 967 812 435 967 812 435
... ... ... 379 164 852 379 164 852
... ... ... 582 397 641 582 397 641
... ... ... 641 528 397 641 528 397
Band 2 and 3 are untouched.
Stacks preserve momentum since the only changes are within the minicolumns.
- Code: Select all
SF Band 1 momentum: abs(sum(-1,-1,-1,-1,-1,-1,-1,-1,-1)) = 9
SF UA swapped Band 1 momentum: abs(sum(+1,-1,-1,+1,-1,-1,+1,-1,-1)) = 3
So, the Grid Momentum is NOT invariant under U6 permutations. At least for this type of 3-digit U6. And defined in exactly this way.
)