Down Under Upside Down - a Sudoku puzzle

Post puzzles for others to solve here.

Postby champagne » Tue Dec 23, 2008 2:15 am

udosuk wrote:If your solver can't solve this one easily, then you should seriously consider teaching it some tricks on 90 symmetry.


Hi,

This question was still pending, waiting for implementation of 90° symmetry.
Here is the answer

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

r2c5=2 r5c2=3 r5c8=6 r8c5=5
r5c5=4 r1c4=4 r4c9=4 r6c1=4 r9c6=4
r1c1=5 r1c9=3 r2c6=6 r3c6=3 r4c2=2
r4c3=5 r6c7=2 r6c8=5 r7c4=6 r8c4=3
r9c1=6 r9c9=2 r1c2=6 r2c9=5 r8c1=2
r9c8=3

And the tagged (partially) map of candidates at this point.
The most important was for sure r5c5=4.
Nevertheless, the solver uses symmetry to produce these 2 AICs

Code: Select all
5     6     7f89h |4    789  1    |7k89  2     3     
3     178d9 1789  |7A8a 2    6    |4     1789d 5     
189k  4     2     |5    7e89 3    |6     1789  1f7h9
----------------------------------------------------
7     2     5     |1a8A 6    8a9A |3     1A9a  4     
189   3     189e  |2    4    5    |1e79  6     179   
4     1a9A  6     |1A7a 3    7A9a |2     5     8     
----------------------------------------------------
18h9f 1789  3     |6    178e 2    |5     4     1k79 
2     1d789 4     |3    5    7a8A |1789  17d89 6     
6     5     178k  |9    178  4    |1h78f 3     2     


[]9r1c3.h - 7r1c3.f = 7r2c23.F - 7r2c4.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r9c7.h

[]1r7c9.k - 1r89c7.E = 1r5c7.e - 1r5c13.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r7c9.k
candidates tagged 'h' or 'k' are eliminated

and one XYWing eg: r3c9 19 r1c7 89 r3c1 18
gives singles to the end


champagne

PS: what is missing in my sample file is an example of double diagonal symmetry. Can anybody fill the gap??
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Tue Dec 23, 2008 3:52 am

champagne wrote:This question was still pending, waiting for implementation of 90° symmetry.
Here is the answer
[...]
Nevertheless, the solver uses symmetry to produce these 2 AICs

Code: Select all
5     6     7f89h |4    789  1    |7k89  2     3     
3     178d9 1789  |7A8a 2    6    |4     1789d 5     
189k  4     2     |5    7e89 3    |6     1789  1f7h9
----------------------------------------------------
7     2     5     |1a8A 6    8a9A |3     1A9a  4     
189   3     189e  |2    4    5    |1e79  6     179   
4     1a9A  6     |1A7a 3    7A9a |2     5     8     
----------------------------------------------------
18h9f 1789  3     |6    178e 2    |5     4     1k79 
2     1d789 4     |3    5    7a8A |1789  17d89 6     
6     5     178k  |9    178  4    |1h78f 3     2     


[]9r1c3.h - 7r1c3.f = 7r2c23.F - 7r2c4.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r9c7.h

[]1r7c9.k - 1r89c7.E = 1r5c7.e - 1r5c13.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r7c9.k[/b]

In the first "AIC", the use of symmetry appears to be ...

{1r9c7.h; 9r1c3.h} - 7r1c3.f = 7r2c23.F - 7r2c4.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r9c7.h

... but that's 180-degree symmetry. Where's the reliance on 90-degree symmetry:?:

In the second AIC, I see no reliance on symmetry whatsoever.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Tue Dec 23, 2008 4:06 am

champagne wrote:PS: what is missing in my sample file is an example of double diagonal symmetry. Can anybody fill the gap??

This puzzle has double diagonal symmetry, but maybe too easy for your solver:

Code: Select all
1..3....8
....4..2.
..9..6...
6..1.27..
.7.....3.
..38.9..4
...4..1..
.8..6....
2....7..9

