## Down Under Upside Down - a Sudoku puzzle

Post puzzles for others to solve here.
eleven wrote:It is really annoying, that both of you did not mention, that you did need my first step in your solution paths.
So we looked for something, which was not there - how could we know, that you have a strange feeling, what is as easy as an xy-wing ? Otherwise it would have been very easy to find the second step.
(btw not to place a single at the beginning is just stupid for me.)

I guess the main point is not whether your logic is as easy as xy-wing, but how you present your move. The way you presented your move was by chains, and I specifically stated that the puzzle doesn't need chains to be solved. If you had used something other than chains to present your logic, then we could have the argument whether it's as easy as xy-wing.

Note my first two steps are as simple as "locked candidates" once you factor out the symmetrical element of the logic. I think roughly speaking there are 3 level of difficulties among techniques:

1. basic techniques:
singles, subsets, locked candidates (aka box-line intersection)

2. intermediate techniques:
simple fish (e.g. x-wing), turbot fish, xy-wing, w-wing, empty rectangle, sue de coq, etc
(and if uniqueness is allowed: UR, BUG, BUG-lite, etc)

forcing chain (including xy-chain), ALS (including ALS-xz), forcing net etc

So my intention was that you should solve the puzzle using the first 2 levels of techniques only.

eleven wrote:As a revenge here is an unfair challenge for you:
Code: Select all
` *-----------------------* | . 9 6 | . . 5 | . 1 . | | . . . | 3 . . | . . . | | 2 . . | . . 6 | 5 . 9 | |-------+-------+-------| | . . 5 | . . . | 6 . . | | 9 4 2 | . . . | 3 . . | | . . 3 | . . . | 1 9 4 | |-------+-------+-------| | . 2 . | . . 4 | . . 1 | | 5 . . | 8 . 2 | 4 . 7 | | . 8 4 | 7 . 1 | . 6 . | *-----------------------*`

Nothing harder than xy-wing needed (no xy-chain).

Nice puzzle! I have a rough idea how to crack it using the least amount of work, but I can't straighten out my logic (yet). Here is a sketch of what I see:

First swap r45, then swap r78, then swap c56, then swap c89:
Code: Select all
`+----------------------------+----------------------------+----------------------------+| 3478     9        6        | 24       5        2478     | 278      238      1        || 1478     157      178      | 3        789      124789   | 278      268      2478     || 2        137      178      | 14       6        1478     | 5        9        3478     |+----------------------------+----------------------------+----------------------------+| 9        4        2        | 156      78       15678    | 3        58       578      || 178      17       5        | 1249     3789     1234789  | 6        28       278      || 678      67       3        | 256      78       25678    | 1        4        9        |+----------------------------+----------------------------+----------------------------+| 5        136      19       | 8        2        369      | 4        7        3        || 367      2        79       | 569      4        3569     | 89       1        358      || 3        8        4        | 7        1        359      | 29       235      6        |+----------------------------+----------------------------+----------------------------+`

Note despite b258 being a mess we have perfect 180 degree rotational symmetry @ b13, b46 & b79 respectively with the digit mapping 1-2, 5-6, 7-8 and 3-3, 4-4, 9-9. If we can somehow prove that this symmetry must be conserved in the solution then this puzzle can be solved in one simple move - r8c37=[78]. (Remember to swap back the rows/columns to produce the solution for the original puzzle.)

(I suppose one might use a uniqueness line of argument as follows: say r8c37=[79] yields a solution, then you can argue that r8c37=[98] must produce another solution using the rotational operations on b13, b46, b79 with digit remapping.)

RW, what duya think?
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:RW, what duya think?

I think you already proved yourself wrong... In a symmetric puzzle, only one digit may be it's own symmetrical pair.

Eleven, when working with puzzles like these with few predefined solving techniques, defining the techniques is an important part of the excercise (and the fun part IMO ). For this it is not ehough to find the elimination, you must also find the essential logic behind the elimination. It's not only about what you're doing, it's about knowing what you're doing. If you had noticed that it was enough to examine the candidates of only two cells to make the elimination, then I bet you would have regarded the elimination as "easier" than XY-wing.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

