Grid Momentum

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

Grid Momentum

Postby dobrichev » Mon Oct 11, 2010 11:55 pm

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 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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Grid Momentum

Postby AR4793 » Tue Oct 12, 2010 3:46 am

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 :oops: )

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

Postby AR4793 » Tue Oct 12, 2010 4:29 am

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

Postby dobrichev » Tue Oct 12, 2010 3:09 pm

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: 1311
Joined: 24 May 2010

Re: Grid Momentum

Postby AR4793 » Tue Oct 12, 2010 11:14 pm

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

Postby eleven » Wed Oct 13, 2010 3:48 pm

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: 1534
Joined: 10 February 2008


Return to General