The New Sudoku Players' Forum

[coloin]

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 ?

[Red Ed]

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

[coloin]

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]

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

[StrmCkr]

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

[Smythe Dakota]

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

[gsf]

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


[coloin]

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]

[StrmCkr]

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

[Mauricio]

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 .

Code: Select all

123486597456197382789253164817524936564319278392678415671945823248731659935862741
123486795458197362769235184817523946546819273392674518671358429285941637934762851


[gsf]

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 .

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


[JPF]

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

[Red Ed]

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]

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.

[coloin]

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