How close together are the isomorphs of two random grids ?

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

Postby gsf » Mon Nov 10, 2008 8:33 am

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

Postby Mauricio » Mon Nov 10, 2008 10:11 am

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

Postby JPF » Mon Nov 10, 2008 11:20 am

Excellent and neat, Mauricio:)

Thanks.

JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

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

Postby Addlan » Wed Nov 12, 2008 4:29 pm

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..1
123486.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.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Wed Nov 12, 2008 8:33 pm

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 48
123456789456789123789123456231564897564897231897231564312645978645978312978312645
128453769456179823793682154231867495965341287874295316317526948642938571589714632

+---+---+---+
|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: 1000
Joined: 16 March 2006

Postby Addlan » Thu Nov 13, 2008 12:51 am

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.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Thu Nov 13, 2008 2:55 am

Addlan wrote:
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
817596234923471685465283719751829463289634571346715928692358147578142396134967852
617593284924187356835246719751829463289634571346751928592468137478312695163975842
Distance 30

Common cells:
.1759.2.492.........52..7197518294632896345713467..928.92..81.7.78..2.9.1..9..8.2
3 solutions => 2 unavoidable sets, common cell r7c8

2 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: 1000
Joined: 16 March 2006

Postby Addlan » Thu Nov 13, 2008 4:43 am

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

Code: Select all
distance 48
123456789456789123789123456231564897564897231897231564312645978645978312978312645
128453769456179823793682154231867495965341287874295316317526948642938571589714632


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.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Thu Nov 13, 2008 5:39 am

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: 1000
Joined: 16 March 2006

Postby gsf » Thu Nov 13, 2008 6:12 am

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

Postby coloin » Thu Nov 13, 2008 6:23 am

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

Code: Select all
mcgrid 1 #123456789456789123789123456231564897564897231897231564312645978645978312978312645
puzzle   #12.45.7.9456..9.237......5.231.6..97.6....2..8.72.....31....9.864.9.8..2....1.6..

**grid 2 #128453769456179823793682154231867495965341287874295316317526948642938571589714632
puzzle   #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: 1702
Joined: 05 May 2005

Postby RW » Thu Nov 13, 2008 6:43 am

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

Code: Select all
mcgrid 1 #123456789456789123789123456231564897564897231897231564312645978645978312978312645
puzzle   #12.45.7.9456..9.237......5.231.6..97.6....2..8.72.....31....9.864.9.8..2....1.6..

**grid 2 #128453769456179823793682154231867495965341287874295316317526948642938571589714632
puzzle   #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: 1000
Joined: 16 March 2006

Postby JPF » Thu Nov 13, 2008 6:53 am

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
179258364632749851845316927726183495958462173314597682563974218281635749497821536
146275389798143652352896417521689734973524168864317925415968273689732541237451896

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

Postby Red Ed » Thu Nov 13, 2008 10:28 am

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..5
20 (2) ............78......................5.489..3..97.3.5.4...........5.7.3..97.3...45
20 (2) ......................23............5...97.31.97.3.5.............5.7.31297...2..5
23 (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..2
33 (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

Postby coloin » Thu Nov 13, 2008 11:45 am

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..2
33 (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: 1702
Joined: 05 May 2005

PreviousNext

Return to General