Greatest divergance possible in dual solution puzzle?

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

Postby RW » Sun Nov 19, 2006 9:56 pm

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Ocean » Sun Nov 19, 2006 10:11 pm

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

Postby Red Ed » Sun Nov 19, 2006 10:51 pm

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

Postby ravel » Mon Nov 20, 2006 12:13 am

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

Postby Ocean » Mon Nov 20, 2006 1:05 am

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

Postby daj95376 » Mon Nov 20, 2006 3:33 am

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

Postby JPF » Mon Nov 20, 2006 9:14 am

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

Postby Ocean » Mon Nov 20, 2006 10:34 am

Thanks Red Ed and JPF for adjusting/proving the two propositions.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Red Ed » Mon Nov 20, 2006 11:38 pm

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 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 ...!:)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Tue Nov 21, 2006 1:30 am

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

Postby Ocean » Tue Nov 21, 2006 11:24 am

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

Postby Red Ed » Tue Nov 21, 2006 3:23 pm

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 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
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Tue Nov 21, 2006 5:48 pm

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

Postby Red Ed » Tue Nov 21, 2006 9:24 pm

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

Postby Ocean » Tue Nov 21, 2006 10:12 pm

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

Return to General