## How close together are the isomorphs of two random grids ?

Everything about Sudoku that doesn't fit in one of the other sections
coloin wrote:It should be likely that there are 2 grids which have a minimum [?] distance of 49.
Why

btw, you can't see the 33 common clues between the two previously-listed "distance 48" grids and the MC grid because I didn't apply the relevant isomorphisms. You'll need to use gsf's solver or something to unscramble my grids. (Then fingers crossed you get my claimed distances.)
Red Ed

Posts: 633
Joined: 06 June 2005

Because of the sheer number of other grids.....

Is there not bound to be another grid, if there was 1 in 250,000 which had a min distance of 48 from the MC grid ?

If what you are implying is that a "random grid" has a less extreme distribution than the one you showed for the MC grid then your estimation will tend to be correct.

C
coloin

Posts: 1877
Joined: 05 May 2005

Thanks...... I find it easier to think of a "max similarity" of 33 rather than a "min distance" of 48.........but at least it is clear for me ..[and possibly others !]

C
coloin

Posts: 1877
Joined: 05 May 2005

I'm working on the principle that the MC grid is an outlier, much farther away (on average) from other grids than is usually the case. I've probably checked the distance of the MC grid from 0.01% of all grids, up to isomorphism. I've found five at distance 48 so far (four at random, one by a deterministic search). I'd bet neither for nor against there being a grid at distance 49 from the MC grid, nor for/against there being a pair of grids a distance 49 apart.

I've just gone past 500,000 random grids, so I'll stop now and let the computer have a rest. The results:
Code: Select all
`  22 : 1  23 : 1  25 : 1  26 : 4  27 : 5  28 : 15  29 : 29  30 : 49  31 : 124  32 : 205  33 : 446  34 : 856  35 : 1721  36 : 3354  37 : 6598  38 : 12496  39 : 22614  40 : 38944  41 : 61708  42 : 87889  43 : 105053  44 : 93265  45 : 51271  46 : 12600  47 : 747  48 : 4`

The three new grids at distance 48 (recall "distance" means min Hamming distance after isomorphism) from the MC grid:
Code: Select all
`638751429957842361241963578374689215582317946169425783495176832726538194813294657724851369361942578589763421436178295892534617157296843675489132248317956913625784956741328783952461214863579465329817827416935139578642678135294542697183391284756`
Red Ed

Posts: 633
Joined: 06 June 2005

I think you are the bookmaker on this one !

However, just as we initially thought that the MC grid would have the largest minimal puzzle [36], this turned out incorrect, the symmetry precluded this occurance by a big margin. A random grid [from the pool] easily outstripped it.[39]

Edit - On reflection - the symmetry of the MC grid will work in its favour in the process here !

Two grids which have a max similarity of only 33 clues is exceptional enough - given that two random grids tend to have [~] 49 clues the same - which is somewhat more than I anticipated.

It is impressive you can find the "distance" so quickly. An observation which I found pleasing was that the more numbers you line up - this increases the chances that subsequent numbers will line up - this and the sheer number of isomorphs certainly explains the probable average "max. similarity" ~ 49 clues between two random grids.

C
Last edited by coloin on Mon Oct 27, 2008 10:36 am, edited 1 time in total.
coloin

Posts: 1877
Joined: 05 May 2005

I was wondering how did you calculated the hamming distance so fast, but after a second thought, I think that a well optimized algorithm for finding the hamming distance between MC and any grid can be at least 648 times faster than the general algorithm between any 2 grids.

648 is the number of automorphisms of MC.

Can you tell us your secret, Red Ed?

BTW
Code: Select all
`638751429957842361241963578374689215582317946169425783495176832726538194813294657`
morphes to
Code: Select all
`823159476451367982769482315216834597984675231537291864392746158645918723178523649`
(computation took 10 minutes).
Mauricio

Posts: 1174
Joined: 22 March 2006

Indeed....

The "isomorphic product" is x 648 less when comparing a random grid with the MC grid - so less chance of a match up.

Whats the distribution of distance for this grid [approx] ?
Code: Select all
`174852693256931487389764521963417258712589346845623179528396714431278965697145832`

This is the other solution grid [no U6] [along with the MC - no U4] in my first post to this thread !

C
coloin

Posts: 1877
Joined: 05 May 2005

For casual observerrs of this forum.

The MC grid
Code: Select all
`+---+---+---+|123|456|789||789|123|456||456|789|123|+---+---+---+|231|564|897||564|897|231||897|231|564|+---+---+---+|312|645|978||645|978|312||978|312|645|+---+---+---+`

It has 3 repeating minirows in all the 6 bands - so called Most Canonical grid.

It has 648-way automorphism. [total number of isomorphs - 9! * 6^8 *2 / 648]

It also has no U4 sets - seen as 4 clue URs in some puzzles.
Last edited by coloin on Mon Oct 27, 2008 11:25 pm, edited 1 time in total.
coloin