As for your latest chains-based solution, sorry I don't think it qualifies as "solving this one easily", especially compared to my simple 2-step solution on p.9.:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Tue Dec 23, 2008 4:17 am

ronk wrote:In the first "AIC", the use of symmetry appears to be ...

{1r9c7.h; 9r1c3.h} - 7r1c3.f = 7r2c23.F - 7r2c4.A = 1r6c2.a - 1r8c2.d = 1r8c78.D - 1r9c7.h

... but that's 180-degree symmetry. Where's the reliance on 90-degree symmetry:?:

In the second AIC, I see no reliance on symmetry whatsoever.


You are right ronk, this is due to the fact that the need to use tagging came very late.
At that point, the central layer A,a can be made without symmetry.

I answered here to udosuk question, but I'll check in other examples I have in my sample file to see if I have somethng more difficult where 90° rotation brings really something specific.

If you have such a puzzle, let me know.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Tue Dec 23, 2008 4:18 am

JPF in the Patterns Game Thread wrote:
Code: Select all
 . . . | . . 1 | . 2 .
 3 . . | . . . | 4 . .
 . 2 5 | 6 . . | 7 . .
-------+-------+-------
 7 . . | . 4 . | 8 . .
 . . . | 1 . 5 | . . .
 . . 9 | . 7 . | . . 4
-------+-------+-------
 . . 4 | . . 2 | 1 6 .
 . . 7 | . . . | . . 3
 . 6 . | 5 . . | . . .       ED=9.4/9.4/9.3

Another very nice symmetrical puzzle that's dead easy to solve using 180 symmetry, diabolical without.

Note it's almost 90 symmetrical as well, but not quite.



gsf in the Patterns Game Thread wrote:
Code: Select all
. . . . . 3 . 2 .
3 . . . . . 4 . .
. 5 1 7 . . 8 . .
7 . . . 8 . 3 . .
. . . 6 . 2 . . .
. . 4 . 9 . . . 5
. . 8 . . 5 9 1 .
. . 3 . . . . . 4
. 6 . 2 . . . . .  ED=4.2/4.2/4.2

I can obtain a 180 symmetrical puzzle using 3 clue-changes:
Code: Select all
r3c2=9 instead of 5
r4c5=1 instead of 8
r9c4=4 instead of 2

.....3.2.
3.....4..
.917..8..
7...1.3..
...6.2...
..4.9...5
..8..591.
..3.....4
.6.4.....

Placing r5c5=8 lead you to a unique solution. So is this a valid puzzle or not?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Tue Dec 23, 2008 5:37 am

udosuk wrote:Placing r5c5=8 lead you to a unique solution. So is this a valid puzzle or not?


without r5c5=8 this puzzle has 5 solutions
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Tue Dec 23, 2008 5:55 am

Exactly!:) Just an example to show that you need to make sure puzzles have unique solutions before applying symmetrical tricks on them.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Tue Dec 23, 2008 5:56 am

Hi ronk,

first and very basic example of 90° symmetry use

Code: Select all
.7..4..8.9....1..6..86..7...2..1.9..1..2.4..3..7.3..4...9..86..8..3....7.6..2..9.




after several steps including XYZ Wngs, you should reach that position:

Code: Select all
6   7     123   |5  4 23 |123   8     9     
9   3B4b  2b345 |7  8 1  |345   2B3b  6     
234 145   8     |6  9 23 |7     1b235 124
----------------------------------------
34  2     34    |8  1 7  |9     6     5     
1   9     6     |2  5 4  |8     7     3     
5   8     7     |9  3 6  |12    4     12   
------------------------------------------
234 13b45 9     |14 7 8  |6     235   124
8   1b4B  125   |3  6 9  |124b5 1B2b  7     
7   6     1l34  |14 2 5  |134   9     8   


So close to the end, you have other possibilities, but using 90° symmetry, the solver expand the layer B,B in such a way that you can eliminate directly

3r2c37 2r37c8 1r8c37 4r37c2

Then the refreshed tagging for layer A,a gives


