The New Sudoku Players' Forum

[RW]

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:             0
Cells that differ in two solutions: 58
168247395943851672572936841231485769857629413496173528389762154625314987714598236
195284367647359821832176954289461735453827619716593248368745192974612583521938476

After canonicalization:

Code: Select all

123457689456189237789362154261938745847615392935724861394871526578246913612593478
123457689456189237789362154261938745847615392935724861394871526578246913612593478

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

RW

[Ocean]

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.

[Red Ed]

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!

[ravel]

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

[Ocean]

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.

[daj95376]

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.

[JPF]

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

[Ocean]

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

[Red Ed]

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 55

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

[JPF]

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

[Ocean]

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.

[Red Ed]

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 73

grid 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

[JPF]

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

[Red Ed]

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

[Ocean]

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.