Posts: 1877
Joined: 05 May 2005

coloin wrote:Whats the distribution of distance for this grid [approx] ?
Code: Select all
`174852693256931487389764521963417258712589346845623179528396714431278965697145832`

Did you mean the hamming distance? 36
Code: Select all
`186753429739124856452689173294861537563497281817235964375942618641578392928316745`
Mauricio

Posts: 1174
Joined: 22 March 2006

Red Ed wrote:btw, you can't see the 33 common clues between the two previously-listed "distance 48" grids and the MC grid because I didn't apply the relevant isomorphisms. You'll need to use gsf's solver or something to unscramble my grids. (Then fingers crossed you get my claimed distances.)

48 confirmed
here is one distance 48 map
Code: Select all
`distance 48123456789456789123789123456231564897564897231897231564312645978645978312978312645128453769456179823793682154231867495965341287874295316317526948642938571589714632`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Mauricio wrote:I was wondering how did you calculated the hamming distance so fast, but after a second thought, I think that a well optimized algorithm for finding the hamming distance between MC and any grid can be at least 648 times faster than the general algorithm between any 2 grids.

648 is the number of automorphisms of MC.

Can you tell us your secret, Red Ed?

It's exactly as you stated above. Well spotted ;-)
Red Ed

Posts: 633
Joined: 06 June 2005

It is related to the automorphs of course !

gsfs example gives a subpuzzle with
Code: Select all
`+---+---+---+|12.|45.|7.9||456|..9|.23||7..|...|.5.|+---+---+---+|231|.6.|.9.||.6.|...|2..||8..|2..|...|+---+---+---+|31.|...|9.8||64.|9.8|...||...|.1.|6..|+---+---+---+ 92 grid solutions.`

The mc grid doent have valid a puzzle with a {+2}.
The other grid has one.

The reduced total amount of "different" puzzles inherent in the MC grid is the reason the two grids dont get near sharing a pseudopuzzle.

Red Eds distance distribution stat. for the MC grid, for >500,000 random grids. Average [mode] distance is 43.
Code: Select all
`  22 : 1  23 : 1  25 : 1  26 : 4  27 : 5  28 : 15  29 : 29  30 : 49  31 : 124  32 : 205  33 : 446  34 : 856  35 : 1721  36 : 3354  37 : 6598  38 : 12496  39 : 22614  40 : 38944  41 : 61708  42 : 87889  43 : 105053  44 : 93265  45 : 51271  46 : 12600  47 : 747  48 : 4`

I think this will be born out if we can [slowly] compute a brief distance distribution stat for a random grid . [Average [mode] distance ~32 ?]

And [perhaps not quite so slowly] for this grid
Code: Select all
`174852693256931487389764521963417258712589346845623179528396714431278965697145832`

which has automorphism-72.

C
coloin

Posts: 1877
Joined: 05 May 2005

Bearing in mind that the mc grid is an out lier - further away from most other grids on average....

I suspected that the puzzles from the mc grid therefore would possibly be more remote.

Nothing could be more wrong !

Code: Select all
`+---+---+---+|.2.|...|.8.||..9|1..|...||4..|7..|.23|+---+---+---+|..1|5..|...||...|.9.|23.||...|.3.|..4|+---+---+---+|3..|.45|9..||..5|...|...||.78|...|6..|+---+---+---+ All clues mutable.`

A 23 clue chameleon puzzle was very easily generated !!!!!! [1 puzzle in 250]

Remarkable - the smallest previous one of these puzzles had 34 clues - and there was not one found in an extensive search of 66M / 225M random puzzles

The mc grid despite being furthest away from most grids - appears to share clues with a lot too.
coloin

Posts: 1877
Joined: 05 May 2005

here Mauricio and I wrote:
Mauricio wrote:I would think that a better definition of distance is this:

D(A,B)=min{d(A,B):A~A', B~B'}, using the d function defined by JPF.

In this new metric it is trivial that D(A,B)=D(A',B') if A~A' and B~B'. We would want this, as properties of sudokus besides aesthetics should be independent of isomorphism.

I think that's a good idea.

It has to be proved that D is a distance on the quotient set S/~

D(A,B)=0 then min{d(A',B'): A'~A, B'~B}=0.
so there are A' and B' such that d(A',B')=0 .
As d is a distance, A'=B' with A'~A and B'~B.
Finally A~B.

I don't have any proof (or counter example) that D(A,B)<=D(A,C)+D(C,B)
Any idea ?
JPF

I'm still looking for a smart proof that D is a metric distance
or isn't

JPF
JPF
2017 Supporter

Posts: 4014
Joined: 06 December 2005
Location: Paris, France

Joining the discussion a bit late...

I guess gsf's solver can be used to calculate the hamming distance, or? If so, what command should I use?

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

PreviousNext