Code: Select all
6    7    1a23 |5  4 23 |1A23A 8    9     
9    34   245A |7  8 1  |4A5a  23   6     
2A34 1A5a 8    |6  9 23 |7     135A 124a
--------------------------------------
34   2    34   |8  1 7  |9     6    5     
1    9    6    |2  5 4  |8     7    3     
5    8    7    |9  3 6  |12    4    12   
---------------------------------------
2a34 135A 9    |14 7 8  |6     3A5a 12A4A
8    14   2A5a |3  6 9  |245A  12   7     
7    6    1A3A4|14 2 5  |13a4  9    8     


'A' is dead

next to come is tougher

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Tue Dec 23, 2008 6:40 am

Hi ronk,

Last example for the time being

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


We can first check that the given are not showing the symmetry.

1 r2c9=5 r5c5=5 r5c6=9 r6c4=2 r8c1=5 r4c4=1 r4c6=4

Now we have it

Code: Select all
3469   5      3469   |46q8c9 249 1      |2689   7      2389   
8      2A67   4679   |469    3   267    |1a2B69 1A69   5     
3679   2a3B67 1      |5      279 26I78C |4      3689   2389   
-------------------------------------------------------------
2      378    37I89C |1      6   4      |5      389    37c89q
136    4      368    |7      5   9      |168    2      138   
167q9c 167    5      |2      8   3      |167C9I 169    4     
-------------------------------------------------------------
1467   1678   2      |46C8I9 479 5      |3      1B4a89 1789   
5      3A78   3a4B78 |489    1   278    |2789   4A89   6     
1467   9      4678   |3      247 26c78q |1278   5      1278   


[]6r1c4.q - 6r7c4.C = 8r1c4.c - 6r1c4.q <=180° sym

[]1r7c8.B - 1r2c8.A = 1r2c7.a - 2r2c7.B <= 90° symmetry

[]6r3c6.I - 8r3c6.C = 6r9c6.c - 6r3c6.I <= 180° symmetry


all 'q' 'B' 'I' tagged candidates are eliminated.

after cleaning, singles to the end.

The second AIC is a direct use of 90° symmetry. One can notice that when the target is in boxes 2;8 , the 180° symmetry is used. With boxes in the corners, we need the 0° symmetry.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby Mauricio » Tue Dec 23, 2008 1:59 pm

udosuk wrote:Exactly!:) Just an example to show that you need to make sure puzzles have unique solutions before applying symmetrical tricks on them.:idea:

I suppose udosuk says that because of

champagne wrote:...Meantime, I red a very nice probe excluding "Unicity use".

Can you point us where you read that proof, champagne? (Assuming that the nice proof is about Gurth's SP).
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby champagne » Tue Dec 23, 2008 7:39 pm

Mauricio wrote:
udosuk wrote:Exactly!:) Just an example to show that you need to make sure puzzles have unique solutions before applying symmetrical tricks on them.:idea:

I suppose udosuk says that because of

champagne wrote:...Meantime, I red a very nice probe excluding "Unicity use".

