The New Sudoku Players' Forum

by **ravel** » Wed Jan 17, 2007 6:21 pm

tarek wrote:I assume that the box symmetry you're referring to is the horizontal & vertical symmetries

No, i took the word from gurth here, i mean the symmetry, where like in the morphed grid to gurths puzzle above, either
b1=b6=b8, b2=b4=b9 and b3=b5=b7
or (isomorphic)
b1=b5=b9, b2=b6=b7 and b3=b4=b8
This is a special form (each number is mapped to itself) of what Mauricio called threefold diagonal symmetry.

by **tarek** » Wed Jan 17, 2007 6:41 pm

ah....got it now........

for symmetry you need an axis of symmetry where is it here or is a translational form of symmetry?

tarek

by **ronk** » Wed Jan 17, 2007 7:51 pm

ravel wrote:I cannot see a 90-degree symmetry in this grid (like in Mauricio's 3rd puzzle here).

I'm not familiar with the formal symmetry definitions, so let me explain mostly by illustration.

By "90-degree symmetry" I meant that even when your permuted grid is rotated 90-degrees, "diagonal symmetry" remains allowing use of gurth's symmetry techniques (ST).

No rotation:

Code: Select all: 9 3 2 | 7 8 4 | 6 5 1 9 3 2 | 4 7 8 | 5 1 6 4 6 8 | 1 9 5 | 2 7 3 4 6 8 | 5 1 9 | 7 3 2 5 1 7 | 3 2 6 | 8 4 9 5 1 7 | 6 3 2 | 4 9 8 ---------+----------+---------- ---------+----------+---------- 7 8 4 | 6 5 1 | 9 3 2 3 2 6 | 9 8 4 | 1 7 5 1 9 5 | 2 7 3 | 4 6 8 7 8 4 | 1 6 5 | 3 2 9 3 2 6 | 8 4 9 | 5 1 7 1 9 5 | 3 2 7 | 6 8 4 ---------+----------+---------- ---------+----------+---------- 6 5 1 | 9 3 2 | 7 8 4 2 7 3 | 8 4 6 | 9 5 1 2 7 3 | 4 6 8 | 1 9 5 8 4 9 | 7 5 1 | 2 6 3 8 4 9 | 5 1 7 | 3 2 6 6 5 1 | 2 9 3 | 8 4 7 ravel's grid permuted to diagonal 967 1 2 3 | 8 9 6 | 7 4 5 2 10 10 | 10 18 10 | 10 10 10 8 5 6 | 7 4 1 | 9 2 3 . 10 10 | 10 10 2 | 18 10 10 7 4 9 | 5 2 3 | 8 1 6 . . 18 | 10 10 10 | 10 2 10 ---------+----------+---------- ---------+----------+---------- 2 3 5 | 1 6 8 | 4 9 7 . . . | 2 10 10 | 10 18 10 9 6 8 | 4 5 7 | 2 3 1 . . . | . 10 10 | 10 10 2 4 1 7 | 2 3 9 | 5 6 8 . . . | . . 18 | 10 10 10 ---------+----------+---------- ---------+----------+---------- 3 9 2 | 6 8 5 | 1 7 4 . . . | . . . | 2 10 10 6 8 1 | 9 7 4 | 3 5 2 . . . | . . . | . 10 10 5 7 4 | 3 1 2 | 6 8 9 . . . | . . . | . . 18 diagonal 967 normalized diagonal sums <rMcN>+<rNcM>

90-degree CW rotation:

Code: Select all: 6 3 5 | 2 4 9 | 7 8 1 8 9 7 | 3 1 6 | 4 5 2 1 2 4 | 5 7 8 | 9 6 3 ---------+----------+---------- 7 8 1 | 6 3 5 | 2 4 9 4 5 2 | 8 9 7 | 3 1 6 9 6 3 | 1 2 4 | 5 7 8 ---------+----------+---------- 2 4 9 | 7 8 1 | 6 3 5 3 1 6 | 4 5 2 | 8 9 7 5 7 8 | 9 6 3 | 1 2 4 ravel's grid rotated 90-degrees CW 1 2 3 | 4 9 5 | 6 8 7 2 10 10 | 10 18 10 | 10 10 10 8 5 6 | 2 7 1 | 9 3 4 . 10 10 | 10 10 2 | 18 10 10 7 4 9 | 3 6 8 | 5 1 2 . . 18 | 10 10 10 | 10 2 10 ---------+----------+---------- ---------+----------+---------- 6 8 7 | 1 2 3 | 4 9 5 . . . | 2 10 10 | 10 18 10 9 3 4 | 8 5 6 | 2 7 1 . . . | . 10 10 | 10 10 2 5 1 2 | 7 4 9 | 3 6 8 . . . | . . 18 | 10 10 10 ---------+----------+---------- ---------+----------+---------- 4 9 5 | 6 8 7 | 1 2 3 . . . | . . . | 2 10 10 2 7 1 | 9 3 4 | 8 5 6 . . . | . . . | . 10 10 3 6 8 | 5 1 2 | 7 4 9 . . . | . . . | . . 18 90-degree CW and normalized diagonal sums <rMcN>+<rNcM>

The "normalization" puts 159159159 on the diagonal and 123856749 in box 1 to yield diagonal sums (transpositional sums) of 2, 10 and 18 only.

by **Mauricio** » Thu Jan 18, 2007 9:50 pm

This sudoku is isomorphic to a sudoku with DDS, it is your job to find the transformation, after that the puzzle is easy, singles only (after ST).

Code: Select all: . 7 .|. . .|1 . . 2 . .|8 . .|. . 7 . . 1|. . 9|. 5 . -----+-----+----- 4 . .|. . 7|. . . . . 3|5 . .|. . 8 . 6 .|. 2 .|9 . . -----+-----+----- . 8 .|. 5 .|6 . . . . 9|. . 2|. . 4 . . .|1 . .|. 3 . gsfr ~99927, ER 10.5

ravel wrote:I dont know, if DDS implies box symmetry. Any proof or counter-example?

BTW, this puzzle is a counterexample (I think).

by **ronk** » Fri Jan 19, 2007 12:20 am

Mauricio wrote:This sudoku is isomorphic to a sudoku with DDS, it is your job to find the transformation ...

I have found transformations to two diagonally-symmetric grids ... but not one transformation to one double-diagonal-symmetric.

by **gurth** » Fri Jan 19, 2007 9:32 am

ravel wrote:
gurth wrote:ravel, congratulations on discovering the 3 identical sets of boxes... (I didn't ban computers).
I neither have nor know a program, that discovers symmetries (but i saw the box symmetry in Mauricio's samples).

ravel, what I thought is that you were using a computer to give you the solution grids for my two challenges. Analysing a complete solution grid for symmetry would be a lot easier perhaps than just analysing the clues. Forgive me if I was wrong about this. But how did you reach the solution grid of my 3rd Challenge?

Normally of course I would expect solvers to reach a solution by analysing the clues, rather than by analysing the very solution grid that they are expected to discover using ST!

by **udosuk** » Fri Jan 19, 2007 3:51 pm

Mauricio wrote:This sudoku is isomorphic to a sudoku with DDS, it is your job to find the transformation, after that the puzzle is easy, singles only (after ST).

Code: Select all: .7....1.. 2..8....7 ..1..9.5. 4....7... ..35....8 .6..2.9.. .8..5.6.. ..9..2..4 ...1...3. r456312789, c132456798: 4....7... .3.5...8. ..6.2.9.. .1...9..5 ..7...1.. 2..8...7. ..8.5.6.. .9...2.4. ...1....3 *--------------------------------------------------------------------* | 4 258 1259 | 369 13689 7 | 235 12356 126 | | 179 3 129 | 5 1469 146 | 247 8 12467 | | 1578 578 6 | 34 2 1348 | 9 135 147 | |----------------------+----------------------+----------------------| | 368 1 34 | 23467 3467 9 | 2348 236 5 | | 35689 4568 7 | 2346 346 3456 | 1 2369 24689 | | 2 456 3459 | 8 1346 13456 | 34 7 469 | |----------------------+----------------------+----------------------| | 137 247 8 | 3479 5 34 | 6 129 1279 | | 13567 9 135 | 367 3678 2 | 578 4 178 | | 567 24567 245 | 1 46789 468 | 2578 259 3 | *--------------------------------------------------------------------* r1c9=r5c5=r9c1=6 r4c4+r6c6={34} 452987316 139546782 786321954 813479265 947265138 265813479 328754691 591632847 674198523 974265183 256813497 831479256 425987361 193546728 768321945 382754619 519632874 647198532

by **ronk** » Fri Jan 19, 2007 7:29 pm

Mauricio wrote:This sudoku is isomorphic to a sudoku with DDS, it is your job to find the transformation, after that the puzzle is easy, singles only (after ST).
Code: Select all
. 7 .|. . .|1 . . 2 . .|8 . .|. . 7 . . 1|. . 9|. 5 . -----+-----+----- 4 . .|. . 7|. . . . . 3|5 . .|. . 8 . 6 .|. 2 .|9 . . -----+-----+----- . 8 .|. 5 .|6 . . . . 9|. . 2|. . 4 . . .|1 . .|. 3 . gsfr ~99927, ER 10.5

ravel wrote:I dont know, if DDS implies box symmetry. Any proof or counter-example?

BTW, this puzzle is a counterexample (I think).

udosuk wrote:
Code: Select all
452987316 139546782 786321954 813479265 947265138 265813479 328754691 591632847 674198523

Mauricio and udosuk, great puzzle and display of solving skills. I had 346 on the diagonal, but didn't get the correct shuffle for the anti-diagonal.

And I stand corrected. Mauricio's example is definitely proof that while box symmetry implies DDS, DDS does not imply box symmetry.

Not only that, my proposed normalization ...

Code: Select all: 1 2 3 | . . . | . . . 8 5 6 | . . . | . . . 7 4 9 | . . . | . . . -------+-------+------- . . . | 1 . . | . . . . . . | . 5 . | . . . . . . | . . 9 | . . . -------+-------+------- . . . | . . . | 1 . . . . . | . . . | . 5 . . . . | . . . | . . 9

... doesn't work for Mauricio's DDS either. The digits along both diagonals are in a different order in each box.

Perhaps I should stick with fishing.

by **Mauricio** » Fri Jan 19, 2007 11:03 pm

To generate my previous sudoku, I had to modify my generator so that now takes in account 2 given (arbitrary) symmetries , not just 1.

Then I generated sudokus with DS and 180 rotational symmetry, and all of them have DDS, so I conjeture DS and 180 rotational symmetry => DDS.
If that is true, then it is true that DDS<=>(DS and 180 rotational symmetry)

Mauricio

by **gurth** » Sat Jan 20, 2007 8:17 am

GC57 : with UR type 4

and only one 4-cell forcing chain. (SE says two, but one of those is quite unnecessary).

Code: Select all: #GC57 #SE 7.1 . 3 . . . . . . . 7 . . . 4 . . . 6 . . 2 9 . 3 . 8 . 8 . . . . . . . . . . . . 3 . 5 4 . . 6 . . . 2 9 . . . . 5 6 . . . . . . 4 . . . 8 7 . 1 9 . . . . . . . 2

________________________________________

Mauricio's DDS sudoku of Jan 18 :

This sudoku is the first published DDS sudoku with all clues fully symmetrical about BOTH diagonals. There is absolute certainty that there can be no unique non-DDS solution, so a DDS solution can be assumed, and ST techniques applied with absolute assurance of correctness.

My own sudoku with DDS solution, GC53, did not have this full symmetry of clues: all I claimed was "(All the clues conform to DDS, and every clue has a DDS partner.)(Clues on the diagonals partner themselves.)".

But that is not at present enough to prove the solution has DDS. Not to my understanding, until someone proves it rigorously. I wish to claim AS A CONJECTURE that if every clue has at least ONE DDS partner (ie relative to either one of the two diagonals), then that is enough to ensure that any unique solution has DDS.

I propose that this CONJECTURE be allowed as a valid solution technique, provided it DOES lead to a DDS solution, until such time as my CONJECTURE be disproved by counter-example.

My argument being that it would be wrong to discredit a conjecture if it is not possible to disprove it. Moreover, I feel that DDS symmetry is so tight that less than total DDS symmetry in the clues will be enough to solve any puzzle.

For one thing, adopting this methodology should be a productive spur to someone to prove or disprove this conjecture (something beyond me).

Finally regarding GC53, it does NOT have what I call 90-degree symmetry. In 90-degree symmetry, you can deduce 3 cells from any clue, if you know the symmetrical quadruplings. See GC59 below for an example.

Mauricio, it's nice to have someone produce a DDS puzzle for ME to solve! And what a magnificent puzzle. But don't you think it deserves a number, at least, for ready reference? What a thrill, to think that I solved a whopping ER 10.5 puzzle without touching a computer, using one sheet of paper.

I did the transformations in 3 easy stages, shifting tiers, columns, and finally 2 rows and 2 columns to get the clues into DDS. Then it solves easily. Certainly I saw no sign of any box symmetry here! But the rotational symmetry is there, inevitably, as ronk and ravel have pointed out.
________________________________________________________________________________

GC58 : 5th CHALLENGE

Code: Select all: *-----------* |2..|3..|1..| |.6.|.5.|...| |..9|..4|3..| |---+---+---| |.9.|.8.|4..| |..8|..9|.27| |4..|5..|...| |---+---+---| |...|...|7..| |.3.|.1.|.56| |7..|8..|.31| *-----------*

This puzzle is beyond SS, and SE needs 12 forcing chains, up to SE (7.3). That's quite a slog!

This is a NEW symmetry.

Here the symmetry needs to be revealed by NORMALIZATION, (morphing into symmetry), after which you have to figure out the precise nature of the symmetry. Then it is very easy to solve.

You definitely should not be peeping at the solution on this one.
_____________________________________________________________________________________

TENFOLD DIAGONAL SYMMETRY

To create a grid with tenfold diagonal symmetry, i.e. symmetrical about 5 parallel diagonals and also about 5 parallel diagonals perpendicular to the first 5, proceed as follows:

Allocate the 9 values 1 to 9 to 4 colours as follows:
Allocate three values to colour T.
Allocate 2 values each to colours a, c and e.

Now colour in a grid so that the 4 colours are symmetrical about 10 diagonals. Give each cell a colour: don't insert any digits yet.

Of course, each unit (box, row, column) must contain three cells of colour T and two cells each of colours a, c and e.

If you succeed, you will have perfect tenfold diagonal symmetry for the colours (groups). You may also find that the boxes are also symmetrical.

The internal arrangement of the digits within the colours may now be attended to. Varying degrees of digital symmetry, or rather of consistent digital symmetry, are now possible.

Just note one thing: a diagonal need not necessarily bisect a box into 2 equal halves. It can be OFFSET.

Check GC51.
________________________________________________________________________________________

GC59: 90-degree rotational symmetry.

Code: Select all: #GC59 #SE 7.1 with 4 swordfish & 1 forcing chain 6 . . . . 7 . . 1 . . 1 . 5 . . . . . . . 9 . . . 3 . 7 . . . 2 . 4 . . . 4 . 3 . 6 . 8 . . . 8 . 1 . . . 7 . 6 . . . 5 . . . . . . . 9 . 2 . . 2 . . 7 . . . . 3

____________________________________________________________________________________________

by **ravel** » Sat Jan 20, 2007 7:05 pm

Here is a handmade sample for the new symmetry. No morphing, only singles and ST.

Code: Select all: +-------+-------+-------+ | 1 . . | 7 . . | . 5 6 | | . . . | . . . | . . . | | . 8 9 | . . . | 1 . . | +-------+-------+-------+ | . . 1 | . 3 . | . 2 . | | 3 9 . | . 7 . | 8 . 1 | | . 7 . | 8 . 1 | . . 4 | +-------+-------+-------+ | . 1 . | . . 2 | . . 3 | | 2 . 8 | . . 7 | 9 1 . | | . . 7 | 9 1 . | . 4 . | +-------+-------+-------+

by **Mauricio** » Sun Jan 21, 2007 11:36 pm

ravel wrote:Here is a handmade sample for the new symmetry....

That is a nice symmetry, your example give me the ideas of an algorithm to find ALL possible automorphisms of a sudoku.

Hin for programmers: If you have an algorithm that canonicalizes a sudoku, then with a slight change to that algorithm you can have an algorithm that finds ALL possible automorphisms of a sudoku (unless your algorithm is very sophisticated).
A program that canonicalizes "minimizes" the sudoku according to a given order; to find automorphisms, we just want to have the same sudokus.

To find the zeros of a function is IMHO easier than to minimize a function.

by **Mauricio** » Mon Jan 22, 2007 12:22 am

gurth wrote:But that is not at present enough to prove the solution has DDS. Not to my understanding, until someone proves it rigorously. I wish to claim AS A CONJECTURE that if every clue has at least ONE DDS partner (ie relative to either one of the two diagonals), then that is enough to ensure that any unique solution has DDS.

I propose that this CONJECTURE be allowed as a valid solution technique, provided it DOES lead to a DDS solution, until such time as my CONJECTURE be disproved by counter-example.

IMO, it is wrong to credit a cojeture as true if we do not have a proof.

Counterexamples to gurth, each clue not in the central box has a DDS partner, and the clue in the central box has a DS partner (the same cell)

Code: Select all: . . 8|. . 7|. 1 . . 1 .|8 . .|. . 9 2 . .|. 6 .|3 . . -----+-----+----- . 2 .|5 . .|. . 7 . . 4|. . .|8 . . 3 . .|. . .|. 6 . -----+-----+----- . . 7|. 2 .|. . 6 1 . .|. . 4|. 9 . . 9 .|3 . .|4 . .

you may argue easily that if this sudoku leads to a solution with DDS, then r6c6=5, a quick contradiction.
To counter that, take this example

Code: Select all: 5 . .|. . 6|. . 7 . 9 .|3 . .|8 . . . . 1|. 2 .|. 6 . -----+-----+----- . 7 .|. . .|. . 8 . . 8|. . .|4 . . 4 . .|. . 1|. 3 . -----+-----+----- . 2 .|. 6 .|9 . . . . 4|. . 7|. 1 . 3 . .|2 . .|. . 5

here we may not say that argument.

by **JPF** » Mon Jan 22, 2007 12:36 am

Mauricio, I don't know if it' the right thread, but :

you wrote:...your example give me the ideas of an algorithm to find ALL possible automorphisms of a sudoku.

The grid has to be automorphic.

Could you elaborate on your idea ?

JPF

by **Mauricio** » Mon Jan 22, 2007 12:53 am

JPF wrote:The grid has to be automorphic.
Could you elaborate on your idea ?

Under my POV, every sudoku is trivially automorphic, being the identity tranformation an automorphism (the transformation that does nothing

).

But that transformation is not very useful, we regard a sudoku as automorphic if there exists a non trivial tranformatin that leaves the sudoku invariant.

My algorithm only does all possible tranformations to a given sudoku, and returns those that leave the sudoku invariant. That is done "intelligently", ie, the transformation is done by parts, not as a whole; if at some point of the transformation we see that the sudoku can not be automorphic under that transformation, then I do the next transformation.

The New Sudoku Players' Forum

Gurth's Puzzles

re Use of Computer

various