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

Everything about Sudoku that doesn't fit in one of the other sections
RW wrote: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?

yes, use the -C option
it computes the distance between each odd/even pair of puzzles on the input
(i.e., puzzle-1 vs puzzle-2, ..., puzzle-i vs puzzle i+1)
gsf
2014 Supporter

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

JPF wrote:
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

It is not hard.
d(A,B) is the hamming distance between A and B, as strings, it is easy to see that d is indeed a metric.

If f is a sudoku morphism (ie, some column, row, number permutations), denote f(A) the sudoku A after we apply the moves defined by f.

Now, D(A,B)=d(f(A),g(B)) for some sudoku morphisms f and g, and it is easy to see that d(f(A),g(B))=d(g^(-1)(f(A)),g^(-1)(g(B)))=d(g^(-1)(f(A)),B), where g^(-1) is the morphism inverse of g.

So D(A,B)=d(h(A),B) for some sudoku morphism h, and D(A,B)=d(A,k(B)) for some morphism k.

Now, D(A,C)+D(C,B)=d(h(A),C)+d(C,k(B))>=d(h(A),k(B))>=D(A,B). QED.
Mauricio

Posts: 1174
Joined: 22 March 2006

Excellent and neat, Mauricio

Thanks.

JPF
JPF
2017 Supporter

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

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

