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 ?

Postby coloin » Wed Oct 22, 2008 6:39 am

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]


123897654456231987789564321978456213312789546645123879564312798231978465897645132
174852693256931487389764521963417258712589346845623179528396714431278965697145832
.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 1
974356281321784965685219734237891546469573812158462379816927453542638197793145628  - 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 1
123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso

974356281321784965685219734237891546469573812158462379816927453542638197793145628  - grid 2
123586749456179328789243156214758963935612874867394215371865492698421537542937681  - grid 2 iso-1


123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso
123586749456179328789243156214758963935612874867394215371865492698421537542937681  - grid 2 iso-1
123.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 iso
123784659456193782789652143512847936947316528368925417671438295895261374234579861  - grid 2 iso-4
123.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: 1637
Joined: 05 May 2005

Postby Red Ed » Wed Oct 22, 2008 10:17 am

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

Postby coloin » Wed Oct 22, 2008 11:49 am

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

Postby coloin » Wed Oct 22, 2008 12:09 pm

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

Postby StrmCkr » Wed Oct 22, 2008 6:05 pm

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.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby Smythe Dakota » Thu Oct 23, 2008 1:22 am

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: 534
Joined: 11 February 2006

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

Postby gsf » Thu Oct 23, 2008 6:36 am

coloin wrote:next attempt
Code: Select all
123486597456197382789253164817524936564319278392678415671945823248731659935862741  - grid 1 iso
123784659456193782789652143512847936947316528368925417671438295895261374234579861  - grid 2 iso-4
123.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
123486597456197382789253164817524936564319278392678415671945823248731659935862741
123486795458197362769235184817523946546819273392674518671358429285941637934762851

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..1
123486.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

Postby coloin » Thu Oct 23, 2008 8:12 am

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..1
123486.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: 1637
Joined: 05 May 2005

Postby StrmCkr » Thu Oct 23, 2008 3:58 pm

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

on this thread
http://forum.enjoysudoku.com/viewtopic.php?t=6274
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

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

Postby Mauricio » Sat Oct 25, 2008 1:31 pm

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


I can confirm that, though my solver took < 3 mins:D:D:) .
Code: Select all
123486597456197382789253164817524936564319278392678415671945823248731659935862741
123486795458197362769235184817523946546819273392674518671358429285941637934762851
Mauricio
 
Posts: 1174
Joined: 22 March 2006

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

Postby gsf » Sat Oct 25, 2008 2:01 pm

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


I can confirm that, though my solver took < 3 mins:D:D:) .
Code: Select all
123486597456197382789253164817524936564319278392678415671945823248731659935862741
123486795458197362769235184817523946546819273392674518671358429285941637934762851

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 32
123486597456197382789253164817524936564319278392678415671945823248731659935862741
123486795458197362769235184817523946546819273392674518671358429285941637934762851

distance 36
123897654456231987789564321978456213312789546645123879564312798231978465897645132
174852693256931487389764521963417258712589346845623179528396714431278965697145832

distance 32
639845712782913645514627389256139478498576123371284596827351964943768251165492837
639548712781923645524617398256734981497186523318295476872359164943861257165472839
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Sun Oct 26, 2008 3:14 am

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

Postby Red Ed » Sun Oct 26, 2008 11:15 am

The MC (most canonical) grid is an outlier.

A few minutes' random searching gave this, for example ...
Code: Select all
distance = 45
123456789789123456456789123231564897564897231897231564312645978645978312978312645 # MC
647951328813742569925863471458219637362587194179436852784325916236194785591678243

... and a more structured search gave the following, which I think will be hard to beat:
Code: Select all
distance = 48
123456789456789123789123456231564897564897231897231564312645978645978312978312645 # MC
123456789457189236896732514261378945384295167975641328539814672618527493742963851
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Mon Oct 27, 2008 9:41 am

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

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

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

Next

Return to General