udosuk wrote:I guess the main point is not whether your logic is as easy as xy-wing, but how you present your move. The way you presented your move was by chains, and I specifically stated that the puzzle doesn't need chains to be solved. If you had used something other than chains to present your logic, then we could have the argument whether it's as easy as xy-wing.

But when i ask for a solution without chains, and some one posts a chain notation for an x-wing, i will write "you found the x-wing".
RW wrote:If you had noticed that it was enough to examine the candidates of only two cells to make the elimination, then I bet you would have regarded the elimination as "easier" than XY-wing.
Not harder than xy-wing does not exclude easier than xy-wing.
eleven

Posts: 1907
Joined: 10 February 2008

RW wrote:I think you already proved yourself wrong... In a symmetric puzzle, only one digit may be it's own symmetrical pair.

Nope, for 180 degree rotational symmetry only one digit may be it's own conjugate. For other symmetries, such as diagonal reflection, it's perfectly valid to have 3 digits conjugating itself (I think Gurth has showed these types of examples before). As a matter of fact I've worked out the requiring permutation operations for eleven's puzzle to make this mapping fully working, which I'm going to show soon.

eleven wrote:But when i ask for a solution without chains, and some one posts a chain notation for an x-wing, i will write "you found the x-wing".

Aha, I see you're always expecting the puzzle setter to keep watching your working and tell you if you're on the right track or have been totally wrong. This would be the desirable working environment if, say, you're in a high school class or working under a nice supervisor on a new project. Unfortunately, in real life this seldom happens. The bottom line is if you had worked out a solution matching my criteria I would have the obligation to proclaim you as the winner. If you're close but not quite there I can just say "you're not there yet, keep up the good effort" etc.

I could have been nicer and pointed out that you were working at the right cells for the critical moves but needed to rephrase your presentation better. However since I haven't said much you shouldn't have made the (wrong) assumption that the critical move is somewhere else. Instead you should have kept looking both ways - either finding a new breakthrough in other cells, or improving your elegancy on your existing moves to remove the "chain" presentation.

(Or, if you have explicitly asked the question "have I been focusing on the correct area/cells", one of RW or I could have given you much more useful information to avoid all that unnecessary side-tracking. )

So, say if I provide a formal solution for your puzzle in the next post, I will only expect you to say if I'm correct or wrong (but you need to give legitimate and objective reasons if you think I'm wrong). I wouldn't expect you to help me out by pointing explicitly where I should focus on to improve my solution.
udosuk

Posts: 2698
Joined: 17 July 2005

Okay, here goes...

eleven posted the following puzzle, which is supposed to be a valid one (i.e. with a unique solution):
Code: Select all
`+---+---+---+|.96|..5|.1.||...|3..|...||2..|..6|5.9|+---+---+---+|..5|...|6..||942|...|3..||..3|...|194|+---+---+---+|.2.|..4|..1||5..|8.2|4.7||.84|7.1|.6.|+---+---+---+`

I decide to perform the following permutational operations on the puzzle:
Code: Select all
`Swap r13Swap r56Swap r89Permute c123 to c312Permute c789 to c897Swap left 3 columns & right 3 columns`

Then I obtain the following puzzle, which is essentially equivalent to the original one:
Code: Select all
`+---+---+---+|.95|..6|.2.||...|3..|...||1..|..5|6.9|+---+---+---+|..6|...|5..||941|...|3..||..3|...|294|+---+---+---+|.1.|..4|..2||6..|7.1|4.8||.74|8.2|.5.|+---+---+---+`

... which, can be transformed back to the original puzzle with the following digit mapping:
Code: Select all
`Permute digits 1,2Permute digits 5,6Permute digits 7,8`

What does this tell me? Let's put it in formal context:

