Maximum number of clues for a given SE rating

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

Postby daj95376 » Sun Aug 03, 2008 2:18 pm

Thanks Pat for the detailed output from SE. I now know that what it calls Forcing Chains are actually Forcing Nets.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby susume » Mon Aug 04, 2008 2:50 pm

I was playing around with the 11.2 puzzle, not because I think I can solve it, but because it looks so cool - complete 4-arm symmetry of all the clues, and when I start drawing the links in I get symmetrical spaghetti:D ! The solution will have to have the same symmetry. Could this constraint be used to crack the puzzle manually?

The solver started by eliminating 3 from r1c7, but because of the symmetry of the clues it could just as well have started with 2<>r7c9, 1<>r9c3, or 4<>r3c1. In fact all of these eliminations can be made simultaneously using the same logic the solver gave for first step, just rotated 90 degrees around the grid. Every valid elimination, and every valid placement, will have this 4-fold property - it gives us sets of 4 propositions, each about a different digit and cell, that must either all be true or all be false. Specifically, any proposition about digit 1,2,3 or 4 must be true for 1,2,3 AND 4 (in their 90 degree shifted positions), or false for all of them. Any proposition about 6,7,8 or 9 must be true for 6,7,8 AND 9 (in their shifted positions), or false for all of them.

The b/b plot of this puzzle is very sparse, to say the least - no bival cells at all, and of the bilocs, no two digits have strong links ending in the same cell. I am guessing that the constraints from the symmetry will cause more interactions between cells, and interactions between digits, possibly offering some useful manually-discoverable chains. Anyone care to try it?

Is there agreed-on notation for sets of propositions which must be all true or all false together? Do they have a name? Are there sudoku theorems known about them?

I hope I'm not out in left field here--if I am, please laugh nicely:)
susume
susume
 
Posts: 19
Joined: 03 August 2008

Postby RW » Mon Aug 04, 2008 8:08 pm

susume wrote:I was playing around with the 11.2 puzzle, not because I think I can solve it, but because it looks so cool - complete 4-arm symmetry of all the clues, and when I start drawing the links in I get symmetrical spaghetti:D ! The solution will have to have the same symmetry. Could this constraint be used to crack the puzzle manually?

Yes, you can use the symmetry as a constraint, see here. Can't remember if anyone has already provided a nice manual solution using this technique. But it should prove a lot easier than ER 11.2...

For reference, the puzzle was first posted by Mauricio here.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Glyn » Mon Aug 04, 2008 10:23 pm

Susume/RW Although Sudocue can't solve this without Brute Force, its very first move is r1c3=8 reducing the puzzle to ER 9.0. The associated symmetry move r9c7=6 reduces the ER to 3.4. So there may be mileage in this technique when it can be identified as a property of the grid. I haven't tested it as a means of accelerating SE's solving path yet. SE should find the symmetry move automatically as it always determines all moves of a given range of ratings in the same pass.

At the very least you do get roughly double the info from any chains that are determined, and on a puzzle of this level of difficulty that's a bonus. Applying Sod's Law they probably don't interact favourably to do more than that, but it might be worth trying, and that is probably best done manually.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby RW » Tue Aug 05, 2008 4:45 am

Glyn wrote:So there may be mileage in this technique when it can be identified as a property of the grid.

There definitely is, it is the only known technique that has managed to give a simple, humanly readable manual solution to a ER >10 puzzle (10.5 if I recall correctly).

Glyn wrote:I haven't tested it as a means of accelerating SE's solving path yet. SE should find the symmetry move automatically as it always determines all moves of a given range of ratings in the same pass.

To test it succesfully on SE, I think you would need to reprogram SE's chain algorithms to take the symmetry into account...

Glyn wrote:At the very least you do get roughly double the info from any chains that are determined, and on a puzzle of this level of difficulty that's a bonus.

The nice thing with this technique is that you get double info within the chain. SE's first chain starts with (1) If R1C7 contains the value 3, then R1C7 cannot contain the value 4 (the cell can contain only one value), when it could just as well start with (1) If R1C7 contains the value 3, then R9C3 must contain the value 1 (symmetry). Making that symmetrical move a part of the chain, the length reduces significantly (contradiction can be reached using SSTS).

RW
Last edited by RW on Tue Aug 05, 2008 7:35 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

re: arguing from symmetry

Postby Pat » Tue Aug 05, 2008 9:25 am

RW wrote:
The nice thing with this technique is that you get double info within the chain.


SE's first chain starts with
(1) If R1C7 contains the value 3, then R1C7 cannot contain the value 4 (the cell can contain only one value)

