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

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

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

StrmCkr wrote:i belive all puzzles are formed form a automorphic grid in the first place....

i perhaps think that what he meant was you can get a puzzle from an automorphic grid, remove a few clues and add a few different ones - and be able to get a new puzzle for every one of the 5e^9 essentially different grids.

This boggling assertion is that all grids can be shown to be pretty close to an isomorph of every other different grid. - they might share a puzzle with n identical clues..

Heres an example derived from one extreme solution grid / puzzle.
Code: Select all
`+---+---+---+|...|...|...||.56|.31|.87||.89|.64|.21|+---+---+---+|...|...|...||.12|.89|.46||.45|.23|.79|+---+---+---+|...|...|...||.31|.78|.65||.97|.45|.32|+---+---+---+  pseudopuzzle  with 2 solution grids  [36 clues]123897654456231987789564321978456213312789546645123879564312798231978465897645132174852693256931487389764521963417258712589346845623179528396714431278965697145832.2........56.31.87.89.64.21..........12.89.46.45.23.79..........31.78.65.97.45.32 - 1 sol..7........56.31.87.89.64.21..........12.89.46.45.23.79..........31.78.65.97.45.32 - 1 sol.`

Each solution grid can have at least 10^13 essentially different puzzles.
Each one of these puzzles has 9! * 6^8 * 2 isomorphs.

There are certainly enough puzzles for this to be a possibility !

To test this:

here are two random grids

Code: Select all
`639845712782913645514627389256139478498576123371284596827351964943768251165492837  - grid 1974356281321784965685219734237891546469573812158462379816927453542638197793145628  - grid 2`

Do any of their isomorphs share at least one pseudopuzzle [with 2 solutions]

I would say probably ......but it might be difficult to find it !

Heres my first attempt, both grids are morphed to have these clues - easy.
Code: Select all
`+---+---+---+ |123|...|...| |456|1..|...| |789|...|1..| +---+---+---+ |.1.|...|...| |...|.1.|...| |...|...|.1.| +---+---+---+ |..1|...|...| |...|..1|...| |...|...|..1| +---+---+---+`

Code: Select all
`639845712782913645514627389256139478498576123371284596827351964943768251165492837  - grid 1123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso974356281321784965685219734237891546469573812158462379816927453542638197793145628  - grid 2123586749456179328789243156214758963935612874867394215371865492698421537542937681  - grid 2 iso-1123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso123586749456179328789243156214758963935612874867394215371865492698421537542937681  - grid 2 iso-1123.86...4561..3..7892.31...1....9......1..7........15.71..5.....8..1...........1  - 28 clues -  86887 sol`

next attempt
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso123784659456193782789652143512847936947316528368925417671438295895261374234579861  - grid 2 iso-4123.8....45619..82789.5.1...1....936...31...83.....41.671...........1....3......1  - 32 clues -   2471 sol`

We have 2 random grids - they have 32 common clues !

How far can we take this ?
coloin

Posts: 1877
Joined: 05 May 2005

How about: grid 1 = one with a U4 in it; grid 2 = grid 1 with the U4 transposed. 77 clues in common.
Red Ed

Posts: 633
Joined: 06 June 2005

I believe you are correct !

But two random grids - on average - are very unlikely to be that similar !

The two [random] grids that I chose might have a puzzle each which has n common clues and 2 non-common clues.

In which case what is the lowest sol count for these n clues ?
coloin

Posts: 1877
Joined: 05 May 2005

Thinking about it .......it possibly is very likely that there woud be two puzzles with n+1 different clue for these two random grids.

Take one grid, it has 9!*6^8*2 isomorphs.
There are perhaps 10^13 [minimal] puzzles with 25 clues per each grid.
There are 25 subpuzzles each with 24 clues - perhaps each having 20 grid solutions.

This is way above the 6*10^21 number.

C
coloin

Posts: 1877
Joined: 05 May 2005

glad to see some one takes an intrest
in what i have to say on stuff

and can actually help me go further with my own theories

oringall i started thinking on it from the "sudoku space thread" on here somewhere...

which eventually goes back to my theory how may of them could be "transformed" via box-box back into one another?

which is where i postulated that all puzzles in partial form are related to an automorphick grid but lacking full similarity due to changed clues (adding removing of clues given permations of boxes...

my oringal postulation was that grids identical (issomorphich) given changse can be come n many similar grids. (perhaps they are still identical if no clues are "added or removed"

as each grid has n many mutations restricted by the givens....
and conversly have many identical clues -

which could or would have similar or identical restrictions in line of sight,

yielding a limitation to how many grids it could produce with out adding or removing those clues...

but if you start adding clues you would increase the similar grids count and decress its mutablity at the same time.

or if you remove clues you free up mutablity and potential leave no similar or alike grids with 1 solution count...
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1134
Joined: 05 September 2006

Along these lines, here is another interesting question.

Given two non-isomorphic grids A and B, what is the largest number N of cells which some isomorph of A has in common with some isomorph of B? In other words, how can you "isomorphisize" A and B so that the isomorphs are as close to identical as possible?

Of course, if A and B are isomorphic, then N is 81.

What is the largest possible value of N for non-isomorphic grid pairs? I think it's clear that N can be no larger than 77. (If you change one cell, you must also change another cell in the same row, and another in the same column, and another in the fourth corner of the resulting rectangle.)

Can anybody actually come up with two non-isomorphic grids in which 77 of the 81 cells contain the same values? (And can you actually prove that your two grids are not isomorphic)?

Bill Smythe
Smythe Dakota

Posts: 563
Joined: 11 February 2006

### Re: How close together are the isomorphs of two random grids

coloin wrote:next attempt
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso123784659456193782789652143512847936947316528368925417671438295895261374234579861  - grid 2 iso-4123.8....45619..82789.5.1...1....936...31...83.....41.671...........1....3......1  - 32 clues -   2471 sol`

