## Grid Momentum

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

### Grid Momentum

There are 6670903752021072936960 valid sudoku solution grids.
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 789456 789 123798 231 564234 675 918815 943 276967 812 435379 164 852582 397 641641 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      +12      -13      +14      +15      -16      +17      +18      +19      -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) = 9abs(8 * +1 + 1 * -1) = 7abs(7 * +1 + 2 * -1) = 5abs(6 * +1 + 3 * -1) = 3abs(5 * +1 + 4 * -1) = 1abs(4 * +1 + 5 * -1) = 1abs(3 * +1 + 6 * -1) = 3abs(2 * +1 + 7 * -1) = 5abs(1 * +1 + 8 * -1) = 7abs(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)) = 9Band 2:  abs(sum(+1,-1,+1,+1,-1,+1,+1,+1,-1)) = 3Band 3:  abs(sum(+1,+1,+1,+1,+1,+1,+1,+1,+1)) = 9Stack 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)) = 3Stack 3: abs(sum(-1,+1,+1,-1,+1,-1,-1,+1,-1)) = 1SF Grid Momentum = sum(9,3,9,3,3,1) = 26`

This is Pt grid.

Code: Select all
`123 456 789457 189 326689 327 154231 645 897745 891 632896 732 541318 264 975574 918 263962 573 418`

Code: Select all
`Band 1:  abs(sum(+1,-1,-1,-1,-1,+1,+1,-1,-1)) = 3Band 2:  abs(sum(+1,-1,-1,-1,-1,+1,+1,-1,-1)) = 3Band 3:  abs(sum(+1,+1,-1,-1,+1,+1,+1,+1,-1)) = 3Stack 1: abs(sum(+1,+1,+1,-1,-1,+1,-1,+1,+1)) = 3Stack 2: abs(sum(+1,-1,-1,-1,-1,-1,-1,+1,+1)) = 3Stack 3: abs(sum(+1,-1,-1,+1,+1,-1,+1,+1,+1)) = 3Pt 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)) = 1SF 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)) = 9SF 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.
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010

### Re: Grid Momentum

Don't think your analysis is right... But it is along the line I was thinking.

Ed Russell and Frazer Jarvis analysis at
http://www.afjarvis.staff.shef.ac.uk/su ... group.html
indicate that there are:
(edited oct 12 to fix link )

Code: Select all
`  5,472,706,619 G-classes split into two H-classes. (H+, H-)         23,919 G-classes give a single H-class (H*)  ----------------  5,472,730,538`

The each unique solution grid in H* class doesn't have a mirror image
Each H+ has a corresponding H- which is its mirror image.

I'm thinking you have to look at some sort ("row parity") \$ ("column parity") where \$ is as of yet some undefined operator. The operation yields 3 values ( -1, 0 and +1.)

In other words for the 23,919 unique solution grids that have no mirror image the operation always yields 0 no matter how you switch towers, floors, rows and columns.

There are 5,472,706,619 grids which will always give +1

There are 5,472,706,619 grids which will always give -1

Code: Select all
`   5,472,706,619 H+ grids   5,472,706,619 H- grids          23,919 H* grids  ----------------  10,945,437,157 unique grids if you don't consider transposition `

Looking back at the 15 puzzle, the count was based on how often the digits were out of order. Just looking at 3 digit groups as an example 123 has no digits out of order whereas 321 has 3 ( 3 before 2, 3 before 2, and 2 before 3). Not sure how to swizzle all this together but somehow I think it fits.

So I think the way to start to figure this out is to find a member of the H* class, and a matched pair H+ and H-. Of course given H+ you just transpose to get H-.

I think all of this would lead to some simplification of how many permutations of a solution grid that you'd need to check to see what canonical form is correct.
Last edited by AR4793 on Tue Oct 12, 2010 11:09 pm, edited 1 time in total.
AR4793

Posts: 13
Joined: 26 September 2010

### Re: Grid Momentum

I've been learning....

Actually the "momentum" function should work for 2x2 Shi Doku also. Shi doku has two essentially different grids one which has a mirror image and one which doesn't.

Regards,
Herb
AR4793

Posts: 13
Joined: 26 September 2010

### Re: Grid Momentum

In this post dpbobelisk pointed that momentum approach overlaps Braid Analysis.

AR4793 wrote:Ed Russell and Frazer Jarvis analysis at
http://www.afjarvis.staff.shef.ac.uk/su ... group.html
indicate that there are...

The link is incomplete. If you meant the H classes in http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html then this is not the same matter.
This approach is to remove as much as possible restrictions instead of adding more.
Although inspired by your good analogy with the slide puzzles, this approach is not a Parity definition.

MD
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010

### Re: Grid Momentum

dobrichev wrote: ...
Although inspired by your good analogy with the slide puzzles, this approach is not a Parity definition.
MD

Thank you for the clarification. I didn't understand the idea long well enough to understand what you were doing. Sorry I injected something that really had nothing to do with the thread that you started.

Regards,
Herb
AR4793

Posts: 13
Joined: 26 September 2010

### Re: Grid Momentum

Hi dobrichev,

i agree, when you exchange the numbers in an UA of a grid, you get a very related grid, while 2 other grids with the same hamming distance would be much less related, when
you have to change numbers in a way, which destroys or invents an UA.

So it would be nice to know more about these grid families.
eleven

Posts: 2280
Joined: 10 February 2008