Assume the solution to the original puzzle has the following cell values:
Code: Select all
`Solution Grid A a11 a12 a13 | a14 a15 a16 | a17 a18 a19 a21 a22 a23 | a24 a25 a26 | a27 a28 a29 a31 a32 a33 | a34 a35 a36 | a37 a38 a39-------------+-------------+------------- a41 a42 a43 | a44 a45 a46 | a47 a48 a49 a51 a52 a53 | a54 a55 a56 | a57 a58 a59 a61 a62 a63 | a64 a65 a66 | a67 a68 a69-------------+-------------+------------- a71 a72 a73 | a74 a75 a76 | a77 a78 a79 a81 a82 a83 | a84 a85 a86 | a87 a88 a89 a91 a92 a93 | a94 a95 a96 | a97 a98 a99`

Performing the aforementioned permutational operations plus digit mapping, we obtain the following solution grid:
Code: Select all
`Solution Grid B b38 b39 b37 | b34 b35 b36 | b33 b31 b32 b28 b29 b27 | b24 b25 b26 | b23 b21 b22 b18 b19 b17 | b14 b15 b16 | b13 b11 b12-------------+-------------+------------- b48 b49 b47 | b44 b45 b46 | b43 b41 b42 b68 b69 b67 | b64 b65 b66 | b63 b61 b62 b58 b59 b57 | b54 b55 b56 | b53 b51 b52-------------+-------------+------------- b78 b79 b77 | b74 b75 b76 | b73 b71 b72 b98 b99 b97 | b94 b95 b96 | b93 b91 b92 b88 b89 b87 | b84 b85 b86 | b83 b81 b82`

... with the following "digit-mapping table":
Code: Select all
`a[i,j]  b[i,j]   1       2   2       1   3       3   4       4   5       6   6       5   7       8   8       7   9       9`

If you plug in the given clues from the original puzzle (e.g. a12=9, a13=6 etc) to Solution Grid B (e.g. b12=9, b13=5 etc), you create an identical puzzle to the original one. Because the original puzzle has only one unique solution, we can safely say that Solution Grid A & Solution Grid B must be exactly the same. Hence we can match cell values from both grids and establish some one-to-one relationships. One such relationship is:
Code: Select all
`a73=b77`

But a73 & a77 are both @ r7, can't both be 9
=> r7c37 can't have 9

With this elimination the rest of the puzzle can be solved via naked singles.

To make things academic, we can have the following theorem:

Principle Of Common Key Equivalence Transformation (POCKET)

If a valid sudoku puzzle (with a unique solution), after a certain set of permutational operations, including reflection, rotation, row/columns swapping and digit mapping, is transformed back to an identical image of the original puzzle, then we can establish certain one-to-one relationships on certain cells within the grid, both in context of candidate lists in the pencilmark grid or cell values in the solution grid.

But the question is, how to spot these permutational operations quickly? Well, it's certainly a skill that needs a lot of practice, and an exceptional observation power.

Edited: Name of theorem edited based on RW's advice
Last edited by udosuk on Sat Sep 27, 2008 10:57 pm, edited 1 time in total.
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:
RW wrote:I think you already proved yourself wrong... In a symmetric puzzle, only one digit may be it's own symmetrical pair.

Nope, for 180 degree rotational symmetry only one digit may be it's own conjugate. For other symmetries, such as diagonal reflection, it's perfectly valid to have 3 digits conjugating itself

Sorry, left out a word, it was my intention to say "rotational symmetry", because that was what you said in your post...

Congratulations on your nice solution! I like the POCKET! I'm a bit cautious about the use of the word "Emerald", which has been defined by Gurth as "a puzzle having a symmetrical solution", though I guess this also is a kind of symmetry... Still, I think "Principle Of Common Key Equivalence Transformation" would be more descriptive for the technique...

Question 1: Does the transformation give any other immediate eliminations than r247c123789<>347?

Question 2: What is the most symmetrical form of the solution grid to this puzzle?

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote:Sorry, left out a word, it was my intention to say "rotational symmetry", because that was what you said in your post...

