How close together are the isomorphs of two random grids ?

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

Postby Red Ed » Mon Oct 27, 2008 12:57 pm

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

Postby coloin » Mon Oct 27, 2008 1:13 pm

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: 1733
Joined: 05 May 2005

Postby coloin » Mon Oct 27, 2008 1:19 pm

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: 1733
Joined: 05 May 2005

Postby Red Ed » Mon Oct 27, 2008 1:24 pm

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
638751429957842361241963578374689215582317946169425783495176832726538194813294657
724851369361942578589763421436178295892534617157296843675489132248317956913625784
956741328783952461214863579465329817827416935139578642678135294542697183391284756
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Mon Oct 27, 2008 1:43 pm

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: 1733
Joined: 05 May 2005

Postby Mauricio » Mon Oct 27, 2008 2:01 pm

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

Postby coloin » Mon Oct 27, 2008 2:12 pm

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: 1733
Joined: 05 May 2005

Postby coloin » Mon Oct 27, 2008 2:31 pm

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: 1733
Joined: 05 May 2005

Postby Mauricio » Mon Oct 27, 2008 3:54 pm

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

Postby gsf » Mon Oct 27, 2008 4:28 pm

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 48
123456789456789123789123456231564897564897231897231564312645978645978312978312645
128453769456179823793682154231867495965341287874295316317526948642938571589714632
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Mon Oct 27, 2008 10:01 pm

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

Postby coloin » Tue Oct 28, 2008 3:47 am

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: 1733
Joined: 05 May 2005

Postby coloin » Tue Nov 04, 2008 6:46 am

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: 1733
Joined: 05 May 2005

Postby JPF » Sun Nov 09, 2008 4:24 pm

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: 3754
Joined: 06 December 2005
Location: Paris, France

Postby RW » Mon Nov 10, 2008 8:03 am

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: 1000
Joined: 16 March 2006

PreviousNext

Return to General