Gurth's Puzzles

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

Postby 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.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby 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
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Postby 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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby 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).
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby 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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

re Use of Computer

Postby 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!
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby 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
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby 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.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby 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
Mauricio
 
Posts: 1174
Joined: 22 March 2006

various

Postby 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

____________________________________________________________________________________________
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby 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 . |
+-------+-------+-------+
ravel
 
Posts: 998
Joined: 21 February 2006

Postby 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.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby 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.
Last edited by Mauricio on Mon Jan 22, 2007 6:18 pm, edited 1 time in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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:D ).

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.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

PreviousNext

Return to General