## Greatest divergance possible in dual solution puzzle?

Everything about Sudoku that doesn't fit in one of the other sections
I had mixed up the grids, the canonicalized versions where from the first two grids posted by JPF, I'll fix it. However, the second example also has this same feature:

Code: Select all
`Clues given:                        23 Cells that are the same:             0Cells that differ in two solutions: 58 168247395943851672572936841231485769857629413496173528389762154625314987714598236 195284367647359821832176954289461735453827619716593248368745192974612583521938476`

After canonicalization:
Code: Select all
`123457689456189237789362154261938745847615392935724861394871526578246913612593478123457689456189237789362154261938745847615392935724861394871526578246913612593478`

The previous record (Red Ed's unavoidable size 55) does not have this property, the two solutions are very different grids.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

ravel wrote:
RW wrote:Both grids are the same...
Wow, like for Gordons famous 16 clue with 2 solutions [where it is obvious]. Does this hold for each [minimal] sudoku with 2 solutions, that have no common cells beside of the givens ?

I think we can at least say: Every puzzle that is a transpose of itself, will have either zero or an even number of solutions, where the all solution grids are pairwise isomorph. Because, for every specific solution grid found, the transpose of that particular grid is also a solution.
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote:I think we can at least say: Every puzzle that is a transpose of itself, will have either zero or an even number of solutions, where the all solution grids are pairwise isomorph. Because, for every specific solution grid found, the transpose of that particular grid is also a solution.
... and because no solution grid can be equal to its own transpose.

Since JPF's puzzle, call it P, is equal to its own transpose, P = tP, and has exactly two solutions, G and H say, it is "obvious" that these solutions must be the transpose of each other, G = tH, and therefore must have the same canonical form. No need for RW and ravel to get excited.

The impressive bit is in actually finding the puzzle P in the first place. We normally improve max/min grids of various types incrementally: finding that huge 58 apparently out of nowhere -- with transposition symmetry to boot -- is something else!
Red Ed

Posts: 633
Joined: 06 June 2005

What does it mean that a puzzle is equal to its own transpose, can you give me a link please?
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:What does it mean that a puzzle is equal to its own transpose, can you give me a link please?
For all givens in the puzzle: ricj=rjci. Or, when rows and columns are interchanged, we get an identical puzzle.

In fact, transposition is only a special case of the more general (borrowing formalism from Red Ed):

If a puzzle, call it P, has exactly two solutions, G and H say, and there exists a sym.op. s such that P = sP, then, (unless both G = sG and H = sH) the solutions must satisfy G = sH, and therefore must have the same canonical form.

Maybe not so obvious? - so somebody should prove or eventually correct this.
Ocean

Posts: 442
Joined: 29 August 2005

ravel wrote:What does it mean that a puzzle is equal to its own transpose, can you give me a link please?

When you rotate it around the \-diagonal, you get the same puzzle.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

ravel wrote:What does it mean that a puzzle is equal to its own transpose, can you give me a link please?

See here.
It’s a main diagonal reflection

t(P)=P because P is diagonal symmetric.

If t is a transformation which keeps the puzzle P equivalent [t(P)~P] such as :
reflections diagonal, antidiagonal, axis
permutation rows, columns, bands, stacks
rotation 90 degrees
permutation of digits

then :

if S(P) is a grid solution of P, t(S(P)) is a solution of t(P).

As a consequence :
if P has n solutions, t(P) has n solutions.
if P has a unique solution, S(t(P)) = t(S(P))

Lemma :
if G is a full grid and if t(G)=G, then t = e (identity transformation)
[not true ; see Red Ed's counterexample in a next post]

If t(P)=P and t#e , then P can’t have a unique solution.
In that case the grid S(P) would be equal to t(S(P)), which is not possible as t#e.
[not true ; end of my post deleted]

JPF
Last edited by JPF on Tue Nov 21, 2006 1:26 pm, edited 1 time in total.
JPF
2017 Supporter

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

Thanks Red Ed and JPF for adjusting/proving the two propositions.
Ocean

Posts: 442
Joined: 29 August 2005

JPF wrote:If t(P)=P and t#e , then P can’t have a unique solution.
In that case the grid S(P) would be equal to t(S(P)), which is not possible as t#e.
No, not true. Here's a counterexample:
Code: Select all
`validity-preserving cell permutation: 99 97 98 93 91 92 96 94 95 79 77 78 73 71 72 76 74 75 89 87 88 83 81 82 86 84 85 39 37 38 33 31 32 36 34 35 19 17 18 13 11 12 16 14 15 29 27 28 23 21 22 26 24 25 69 67 68 63 61 62 66 64 65 49 47 48 43 41 42 46 44 45 59 57 58 53 51 52 56 54 55grid fixed by that permutation: 1 2 3 7 8 9 4 5 6 4 5 6 1 2 3 7 8 9 7 8 9 4 5 6 1 2 3 3 1 2 9 7 8 6 4 5 6 4 5 3 1 2 9 7 8 9 7 8 6 4 5 3 1 2 2 3 1 8 9 7 5 6 4 5 6 4 2 3 1 8 9 7 8 9 7 5 6 4 2 3 1`
Ah, our old friend the canonical grid again ...!
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks Red Ed.
You are right.

The lemma : t # e => t(G) # G is not true.

It is correct, for every G, only for a subset of transformations like :
a reflection
a rotation 90°
a permutation of 2 cols,
a permutation of 2 rows
etc..

JPF
JPF
2017 Supporter

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

ok, maybe this reformulation is easier to prove (eventually one of the subcases) ...

Proposition: If a puzzle, call it P, is equal to its own transformation, P = tP, then for every specific solution grid G found, tG, t(tG), t(t(tG)), ... is also a solution, and all these solutions are either isomorph or equal. Only when G=tG a unique solution can exist.

1) There is a subset of sym.ops T, such that for every t in T, tG<>G for all G.
2) There is a subset M of solution grids, such that for every G in M, tG<>G for all t.
3) There are pairs of (t, G) where t is not in T, G is not in M, such that tG<>G.
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote:Proposition: If a puzzle, call it P, is equal to its own transformation, P = tP, then for every specific solution grid G found, tG, t(tG), t(t(tG)), ... is also a solution, and all these solutions are either isomorph or equal. Only when G=tG a unique solution can exist.
Yes, true. We did this a while ago didn't we? If G contains P then tG contains tP = P, so tG is a solution, as is t(tG) etc. Let k>0 be minimal s.t. (t^k)G = G. Then there are at least k distinct solutions to P, namely (t^i)G, i=0,...,k-1. Having k=1 doesn't imply there's a unique solution though: e.g. consider P={empty grid} and (t,G) are as given in my previous posting.

