The New Sudoku Players' Forum

[Red Ed]

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.)

[coloin]

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]

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

[Red Ed]

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

[coloin]

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

[Mauricio]

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).

[coloin]

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]

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.

[Mauricio]

Whats the distribution of distance for this grid [approx] ?

Code: Select all

174852693256931487389764521963417258712589346845623179528396714431278965697145832

Did you mean the hamming distance? 36

Code: Select all

186753429739124856452689173294861537563497281817235964375942618641578392928316745


[gsf]

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


[Red Ed]

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 ;-)

[coloin]

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]

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.

[JPF]

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

[RW]

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