when it could just as well start with
(1) If R1C7 contains the value 3, then R7C9 must contain the value 1 (symmetry)


Making that symmetrical move a part of the chain,
the length reduces significantly
(contradiction can be reached using SSTS).



i suppose you meant 3
    the question is,
    can we define this symmetry ?
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: re: arguing from symmetry

Postby RW » Tue Aug 05, 2008 10:35 am

Pat wrote:
RW wrote:i suppose you meant 3

No, I meant 1. In this puzzle all given clues are grouped in symmetrically opposite pairs. The pairs are 1-3, 2-4, 6-8, 7-9 and 5-5. Wherever there is a given digit 1, the symmetrically opposite cell has a 3, wherever there is a given digit 2, the symmetrically opposite cell has a 4 etc. Because all of the givens are paired like this, the remaining digits must also have the same symmetrical pairs (if the puzzle has an unique solution).

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Pat » Tue Aug 05, 2008 10:59 am

RW wrote:No, I meant 1.

In this puzzle all given clues are grouped in symmetrically opposite pairs. The pairs are 1-3, 2-4, 6-8, 7-9 and 5-5. Wherever there is a given digit 1, the symmetrically opposite cell has a 3, wherever there is a given digit 2, the symmetrically opposite cell has a 4 etc.

Because all of the givens are paired like this, the remaining digits must also have the same symmetrical pairs (if the puzzle has an unique solution).


sorry!
and thanks for the explanation.
    however, i'm still missing something here --
    from r1c7, the symmetrically opposite cell would be r9c3 (not r7c9)
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby tarek » Tue Aug 05, 2008 11:01 am

I've been following this discussion with interest.

It seems that these techniques stem from the fact that the SOLUTION GRID displays symmetrical properties.

I'm not sure how this information can be used to advance the solution without prior knowledge of this property.

As you know a valid solution grid for a disjoint group sudoku or a windoku for example can be used to generate valid vanilla puzzles.

Prior knowledge that these grids have these properties would then help us advancing the puzzle becaus ewe can introduce these new constraints to our puzzle.

These symmetrical puzzles shouldn't be vanilla sudokus they should be sudoku variants.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

re: arguing from symmetry

Postby Pat » Tue Aug 05, 2008 11:05 am

tarek wrote:
It seems that these techniques stem from the fact that the SOLUTION GRID displays symmetrical properties.

I'm not sure how this information can be used to advance the solution without prior knowledge of this property.

These symmetrical puzzles shouldn't be vanilla sudokus they should be sudoku variants.



but this is plain SuDoku

if i understand RW's explanation,
the special symmetry seen in the givens
guarantees same symmetry in the answer
    (rigorous proof needed)
and this allows us to make these extra deductions---
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: re: arguing from symmetry

Postby udosuk » Tue Aug 05, 2008 11:13 am

Pat wrote:but this is plain SuDoku

if i understand RW's explanation,
the special symmetry seen in the givens
guarantees same symmetry in the answer
    (rigorous proof needed)
and this allows us to make these extra deductions---

Yep, it has been proved before, by Carcul, tso (or cho?) or gurth.

I could have searched it for you, but since you're our designated archiver, I'll let you dig it out yourself.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Glyn » Tue Aug 05, 2008 11:21 am

Did you mean this one Matt?
RW wrote:Yes, you can use the symmetry as a constraint, see here. Can't remember if anyone has already provided a nice manual solution using this technique. But it should prove a lot easier than ER 11.2...
RW
Glyn
 
Posts: 357
Joined: 26 April 2007

re: arguing from symmetry

Postby Pat » Tue Aug 05, 2008 11:39 am

Glyn wrote:
RW wrote:Yes, you can use the symmetry as a constraint, see here.


thanks Glyn!!
    so all i had to do was,
    carefully read RW's post on the present page---
tarek, are you convinced?
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby RW » Tue Aug 05, 2008 11:40 am

Pat wrote:
    however, i'm still missing something here --
    from r1c7, the symmetrically opposite cell would be r9c3 (not r7c9)

Oops... Sorry, typo... Edited!

udosuk wrote:Yep, it has been proved before, by Carcul, tso (or cho?) or gurth.

It was proved by Gurth, actually in the post just above the one I linked to earlier, see here.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Glyn » Tue Aug 05, 2008 12:23 pm

Actually the symmetry of the Mauricio 37 clue puzzle is even greater
Using 90 degree clockwise rotations
Code: Select all
2-->1  6-->9
^   |  ^   |
|   v  |   v
3<--4  7<--8

4 times the info?
Glyn
 
Posts: 357
Joined: 26 April 2007

PreviousNext

Return to General