Can you point us where you read that proof, champagne? (Assuming that the nice proof is about Gurth's SP).


I'll do it but to answer your point, it just says the solution has the same symmetry as the given. It does not state the solution is unique.

This issue of unicity is not a concern for me I ckeck all puzzles before starting the search of the solution.:D

champagne


EDIT: source gurth here for a very simple probe of symmetry in the results

http://forum.enjoysudoku.com/viewtopic.php?p=32842#p32842

not so long, so I copy it

ravel, I see that aeb's argument did not convince you, and you expressed your doubts with an intelligent question. Let's see if I can help you to understand.

Please do the following thought experiment. Imagine a man solving a puzzle with symmetrical givens. When he solves his first cell C, he uses some set of the givens, call it S, and a technique, call it T. Now instead of doing that, he could just as well have used the set of givens symmetrically opposed to S, and the same technique T, to solve the cell symmetrically opposed to C.

And in fact, he could in this way have solved both cells, one after the other,
arriving at a perfectly symmetrical partial solution.

And moreover, as he proceeds further with his solving process, he can in the same way preserve the symmetry of his solution at all stages of its development. Right to the end. So he can only arrive at a symmetrical solution, and as that solution is unique, there can be no asymmetrical solution.

Does that help you?

Please note also: I did not define as axiom "what intuitively seems to be right." That is only YOUR idea. I said "that which is obvious without proof." Something very different, and a perfectly true definition of "axiom".
Some people say that an axiom can't be proved, but what they mean (or should mean) is that any proof of an axiom is at least as complicated and difficult to understand as the axiom itself, so therefore it is superfluous as a proof. Yet minds work in different ways, and what might be obvious to one may not be to another. There is in fact no rigorous definition possible of the (meaning of the) term "proof" itself. That which is universally accepted? No. A proof of the famous 4-Colour Theorem was "universally accepted" for 11 years, until somebody pointed out that it was false!
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Tue Dec 23, 2008 9:31 pm

Mauricio wrote:Can you point us where you read that proof, champagne? (Assuming that the nice proof is about Gurth's SP).


I would just stress on the fact that I see no contradiction between udosuk example and Gurth proof.

If there are several solutions in a puzzle, you will not find a logic rule to assign a cell in the area where values can be exchanged.

But it remains true that, as for unicity, applying symmetry without checking uniqueness is equivalent to making an assumption (here that the solution is symmetric), not granted if the solution is not unique.

champagne
Last edited by champagne on Tue Dec 23, 2008 10:39 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Wed Dec 24, 2008 12:38 am

champagne wrote:
Code: Select all
6   7     123   |5  4 23 |123   8     9     
9   3B4b  2b345 |7  8 1  |345   2B3b  6     
234 145   8     |6  9 23 |7     1b235 124
----------------------------------------
34  2     34    |8  1 7  |9     6     5     
1   9     6     |2  5 4  |8     7     3     
5   8     7     |9  3 6  |12    4     12   
------------------------------------------
234 13b45 9     |14 7 8  |6     235   124
8   1b4B  125   |3  6 9  |124b5 1B2b  7     
7   6     1l34  |14 2 5  |134   9     8   


So close to the end, you have other possibilities, but using 90° symmetry, the solver expand the layer B,B in such a way that you can eliminate directly

3r2c37 2r37c8 1r8c37 4r37c2

I see an xy-ring ...

r2c2 -3- r2c8 -2- r8c8 -1- r8c2 -4- r2c2 - continuous loop

What exactly is your "90-degree symmetry method" for those eliminations:?:

champagne wrote:But it remains true that, as for unicity, applying symmetry without checking unicity is equivalent to making an assumption (here that the solution is symmetric), not granted if the solution is not unique.

Huh? Unicity, a term no one else on this forum uses, means unique, does it not?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Wed Dec 24, 2008 12:51 am

ronk wrote:What exactly is your "90-degree symmetry method" for those eliminations:?:

Here I'll answer for champagne:

If r2c37 were to have 3, then r37c8 would have 2 by 90 symmetry, causing an empty cell @ r2c8.
Therefore r2c37 can't have 3 (and you can copy this elimination 3 times using 90 symmetry).

But "using 180 symmetry, r1c37 can't be {13}" is enough to solve it...:idea:

ronk wrote:Huh? Unicity, a term no one else on this forum uses, means unique, does it not?

I suppose it's a synonym of uniqueness. However:

http://en.wikipedia.org/wiki/Unicity

http://en.wikipedia.org/wiki/Unicity_distance

Interesting...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Wed Dec 24, 2008 2:20 am

udosuk wrote:If r2c37 were to have 3, then r37c8 would have 2 by 90 symmetry, causing an empty cell @ r2c8.
Therefore r2c37 can't have 3 (and you can copy this elimination 3 times using 90 symmetry).

Thanks udosuk, I obvously missed the chapter explaining that 90-degree symmetry uses two cyclic permutations of four values each ... (1234)(6789) for this example.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Puzzles