gsf wrote: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`

We can rephrase it as: grid 1 can be transformed into grid 2 by swapping the digit 3 and the digit 4 (where they differ), i.e. if that digit 3 in grid 1 is changed to digit 4, it can lead to grid 2. View in this way, the distance between grid 1 and grid 2 is 1 clue.
Last edited by Addlan on Wed Nov 12, 2008 4:34 pm, edited 1 time in total.

Posts: 62
Joined: 15 July 2005

Addlan wrote:We can rephrase it as: grid 1 can be transformed into grid 2 by swapping the digit 3 and the digit 4 (where they differ), i.e. if that digit 3 in grid 1 is changed to digit 4, it can lead to grid 2. View in this way, the distance between grid 1 and grid 2 is 1 clue.

I was just thinking about this option for measuring distance as well... If this is the measure, then the distance between 2 grids can't be very large. Take for example one of the most distant grid pairs so far:

Code: Select all
`distance 48123456789456789123789123456231564897564897231897231564312645978645978312978312645128453769456179823793682154231867495965341287874295316317526948642938571589714632+---+---+---+|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.`

Only 92 solutions...

How many unavoidable sets are there in the 48 empty cells?

If we define "step" as swapping the digits in an unavoidable set, how many steps are there in the shortest path from the first grid to the next?

If we define "step" as swapping a digit in a puzzle made from the original grid, how many steps are there in the shortest path from the first grid to the next? This should be equal to or less than the steps in the previous question, because by changing one clue we may swap several unavoidable sets.

For the last question, I think we should add that each "step" must lead to another valid puzzle. This way we will also find a collection of grids that lies in between the two original grids.

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

RW wrote:If we define "step" as swapping a digit in a puzzle made from the original grid, how many steps are there in the shortest path from the first grid to the next?

It appears to be a hard question to me - It might be easy to find a path between two grids, but it seems hard to find the shortest path between two grids. No ideas at all at the moment.

Posts: 62
Joined: 15 July 2005

RW wrote:If we define "step" as swapping a digit in a puzzle made from the original grid, how many steps are there in the shortest path from the first grid to the next?

It appears to be a hard question to me - It might be easy to find a path between two grids, but it seems hard to find the shortest path between two grids. No ideas at all at the moment.

I know, it's not an easy task... It should be easy to find if the distance (when swapping given clues) is 1: find all unavoidable sets in the differing cells and find a cell common to all sets.

Example:
Code: Select all
`817596234923471685465283719751829463289634571346715928692358147578142396134967852617593284924187356835246719751829463289634571346751928592468137478312695163975842Distance 30Common cells:.1759.2.492.........52..7197518294632896345713467..928.92..81.7.78..2.9.1..9..8.23 solutions => 2 unavoidable sets, common cell r7c82 52 clue unique puzzles with 51 common givens:.1759.2.492.........52..7197518294632896345713467..928.92..8147.78..2.9.1..9..8.2.1759.2.492.........52..7197518294632896345713467..928.92..8137.78..2.9.1..9..8.2`

Unfortunately, the hamming distance doesn't always help us answer these questions. From the example above we might think that we will have to swap two different unavoidable sets to get from grid one to grid 2. First this set:
Code: Select all
` *--------------------------------* |*8  1  7  | 5  9 *6  | 2 *3  4  | | 9  2 *3  |*4 *7 *1  | 6 *8  5  | |*4 *6  5  | 2 *8 *3  | 7  1  9  | |----------+----------+----------| | 7  5  1  | 8  2  9  | 4  6  3  | | 2  8  9  | 6  3  4  | 5  7  1  | | 3  4  6  | 7 *1 *5  | 9  2  8  | |----------+----------+----------| |*6  9  2  | 3 *5  8  | 1 *4  7  | | 5  7  8  |*1 *4  2  | 3  9  6  | | 1 *3 *4  | 9 *6 *7  | 8 *5  2  | *--------------------------------*`

Then this:
Code: Select all
` *--------------------------------* | 6  1  7  | 5  9  3  | 2  8  4  | | 9  2  4  | 1  8  7  |*6 *3 *5  | | 8  3  5  | 2  4  6  | 7  1  9  | |----------+----------+----------| | 7  5  1  | 8  2  9  | 4  6  3  | | 2  8  9  | 6  3  4  | 5  7  1  | | 3  4  6  | 7  5  1  | 9  2  8  | |----------+----------+----------| |*4  9  2  |*3  6  8  | 1 *5  7  | |*5  7  8  |*4  1  2  |*3  9 *6  | | 1  6  3  | 9  7  5  | 8  4  2  | *--------------------------------*`

However, the two grids actually only differ by only one unavoidable set:
Code: Select all
`  *--------------------------------*  |*8  1 *7  | 5 *9 *6  | 2 *3 *4  |  |*9 *2  3  |*4  7 *1  |*6  8 *5  |  |*4 *6 *5  |*2 *8 *3  |*7 *1  9  |  |----------+----------+----------|  | 7  5 *1  |*8  2 *9  | 4  6 *3  |  | 2 *8 *9  |*6 *3 *4  | 5 *7  1  |  |*3  4  6  |*7 *1  5  |*9 *2 *8  |  |----------+----------+----------|  | 6 *9  2  | 3 *5 *8  |*1  4 *7  |  |*5 *7 *8  |*1 *4  2  | 3 *9 *6  |  |*1 *3 *4  | 9 *6 *7  | 8 *5 *2  |  *--------------------------------*`

(55 clue unavoidable set, found by Red Ed here)

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

RW wrote:Take for example one of the most distant grid pairs so far:

Code: Select all
`distance 48123456789456789123789123456231564897564897231897231564312645978645978312978312645128453769456179823793682154231867495965341287874295316317526948642938571589714632`

It is interesting to know there is a 55-clue unavoidable set. But first of all, I have a question: How do you align the above grid pairs? The alignment should have a strong impact on the number of steps needed.

Posts: 62
Joined: 15 July 2005

Addlan wrote:But first of all, I have a question: How do you align the above grid pairs? The alignment should have a strong impact on the number of steps needed.

gsf's program has been used to find the isomorph of the second puzzle that has the most cells in common with the first grid.

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

RW wrote:gsf's program has been used to find the isomorph of the second puzzle that has the most cells in common with the first grid.

just to be clear, the search finds an isomorph
there could be more than one meeting the distance measure
and each of those could result in a different mapping between the two grids
gsf
2014 Supporter

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

RW wrote:How many unavoidable sets are there in the 48 empty cells?

Code: Select all
`mcgrid 1 #123456789456789123789123456231564897564897231897231564312645978645978312978312645puzzle   #12.45.7.9456..9.237......5.231.6..97.6....2..8.72.....31....9.864.9.8..2....1.6..**grid 2 #128453769456179823793682154231867495965341287874295316317526948642938571589714632puzzle   #12.45.7.9456..9.237......5.231.6..95.65...2..8..2.....31....9.864.9.8.......1.6..`