At that time I hadn't yet worked out the full transformation involving b258, so I could only see the rotational symmetry in b13 etc. Turns out this is a totally different sort of "symmetry"!

RW wrote:Congratulations on your nice solution! I like the POCKET! I'm a bit cautious about the use of the word "Emerald", which has been defined by Gurth as "a puzzle having a symmetrical solution", though I guess this also is a kind of symmetry... Still, I think "Principle Of Common Key Equivalence Transformation" would be more descriptive for the technique...

Your full name is much better than mine! I was just trying to make an honourable mention to Gurth's invention but I'm sure he wouldn't mind if we drop the word. I was actually thinking of something like "Principle of Symmetrical Transformation (POST)" but the word "symmetrical" might cause confusion as the symmetry is not always "visible".

RW wrote:Question 1: Does the transformation give any other immediate eliminations than r247c123789<>347?

I assume you mean "<>349"? Yes, because the "axis of symmetry" for this puzzles is r247c456, an immediate first move (corresponding to "Gurth's Symmetrical Placement") is all 9 cells of r247c456 must be from {349}.

I have a conjecture that in all kinds of symmetry the "axis" must only be of 1 cell (e.g. rotational) or 9 cells spanning 3 blocks (e.g. diagonal reflection, or this puzzle). For 1-cell-axis only 1 digit maps to itself while for 9-cell-axis we have 3 self-mapping digits.

RW wrote:Question 2: What is the most symmetrical form of the solution grid to this puzzle?

If you swap r45, swap r78 and then swap c89, you'll have the "axis of symmetry" in r258c456. Plus if you view each band (i.e. 3 rows) separately you'll see a "pseudo 180 degree rotational symmetry" around the middle mini-row (e.g. r2c456), except that in the central block the swapping is only vertical (e.g. r1c4-r3c4, r1c5-r3c5, r1c6-r3c6). I think this is as good as it gets.
Last edited by udosuk on Sat Sep 27, 2008 11:02 pm, edited 2 times in total.
udosuk

Posts: 2698
Joined: 17 July 2005

Congratulations, Udosuk!

I modified the first puzzle here
http://forum.enjoysudoku.com/viewtopic.php?p=40716#p40716
in the thread (you pointed to) in order to annoy you, but it seems you had fun with it
It has this strange "sticks symmetry".

udosuk wrote:But the question is, how to spot these permutational operations quickly? Well, it's certainly a skill that needs a lot of practice, and an exceptional observation power.

Probably this depends much on the given pattern. In this case it is not too hard. There are only 3 useful symmetries, rotational, diagonal and this sticks symmetry.

Transformations cannot change the number of givens in a box.
For rotational symmetry you need a box with symmetric givens in the center. This only could be boxes 5 and 9 here. But boxes 1/9 and 1/3 have a different number of givens.
For diagonal symmetry you need 3 boxes with diagonal symmetric givens in a diagonal, but possible candidates are only 2, 4 and 9.

So what is left is this sticks symmetry, where (horizontally) 2 bands are swapped and 2 colums in all stacks. This also is not possible, but vertically it is, stacks 1 and 3 have the same number of givens.
Now its clear, that rows 1/3, 5/6 and 8/9 must be swapped (96 in r1c23 can only map to 59 in r3c79 and so on) to reach this symmetry.
The rest is to check, if the digits map correctly. In band 1 we have 2->1, i.e c1 to c8, in band 2 5->6, i.e c3 to c7, remains c2 to c9.
In stack 2 rows 2, 4 and 7 map to themselves.
When all givens are checked - in all cases a number maps to the same,
namely 12, 33, 44, 56, 78, 99. we can make a lot of eliminations and placements in this grid:
Code: Select all
`+----------------------+----------------------+----------------------+| 47     9      6      | 24     2478   5      | 278    1      3      || 147    5      178    | 3      12478  9      | 278    248    6      || 2      3      178    | 14     1478   6      | 5      48     9      |+----------------------+----------------------+----------------------+| 18     17     5      | 49     49     3      | 6      27     28     || 9      4      2      | 16     16     78     | 3      57     58     || 68     67     3      | 25     25     78     | 1      9      4      |+----------------------+----------------------+----------------------+| 67     2      79     | 569    3      4      | 89     58     1      || 5      16     19     | 8      69     2      | 4      3      7      || 3      8      4      | 7      59     1      | 29     6      25     |+----------------------+----------------------+----------------------+`

