Symmetrical Givens

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

Re: Symmetrical Givens

Postby eleven » Wed Jun 10, 2015 3:34 pm

ronk wrote:
eleven wrote:... i needed a couple of (symmetry) moves.
Code: Select all
.....7.6...4.3.5...7.6....3..1....32....1....45....1..5....8.9...3.5.2...8.9.....
+----------------------+----------------------+----------------------+
| 12389  1239   589    | 12458  2489   7      | 89     6      14     |
| 12689  1269   4      | 128    3      129    | 5      127    17     |
| 1289   7      589    | 6      2489   12459  | 89     124    3      |
+----------------------+----------------------+----------------------+
| 6789   69     1      | 578    6789   569    | 4      3      2      |
| 36789  369    89     | 24     1      24     | 67     578    56789  |
| 4      5      2      | 378    6789   369    | 1      78     6789   |
+----------------------+----------------------+----------------------+
| 5      124    67     | 12347  2467   8      | 367    9      1467   |
| 19     149    3      | 147    5      146    | 2      1478   14678  |
| 12     8      67     | 9      2467   12346  | 367    1457   14567  |
+----------------------+----------------------+----------------------+


Hi eleven. Please provide the moves, particularly the symmetry moves, you used to get to these pencilmarks.

Ron,
i had not tried to come to this grid with symmetry moves, but it is relatively easy. After an L-wing you have this grid:
Code: Select all
+-------------------------+-------------------------+-------------------------+
| 12389   1239    2589    | 12458   2489    7       | 489     6       1489    |
| 1268    1269    4       | 128     3       129     | 5       1278    179     |
| 1289    7       2589    | 6       2489    12459   | 489     1248    3       |
+-------------------------+-------------------------+-------------------------+
| 6789    69      1       | 4578    46789   4569    | 46789   3       2       |
| 236789  2369    26789   | 2478    1       2469    | 46789   4578    456789  |
| 4       5       26789   | 2378    26789   2369    | 1       78      6789    |
+-------------------------+-------------------------+-------------------------+
| 5       1246    267     | 12347   2467    8       | 3467    9       1467    |
| 179     1469    3       | 147     5       146     | 2       1478    1468    |
| 1267    8       267     | 9       2467    12346   | 3467    1457    14567   |
+-------------------------+-------------------------+-------------------------+

Now a 6 or 8 in r6c3 implies 8 or 6 in r4c7, then r4c12/r6c89=79, and r5c46=79. This kills all 7's in row 8 -> contradiction.
Similar r6c3/r4c7=79 leads to r4c12/r6c89/r5c46=86, which kills all 6's in row 8.

From the other side a Kraken 7r8:
7r8c1/9r2c9->7r8c2->8r6c8/6r4c2 => r6c3<>68
7r8c4/9r3c6->79r46c5->[Edit:](ALS 6789r4c125)->68r4c12/r6c89 => r6c3<>68
7r8c8/9r2c2->8r6c8/6r4c2 => r6c3<>68

Similar for 6r8 => r6c3/r4c7<>79

Please note, that in some of my following moves of that post i did use the double exocet properties.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: Symmetrical Givens

Postby Serg » Sun Jun 14, 2015 1:55 pm

Hi, people!
I'd like to present some considerations concerning checking valid puzzles for minimality.
Usual approach requires checking all puzzle's clues, one by one. If the puzzle will be still valid after next clue removal, it is not minimal, but if each clue removal invalides the puzzle, then this puzzle is minimal. It turns out, that if a valid puzzle has automorphisms, it requires checking not all, but only part of the clues.

Let me define a clue being critical, if after its removal valid puzzle becomes invalid. Opposite, if after clue removal valid puzzle stays valid, the clue is non-critical.

If a puzzle has (non-trivial) automorphisms, they form group, partitioning grid cells into orbits. Each orbit's cells pass each other by the action of automorphisms group. Let N - number of puzzle's automorhisms. Then maximal possible orbit length is N. Though orbit length can be less, than N, it must divide N in any way. It can be proven, that all clues participating the same orbit, all are critical or all are non-critical. So, it isn't necessary to check all puzzle's clues for minimality. It is sufficient to check only one clue from each orbit to determine puzzle's minimality.

Let's consider an example.
blue published in this thread such 36-clue puzzle having quarter turn symmetry among its clues:
Code: Select all
. . . 4 . . . . .
. 6 7 2 . 3 4 9 .
. 5 4 . 7 8 3 6 .
. 4 9 . . . . 5 3
. . 8 . . . 6 . .
5 3 . . . . 7 2 .
. 8 5 6 9 . 2 3 .
. 7 2 5 . 4 9 8 .
. . . . . 2 . . .

This puzzle has 4 automorhisms:
1. 90-degrees turn;
2. 180-degrees turn;
3. 270-degrees turn;
4. "Do nothing" (0-degrees turn).

So, all 36 clues are partitioned into 9 orbits, each orbit contains 4 clue cells. Below is 1 orbit (of 9):
Code: Select all
. . . 4 . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . 3
. . . . . . . . .
5 . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . 2 . . .

To check this puzzle for minimality it's sufficient to check 9 clues - representatives of 9 orbits. For example, One can check cells
Code: Select all
. . . 4 . . . . .
. 6 7 2 . 3 4 . .
. . 4 . 7 8 . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Such approach gives 4-times speed-up during minimality check, because number of clues to check is decreased 4 times.

This method is useful for puzzles having symmetry among its clue values, because such puzzles always have non-trivial automorphisms.

It's no sense to use this method for minimality check of alone puzzle, but it can be useful during minimality check of a million puzzles' bunch, if those puzzles have the same automorphism groups or at least their automorphism groups contain given automorphism group as subgroup.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Symmetrical Givens

Postby champagne » Sun Jun 14, 2015 2:21 pm

Hi Serg,

quite true although I did not do it in the recent searches.

In fact, looking first for "minimal symmetry", this was not a critical issue.

In the pi_stick symmetry, with the high number of puzzles having a "minimal symmetry" but not strictly minimal, doing it could slightly change the run time, but the job is done on my side.
champagne
2017 Supporter
 
Posts: 5641
Joined: 02 August 2007
Location: France Brittany

Previous

Return to General