We have 2 random grids - they have 32 common clues !

How far can we take this ?

using the -C option of my solver (still working on getting the windows version to package properly)
it finds a minimum hamming distance of 32 in ~10min
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851`

which results in a pseudo puzzle with 49 common clues
Code: Select all
`123486.9.45.1973.27.92..1.481752.9.65...1927.39267..1.671....2.2....16..93..62..1`

adding one clue to each results in two non-isomorphic 50 clue puzzles with 49 clues in common
Code: Select all
`123486.9.45.1973.27.92..1.481752.9.65...1927.39267..1.671....2.2....163.93..62..1123486.9.45.1973.27.92..1.481752.9.65...1927.39267..1.671....2.2....164.93..62..1`
gsf
2014 Supporter

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

Bill - i think finding two non-isomorphic grids which differ only by 4 cells is somewhat easy.

gsf [thanks] has shown that we can find many common clues in a random grid [constant] and scrolling through the isomorphs of another random grid. there will be many puzzle pairs from the two grids where the puzzles differ by only one clue.

Code: Select all
`123486.9.45.1973.27.92..1.481752.9.65...1927.39267..1.671....2.2.8..16..93..62..1123486.9.45.1973.27.92..1.481752.9.65...1927.39267..1.671....2.2..9.16..93..62..1`

It must be a product of the number of puzzles and the number of isomorphs.

So it is probably quite likely that almost all grids will do this - even markedly different grids like the two in my first post. [one no u6, the other no u4]
coloin

Posts: 1877
Joined: 05 May 2005

thanks colin and gsf. so how are they more identical

or perhapse are issomorhic but not consdering the definition of issomporhs..?

i belive it comes down to where the line of sight restrictins interact.

Given two non-isomorphic grids A and B, what is the largest number N of cells which some isomorph of A has in common with some isomorph of B? In other words, how can you "isomorphisize" A and B so that the isomorphs are as close to identical as possible?

i am tryign to do this with box to box rotations using line of sights
. instead of the accepted "issomoph identities" to unie issomporhs to non issomphic grids

http://forum.enjoysudoku.com/viewtopic.php?t=6274
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1134
Joined: 05 September 2006

### Re: How close together are the isomorphs of two random grids

gsf wrote:it finds a minimum hamming distance of 32 in ~10min
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851`

I can confirm that, though my solver took < 3 mins .
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851`
Mauricio

Posts: 1174
Joined: 22 March 2006

### Re: How close together are the isomorphs of two random grids

Mauricio wrote:
gsf wrote:it finds a minimum hamming distance of 32 in ~10min
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851`

I can confirm that, though my solver took < 3 mins .
Code: Select all
`123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851`

thanks, I don't know what machine I timed it on, but it takes ~2m10s on my home machine
for each of the three examples
Code: Select all
`distance 32123486597456197382789253164817524936564319278392678415671945823248731659935862741123486795458197362769235184817523946546819273392674518671358429285941637934762851distance 36123897654456231987789564321978456213312789546645123879564312798231978465897645132174852693256931487389764521963417258712589346845623179528396714431278965697145832distance 32639845712782913645514627389256139478498576123371284596827351964943768251165492837639548712781923645524617398256734981497186523318295476872359164943861257165472839`
gsf
2014 Supporter

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

Back to the Sudoku space, what is the greatest distance beetween 2 sudokus ?

See the definition of the distance beetween 2 sudokus A and B :
here

JPF
JPF
2017 Supporter

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

The MC (most canonical) grid is an outlier.

A few minutes' random searching gave this, for example ...
Code: Select all
`distance = 45123456789789123456456789123231564897564897231897231564312645978645978312978312645 # MC647951328813742569925863471458219637362587194179436852784325916236194785591678243`

... and a more structured search gave the following, which I think will be hard to beat:
Code: Select all
`distance = 48123456789456789123789123456231564897564897231897231564312645978645978312978312645 # MC123456789457189236896732514261378945384295167975641328539814672618527493742963851`
Red Ed

Posts: 633
Joined: 06 June 2005

The distance of 250,000 random grids from the MC grid:
Code: Select all
`  25 : 1  26 : 1  27 : 1  28 : 5  29 : 11  30 : 21  31 : 64  32 : 102  33 : 222  34 : 435  35 : 890  36 : 1705  37 : 3385  38 : 6247  39 : 11386  40 : 19409  41 : 30820  42 : 43835  43 : 52518  44 : 46643  45 : 25641  46 : 6301  47 : 356  48 : 1`

Here's the randomly-discovered grid at distance 48 (different to the one from the structured search):
Code: Select all
`325961478974852361861743529436518297289437615157296843548679132693125784712384956`

I suppose it's conceivable that some of the grids at distance 45+ from the MC grid might be made more distant still by "tweaking" them a little (e.g. permuting some small unavoidables), but I don't think I'll bother trying.
Red Ed

Posts: 633
Joined: 06 June 2005

Just to clarify......

We have shown that it is fairly easy to get two random grids to have a minimum distace of 32 - which means there are 49 common clues - and subsequent {+1} puzzles are easy to spot.

Red Ed has taken the MC grid - and found by both search and random methods a grid which has a [? minimum] distance of 48.......does this mean that the best isomorph of this puzzle has only 33 common clues ?

However - in both examples however I dont see the 33 common clues !.

It should be likely that there are 2 grids which have a minimum [?] distance of 49. But unlikely to be found easily.

C
coloin

Posts: 1877
Joined: 05 May 2005

Next