The unavoidable sets will be specific to the 2 grid solutions here [and the other 90] In all of them the clue in every empty cell will be in at least one unavoidable set.

mcgrid1 needs 3 more clues [many puzzles]
**grid2 needs 2 more clues [only one puzzle]

2 of the 90 have a puzzle with [-0+1} These clues are in all the remaining unavoidable sets in these grid solutions.
Code: Select all
`1a#12.45.7.9456..9.237..3...5.231.6..9..6....2..8..2.....31....9.864.9.8.......1.6..1b#12.45.7.9456..9.237....1.5.231.6..9..6....2..8..2.....31....9.864.9.8.......1.6..1c#12.45.7.9456..9.237......5.231.6..9..6.1..2..8..2.....31....9.864.9.8.......1.6..2a#12.45.7.9456..9.237......5.231.6..9..6...52..8..2.....31....9.864.9.8.......1.6..2b#12.45.7.9456..9.237......5.231.6..9..6....2..8..2..4..31....9.864.9.8.......1.6..`

It would appear there are 17086 puzzles within {-0+3} of the "subpuzzle"

you might be able to go from mcgrid1 to **grid2

C
coloin

Posts: 1877
Joined: 05 May 2005

coloin wrote:
RW wrote:How many unavoidable sets are there in the 48 empty cells?

Code: Select all
`mcgrid 1 #123456789456789123789123456231564897564897231897231564312645978645978312978312645puzzle   #12.45.7.9456..9.237......5.231.6..97.6....2..8.72.....31....9.864.9.8..2....1.6..**grid 2 #128453769456179823793682154231867495965341287874295316317526948642938571589714632puzzle   #12.45.7.9456..9.237......5.231.6..95.65...2..8..2.....31....9.864.9.8.......1.6..`

The unavoidable sets will be specific to the 2 grid solutions here [and the other 90] In all of them the clue in every empty cell will be in at least one unavoidable set.

But that wasn't what I was asking for... I asked for all unavoidable sets in the empty cells. The unavoidable sets that are responsible for the 92 solutions.

coloin wrote:2 of the 90 have a puzzle with [-0+1} These clues are in all the remaining unavoidable sets in these grid solutions.

If it's easier to find unavoidable sets among solved cells instead of empty cells, all unavoidables in the 48 empty cells should be visible in these two grids.

RW
RW
2010 Supporter

Posts: 1010
Joined: 16 March 2006

Here is a puzzle with 2 solutions.
Code: Select all
` *-----------* |1..|2..|3..| |...|.4.|.5.| |...|..6|..7| |---+---+---| |.2.|.8.|...| |9..|...|1..| |..4|..7|...| |---+---+---| |...|9..|2..| |.8.|.3.|.4.| |..7|..1|..6| *-----------*`

The 2 solutions A and B are :
Code: Select all
`179258364632749851845316927726183495958462173314597682563974218281635749497821536146275389798143652352896417521689734973524168864317925415968273689732541237451896`

They differ on 60 cells.
One can get B from A using an unavoidable set with 60 clues.

But... the distance D(A,B)=0
A and B are isomorphic.

JPF
JPF
2017 Supporter

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

RW wrote:How many unavoidable sets are there in the 48 empty cells?
That's not quite what you mean. There are NO unavoidable sets in the empty cells. But there ARE unavoidable sets confined to those positions in either of the original solution grids.

Of course you get different unavoidables depending on which of the two solution grids you're looking at. Here are the minimal unavoidables.