r1c4=2 (maps to r3c4), r2c5=4 (maps to itself) and so on.
eleven

Posts: 1907
Joined: 10 February 2008

udosuk wrote:
RW wrote:Question 1: Does the transformation give any other immediate eliminations than r247c123789<>347?

I assume you mean "<>349"? Yes, because the "axis of symmetry" for this puzzles is r247c456, an immediate first move (corresponding to "Gurth's Symmetrical Placement") is all 9 cells of r247c456 must be from {349}.

Well, I regard that as the same elimination... Sort of like the hidden subset equivalent to a naked subset elimination. I was looking for even more immediate eliminations, but I guess there aren't any more of those.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

eleven wrote:Congratulations, Udosuk!

I modified the first puzzle here
http://forum.enjoysudoku.com/viewtopic.php?p=40716#p40716
in the thread (you pointed to) in order to annoy you, but it seems you had fun with it
It has this strange "sticks symmetry".

Thanks! I must be suffering from severe memory loss! It's surprising to me that I even replied regarding that topic many months ago. Guess it didn't leave a lasting impression on my brain. But truly thanks for giving me the opportunity to reinvent something interesting. The process is really satisfying!

So a more elegant way to present this "sticks symmetry" is: swap r45, swap r78, permute c123 to c312. Then the axis stays the same (r258c456) while in each band we have rotational symmetry with each minirow considered as a "unit".

Two more after-thoughts:

1. There should be 4 different symmetries with a fixed axis: 180 degree rotation, 90 degree rotation, diagonal reflection and this sticks symmetry.

2. There are also other symmetries without a fixed axis, such as "whole band permutation" or "whole block permutation". There might be one-to-one relationships deductable from these properties? No time to investigate more for now though.
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:1. There should be 4 different symmetries with a fixed axis: 180 degree rotation, 90 degree rotation, diagonal reflection and this sticks symmetry.
Yes, but of course 90 degree rotation implies 180 degree rotation. And trivially puzzles with double diagonal symmetry require symmetry for each diagonal (but can have different number mappings).
2. There are also other symmetries without a fixed axis, such as "whole band permutation" or "whole block permutation". There might be one-to-one relationships deductable from these properties? No time to investigate more for now though.
I think, this also is answered in this thead: http://forum.enjoysudoku.com/viewtopic.php?p=40744#p40744. At least no one came up with an idea, how to use it.
eleven

Posts: 1907
Joined: 10 February 2008

After a second thought i cant believe, that other symmetries would not be useful for a solution. E.g. in this Puzzle from this post
http://forum.enjoysudoku.com/viewtopic.php?p=40236#p40236
Code: Select all
`Version 11 . .|. . 4|. 8 .. 9 .|1 . .|. . 5. . 6|. 7 .|1 . .-----+-----+-----. 3 .|. . 2|4 . .5 . .|. 3 .|. . 2. . 2|6 . .|. 3 .-----+-----+-----. 8 .|3 . .|. . 1. . 1|. 9 .|3 . .3 . .|. . 1|. 7 . ER=??(Not tested)Hint: Observe boxes 1-2-3,4-5-6,7-8-9 and digits 1-1,2-2,3-3,4-5-6,7-8-9. *--------------------------------------------------------------------* | 1      257    357    | 259    256    4      | 2679   8      3679   | | 2478   9      3478   | 1      268    368    | 267    246    5      | | 248    245    6      | 2589   7      3589   | 1      249    349    | |----------------------+----------------------+----------------------| | 6789   3      789    | 5789   158    2      | 4      1569   6789   | | 5      1467   4789   | 4789   3      789    | 6789   169    2      | | 4789   147    2      | 6      1458   5789   | 5789   3      789    | |----------------------+----------------------+----------------------| | 24679  8      4579   | 3      2456   567    | 2569   24569  1      | | 2467   24567  1      | 24578  9      5678   | 3      2456   468    | | 3      2456   459    | 2458   24568  1      | 25689  7      4689   | *--------------------------------------------------------------------*`

