The New Sudoku Players' Forum

[gsf]

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)

[Mauricio]

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.

[JPF]

Excellent and neat, Mauricio

Thanks.

JPF

[Addlan]

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.

[RW]

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

[Addlan]

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.

[RW]

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

[Addlan]

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.

[RW]

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

[gsf]

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

[coloin]

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

[RW]

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.

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

[JPF]

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

[Red Ed]

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.

[coloin]

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.