Code: Select all
`grid = 123456789456789123789123456231564897564897231897231564312645978645978312978312645 puz = 12.45.7.9456..9.237......5.231.6..9..6....2..8..2.....31....9.864.9.8.......1.6.. 6 (2) ...................89.........................97.........................78...... 6 (2) ................................4..7..4..7.....7.....4........................... 6 (2) ................................4..7.....7..1.....1..4........................... 6 (2) ......................................4..7..1..7..1..4........................... 6 (2) ........................................................2..5.....5.....2.....2..520 (2) ............78......................5.489..3..97.3.5.4...........5.7.3..97.3...4520 (2) ......................23............5...97.31.97.3.5.............5.7.31297...2..523 (2) ............78........23............5..89..31.97.3.5.............5.7.31297.3.2..5`
... and ...
Code: Select all
`grid = 128453769456179823793682154231867495965341287874295316317526948642938571589714632 puz = 12.45.7.9456..9.237......5.231.6..9..6....2..8..2.....31....9.864.9.8.......1.6.. 4 (2) ....................................9.5.................................5.9...... 6 (2) ........................1.4......4.5.................................5.1.........17 (2) ................................7..5..534...7..4..5.....7.2..4...2.3..7....7.4.3.20 (2) ................................7..5...341..7.....531...7.2..4...2.3.571...7.4.3.26 (2) ..8..3.6....17.8....368.1.4...8..4.5...3.1.8......5.16...5.6.......3..7....7...3.29 (2) ..8..3.6....1..8....368.1.4...8..4.5....41.8......5.16..7526.4...2.3..7......4.3.32 (2) ..8..3.6....1..8....36821.4...8.74.5....41.87.....5.16..7526.4...2....71.....4..233 (2) ..8..3.6....1..8....368.1.4...8.74....5341.8...4..5.16..7526.4...2.3..7....7.4.3.`

Notation is: S (P) U
where S = size of the unavoidable, P = number of permutations of that unavoidable (that have the same footprint), U = the unavoidable itself.
Red Ed

Posts: 633
Joined: 06 June 2005

Excellent demonstration.
Code: Select all
`                          *grid = 128453769456179823793682154231867495965341287874295316317526948642938571589714632 puz = 12.45.7.9456..9.237......5.231.6..9..6....2..8..2.....31....9.864.9.8.......1.6.. 4 (2) ....................................9.5.................................5.9...... 6 (2) ........................1.4......4.5.................................5.1.........17 (2) ................................7..5..534...7..4..5.....7.2..4...2.3..7....7.4.3.20 (2) ................................7..5...341..7.....531...7.2..4...2.3.571...7.4.3.26 (2) ..8..3.6....17.8....368.1.4...8..4.5...3.1.8......5.16...5.6.......3..7....7...3.29 (2) ..8..3.6....1..8....368.1.4...8..4.5....41.8......5.16..7526.4...2.3..7......4.3.32 (2) ..8..3.6....1..8....36821.4...8.74.5....41.87.....5.16..7526.4...2....71.....4..233 (2) ..8..3.6....1..8....368.1.4...8.74....5341.8...4..5.16..7526.4...2.3..7....7.4.3.add 2  ...................................5..5..........................................`

But it also shows another of my erronous assumptions - that every empty cell is envolved in an unavoidable cet. This is not the case eg the 9 @ r3c2 is not envolved in the unavoidable sets in this grid solution.

I wonder what stops the 9 being inserted - apart from the fact it could be an 8.

This clue position 8or9 @r3c2 is defined by the combination of both of the clues which complete the puzzle.

Edit on looking manually,,,this may be another unavoidable set in grid2
Code: Select all
`36  (2) ..8..3.6....1..8...9368.1.4...8.74....5341.8...4..5.16..7526.4...2.3..7..897.4.3.`
coloin

Posts: 1877
Joined: 05 May 2005

PreviousNext