we only know from the symmetry, that a 4 in r2c13 implies a 5 in r3c46 and a 6 in r1c79, thus a 2 in r2c8 and so on.
I dont have the time now (and probably the next days) to look for eliminations from that, but the puzzle must be easier to solve with this additional informations.
eleven

Posts: 1907
Joined: 10 February 2008

re poket:

check out Stromduko in variations...

http://forum.enjoysudoku.com/viewtopic.php?t=6287

you might like it as well.. plays on the same thing.

and have been therizing on another symetry in this thread using rotation idividual boxes. to other specfic boxes yielding the same results in this thread...

http://forum.enjoysudoku.com/viewtopic.php?t=6274
Some do, some teach, the rest look it up.

StrmCkr

Posts: 889
Joined: 05 September 2006

Thanks StrmCkr.

The puzzle from ttt you cited actually demonstrates the "whole block permutation" I mentioned above, and Glyn's solution in the Stormdoku thread shows perfectly on how to use the symmetry to solve it easily, avoiding all the forcing chains.

As for your other concept, I guess it's all about generating new puzzles from existing ones, which are essentially different to the original puzzles. They might be useful theories for Pattern Games players but not much useful in the context of Sudoku solving. So I think I'll pass on studying your long passages. But thanks for bringing it up.
udosuk

Posts: 2698
Joined: 17 July 2005

Lets take this one to demonstrate, how a box symmetry can be used to solve an otherwise extremely hard puzzle:
Code: Select all
`Version 21 . .|. . 8|. . .. . .|2 . .|. . 9. . 7|. . .|3 . .-----+-----+-----6 . .|. . 7|. 3 .. 1 .|4 . .|. . 8. . 9|. 2 .|5 . .-----+-----+-----. 8 .|. . 2|4 . .5 . .|. 9 .|. . 3. . 1|6 . .|. 7 . ER=10.4Hint:Observe boxes 1-2-3,4-5-6,7-8-9 and digits 1-2-3,4-5-6,7-8-9.`

It has a threefold symmetry, each minirow maps to the (cyclically) next one in the neighbour box. E.g if r7c3=3, you have r8c6=1 and r9c9=2.

Code: Select all
`*--------------------------------------------------------------------* | 1     234569  23456  | 3579  34567   8      | 267   2456    24567  | | 348   3456    34568  | 2     134567  13456  | 1678  14568   9      | | 2489  24569   7      | 159   1456    14569  | 3     124568  12456  | |----------------------+----------------------+----------------------| | 6     245     2458   | 1589  158     7      | 129   3       124    | | 237   1       235    | 4     356     3569   | 2679  269     8      | | 3478  347     9      | 138   2       136    | 5     146     1467   | |----------------------+----------------------+----------------------| | 379   8       36     | 1357  1357    2      | 4     1569    156    | | 5     2467    246    | 178   9       14     | 1268  1268    3      | | 2349  2349    1      | 6     3458    345    | 289   7       25     | *--------------------------------------------------------------------*`
Only a small forcing net is needed:
r7c3=3 -> (symm) r8c6=1 -> r7c45=57 -> r8c4=8 -> (symm) r7c1=7 - contradiction (2 7's in row 7)

This gives r7c3=6, r8c6=4, r9c9=5 and the rest is easy.
eleven

Posts: 1907
Joined: 10 February 2008

PreviousNext