On your subsequent points (1,2): yes, T contains the transpose op for example; yes, M accounts for nearly all grids in fact.

Your point (3) is proved by noting that t1G2<>G2 where t1 is the validity-preserving cell permutation shown in my previous posting and G2 is the grid preserved by a different permutation shown below:
Code: Select all
`validity-preserving cell permutation: 24 25 26 27 28 29 21 22 23 34 35 36 37 38 39 31 32 33 14 15 16 17 18 19 11 12 13 54 55 56 57 58 59 51 52 53 64 65 66 67 68 69 61 62 63 44 45 46 47 48 49 41 42 43 84 85 86 87 88 89 81 82 83 94 95 96 97 98 99 91 92 93 74 75 76 77 78 79 71 72 73grid fixed by that permutation: 1 2 3 7 8 9 4 5 6 4 5 6 1 2 3 7 8 9 7 8 9 4 5 6 1 2 3 9 1 2 6 7 5 8 3 4 8 3 4 9 1 2 6 7 5 6 7 5 8 3 4 9 1 2 2 9 1 5 6 7 3 4 8 3 4 8 2 9 1 5 6 7 5 6 7 3 4 8 2 9 1`
Red Ed

Posts: 633
Joined: 06 June 2005

When t^2=e (sym. ops, swaps, etc...) is there any specific properties for the solutions of P, for P such that t(P) = P ?

What about the parity of the number of solutions ?

JPF
JPF
2017 Supporter

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

JPF wrote:What about the parity of the number of solutions ?
Even, since no solution grid is equal to its *foo*, where *foo* is any symmetry op of order 2. (Ocean and I did this for *foo* = transpose previously. There are only 6337 symmetry ops that have any fixed grids, and none of those ops have order 2. I'm just trying to find a nice way of describing them now ...)
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:Yes, true. We did this a while ago didn't we? If G contains P then tG contains tP = P, so tG is a solution, as is t(tG) etc. Let k>0 be minimal s.t. (t^k)G = G. Then there are at least k distinct solutions to P, namely (t^i)G, i=0,...,k-1.
[...]

Thank you for the proofs! ... Right, we did something similar ... but not exactly the same, and in a different context.
Ocean

Posts: 442
Joined: 29 August 2005

PreviousNext