Anti-GSP

Advanced methods and approaches for solving Sudoku puzzles

Anti-GSP

Postby shye » Sun Nov 20, 2022 4:07 pm

.
here is an exotic deduction i've become fascinated by recently, first explored (as far as i'm aware) in these puzzles: Antidote, Poison, and Serum
it is an extension off of Gurths Symmetrical Placement which you can read about here and here, but i will also provide a brief rundown of the logic and show how its similar to anti-GSP

GSP states that:
Code: Select all
if
- a puzzle has 1 solution
- the given information is entirely symmetrical in a particular way
then
- the solution must be symmetric in the same way

anti-GSP on the other hand says:
Code: Select all
if
- a puzzle has 1 solution
- the solution cannot be symmetric in a particular way
then
- the given information cannot be entirely symmetrical in the same way

you can think about it from the perspective of creating a sudoku, if you're only ever adding in symmetric clues, how can you ever reach an asymmetric solution? you either will end up with asymmetric clues, a symmetric solution, or no solution


i've gone and made a bunch of examples to show off different ways we can apply this
in each one i've made 8r1c1 the asymmetric digit, just so that it's clearer to see the symmetry in the remaining clues

Code: Select all
+-------+-------+-------+
| 8 . 1 | 2 3 . | . 9 . |
| . 7 . | . . . | . . 8 |
| 6 . . | . 8 4 | . . . |
+-------+-------+-------+
| 9 . . | . . . | 5 . . |
| 5 2 . | 4 . . | 9 . 3 |
| . . . | . 5 . | . . 2 |
+-------+-------+-------+
| . . 3 | . . . | . . 1 |
| 7 . . | . 2 . | . 6 . |
| . 6 . | . 4 8 | 7 . . |
+-------+-------+-------+
Serum
estimated rating: 9.0
8.123..9..7......86...84...9.....5..52.4..9.3....5...2..3.....17...2..6..6..487..

lets start simple, how could we determine a solution cannot be symmetric for a given puzzle? i think the easiest way to do so would be if a particular cell that is undisturbed after the symmetry operation cannot be a self-mapping digit, which is whats going on in this one
(ignoring 8r1c1,) we have positive diagonal symmetry with the mappings: 1-1, 2-2, 3-3, 4-5, 6-7, 8-9
however, r1c9 is not able to be 1, 2 or 3, so it has to be a paired digit, this implies that the solution to this puzzle is asymmetrical. note that this would not apply if r1c9 was instead given as a 4 for example, because then the given information is not symmetric

our conclusion is that r9c9 cannot be 9, it is the symmetrical counterpart to r1c1 and placing it in would lock the puzzle into having either no solution, or multiple
so -9r9c9, solves with a locked pair

Code: Select all
+-------+-------+-------+
| 8 3 . | . 7 . | . 5 6 |
| 1 . . | . 4 . | . . . |
| . . 2 | . . 8 | . . . |
+-------+-------+-------+
| . . . | . . . | 9 1 4 |
| . . . | . . . | . . . |
| 5 1 8 | . . . | . . . |
+-------+-------+-------+
| . . . | 9 . . | 2 . . |
| . . . | . 5 . | . . 1 |
| 7 4 . | . 6 . | . 3 . |
+-------+-------+-------+
FMK
estimated rating: 9.1
83..7..561...4......2..8.........914.........518.........9..2......5...174..6..3.

another way we could determine the solution is asymmetrical is if the mapping is incompatible with the symmetry type
in this puzzle, we nearly have rotational symmetry with the mapping 1-1, 2-2, 3-3, 4-5, 6-7, 8-9
this is incompatible because there are too many self-mapping digits, only one of 123 could occupy the undisturbed cell r5c5, leaving the other two to repeat in r5, c5, and b5

knowing this, we use our only asymmetrical given to conclude -9r9c9 again, this time giving stte

Code: Select all
+-------+-------+-------+
| 8 . 3 | . . 5 | . . 1 |
| . 9 . | . 1 . | . 8 . |
| 1 . . | 4 . . | 3 . . |
+-------+-------+-------+
| . . 6 | . . . | . 9 . |
| 4 . . | . 3 . | . . 5 |
| . 8 . | . . . | 7 . . |
+-------+-------+-------+
| . . 5 | . . 8 | . . 2 |
| . 7 . | . 2 . | . 6 . |
| 2 . . | 9 . . | 4 . . |
+-------+-------+-------+
Needle Pusher
estimated rating: 8.9
8.3..5..1.9..1..8.1..4..3....6....9.4...3...5.8....7....5..8..2.7..2..6.2..9..4..

now so far i've only shown symmetries that have ways of working under traditional GSP, but theres actually nothing to stop us from using "doomed" symmetries! those being, any symmetry type that wouldnt work under sudoku rules, stuff along the lines of a vertical flip
in this puzzle, the morph we will perform is swapping the rows to be 321654987, and swapping the columns to be 987654321 (using the shortcuts from elevens mapping categories it would be CxRxSx i believe)
or alternatively we can subdivide the grid into 3 rotationally symmetric regions, those being each band of the sudoku. this way of parsing it i first heard about in mith's puzzle Thunderstorm
from this our mapping is 1-1, 2-2, 3-3, 4-5, 6-7, 8-9
the undisturbed cells (r258c5) are fine, however the placements for the remaining self-mapping digits in rows 258 and boxes 258 will always result in a repeat, similar to the last puzzle

8r1c1 is breaking the symmetry here so therefore -9r3c9 stte

Code: Select all
+-------+-------+-------+
| 8 . 4 | . 3 . | 7 . . |
| . 9 . | . . . | . 3 . |
| 1 . . | . 9 . | . . 4 |
+-------+-------+-------+
| . . 7 | . . . | 5 . . |
| . 8 . | . . . | . 2 . |
| 5 . . | . . . | . . 1 |
+-------+-------+-------+
| . . 8 | 1 2 3 | 9 . . |
| . 2 . | 4 5 6 | . 8 . |
| 3 . . | 7 8 9 | . . 2 |
+-------+-------+-------+
Antithesis
estimated rating: 9.0
8.4.3.7...9.....3.1...9...4..7...5...8.....2.5.......1..81239...2.456.8.3..789..2

one last one to wrap up, although there are certainly more ways i can think to explore this, which i will likely continue to do so in this thread
in this puzzle we nearly have sticks symmetry (in rows) with the mapping 1-7, 2-8, 3-9, 4-4, 5-5, 6-6
and at first blush, it seems there isnt a way to disprove possible symmetric solutions, instead what is key to notice is that the undisturbed cells r25c456 form a DP if limited to only self-mapping digits. so we know for certain that if this puzzle was symmetric then it would have either multiple solutions or none! this particular deduction is very useful for sticks anti-GSP, as there are certain required givens needed to disambiguate the undisturbed cells of those puzzles

from this, -2r3c7 stte


let me know of any other ways you can think to apply this! i had a lot of fun exploring the logic and creating this set of examples, i'm very interested in this logic and would love to know your thoughts. also, if this has had documentation in the past that i'm unaware of, please leave that below :D
Last edited by shye on Fri Nov 25, 2022 4:58 pm, edited 1 time in total.
User avatar
shye
 
Posts: 275
Joined: 12 June 2021

Re: Anti-GSP

Postby shye » Thu Nov 24, 2022 2:02 pm

some more puzzles that show different applications of these 4 methods:

first of all, this puzzle by eleven that was posted in the same thread as Serum
Code: Select all
+-------+-------+-------+
| 9 . . | . . . | 2 . 4 |
| 7 . . | 2 . . | 8 . . |
| 3 . . | 1 . 8 | . . 5 |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | 4 . 6 |
| 8 . 7 | 3 . 2 | . . . |
+-------+-------+-------+
| . . 9 | . . . | 6 . . |
| . . 8 | . . 3 | . . 7 |
| . . 2 | 7 . 1 | 5 . . |
+-------+-------+-------+
estimated rating: 8.9
9.....2.47..2..8..3..1.8..5...............4.68.73.2.....9...6....8..3..7..27.15..

this can be solved with either the first method i mentioned: hidden 46 pair in r6 mean that r6c25 cannot be self-mapping digits
or with the last one: sticks symmetry requires r456c258 to be disambiguated yet here there are no givens there
2r1c7 breaks the symmetry so -3r7c9 btte


next up, a different look at incompatible mappings

i was looking at these puzzles by dobrichev with a 62-cell BUG and noticed the symmetric givens. whats cool about these is that adding any disambiguating digit gives you a unique puzzle with an anti-gsp deduction (although for many cases it wont be necessary or useful)
i took one of them and turned it into another example
Code: Select all
+-------+-------+-------+
| . . . | . 7 . | . 8 1 |
| . 4 . | . . 6 | . 7 . |
| 8 . . | . . . | 3 . . |
+-------+-------+-------+
| . . . | . . . | . 6 . |
| . 2 . | . 4 . | . . 7 |
| 1 . . | 3 . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 6 . | . 2 . | . 4 . |
| 5 . . | 1 . . | 9 . . |
+-------+-------+-------+
estimated rating: 8.5
....7..81.4...6.7.8.....3.........6..2..4...71..3...............6..2..4.5..1..9..

near positive-diagonal symmetry with the mapping 1-1, 2-2, 3-3, 4-4, 5-5, 6-6, 7-7, 8-9
diagonal symmetry requires 3 self-mapping digits not 7 (we can observe 2456 in b3 would repeat if symmetric)

so 8r1c8 is breaking the symmetry and therefore -9r2c9
this reduces the puzzle from 8.5 to 7.3 and can be solved with one more non-basic deduction

6r1c7 = (6-7)r7c7 = 7r8c7 - 7r8c1 = (47-2)r47c1 = 2r1c1
-6r1c1, solves with a naked pair
XSudo Input: Show
5 Truths = {247C1 67C7}
6 Links = {6r1 7r8 147n1 7n7}
1 Elimination --> r1c1<>6


lastly, i was playing around some more with doomed symmetries, as i think they're the most fascinating application of the logic. i noticed most of these symmetries are quite restricted to set up, which is to be expected since they can never work anyway
here is one with a very simple left-right mirror, i tried very hard to make it 8+ skfr but it didnt seem meant to be :(
Code: Select all
+-------+-------+-------+
| 8 . 1 | . . . | 2 . . |
| . 3 . | 7 . 8 | . 4 . |
| 5 . . | . 9 . | . . 6 |
+-------+-------+-------+
| 2 . . | 3 . 4 | . . 1 |
| . . 6 | . . . | 5 . . |
| . 8 . | . . . | . 7 . |
+-------+-------+-------+
| 4 . . | 6 . 5 | . . 3 |
| . . 3 | 2 . 1 | 4 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
estimated rating: 7.2
8.1...2...3.7.8.4.5...9...62..3.4..1..6...5...8.....7.4..6.5..3..32.14...........

swap columns to be 987654321 => mapping is 1-2, 3-4, 5-6, 7-8, 9-9
symmetry would require c5 to be filled with only 9s
8r1c1 breaks symmetry so -7r1c9 stte
User avatar
shye
 
Posts: 275
Joined: 12 June 2021

Re: Anti-GSP

Postby jovi_al01 » Wed Dec 07, 2022 7:07 pm

here's something i find interesting-- we can attach the anti-GSP to impossible deductions, rather than impossible symmetries! take this puzzle for example (skfr 9.0):
Code: Select all
Blindsided, by jovi_al

8.5.4.2.7
.928.7.6.
.........
..3....45
.........
12....3..
.........
.7.6.948.
6.4.2.1..

8.5.4.2.7.928.7.6............3....45.........12....3............7.6.948.6.4.2.1..


after basics:

Code: Select all
.------------------.---------------------.-------------------.
| 8     136   5    | 139    4      136   | 2     139   7     |
| 34    9     2    | 8      13     7     | 5     6     134   |
| 347   1346  67   | 12359  13569  12356 | 89    139   13489 |
:------------------+---------------------+-------------------:
| 79    68    3    | 1279   16789  1268  | 6789  4     5     |
| 45    45    6789 | 379    36789  368   | 6789  12    12    |
| 1     2     6789 | 4579   56789  4568  | 3     79    689   |
:------------------+---------------------+-------------------:
| 2359  358   89   | 13457  13578  13458 | 67    2357  236   |
| 235   7     1    | 6      35     9     | 4     8     23    |
| 6     358   4    | 357    2      358   | 1     3579 *39    |
'------------------'---------------------'-------------------'

if 9 were in r9c9, we'd have perfect symmetry, so 3 would be in the center. this would create a Double Junior Exocet using r4c12 and r6c89 as base cells, which is impossible due to r4c7 and r6c3 appearing in neither pair of base cells.
another way to see this: because DJE is a rank0 pattern, we would get the eliminations of [6789] from r37c124689, which is just too many cells without [6789] in those rows.
so, -9r9c9, stte
User avatar
jovi_al01
 
Posts: 102
Joined: 26 July 2021

Re: Anti-GSP

Postby shye » Fri Dec 09, 2022 5:50 am

jovi_al01 wrote:if 9 were in r9c9, we'd have perfect symmetry, so 3 would be in the center. this would create a Double Junior Exocet using r4c12 and r6c89 as base cells, which is impossible due to r4c7 and r6c3 appearing in neither pair of base cells.
another way to see this: because DJE is a rank0 pattern, we would get the eliminations of [6789] from r37c124689, which is just too many cells without [6789] in those rows.
so, -9r9c9, stte

this is fantastic! the way i'd see it would be to use the exocet logic to disprove 3r5c5, and then from there we disprove the possibility of a symmetric solution:

Code: Select all
.-------------------.---------------------.--------------------.
| 8     136    5    | 139    4      136   |  2     139   7     |
| 34    9      2    | 8      13     7     |  5     6     134   |
| 347   1346  *67   | 12359 *13569  12356 | *89    139   13489 |
:-------------------+---------------------+--------------------:
|#79   #68     3    | 12-79 *16789  1268  |#*6789  4     5     |
| 45    45    *6789 | 379   *6789-3 368   | *6789  12    12    |
| 1     2    #*6789 | 4579  *56789  45-68 |  3    #79   #689   |
:-------------------+---------------------+--------------------:
| 2359  358   *89   | 13457 *13578  13458 | *67    2357  236   |
| 235   7      1    | 6      35     9     |  4     8     23    |
| 6     358    4    | 357    2      358   |  1     3579  39    |
'-------------------'---------------------'--------------------'

XSudo Input: Show
14 Truths = {68C3 6789C5 79C7 4N127 6N389}
21 Links = {69r3 6789r4 6789r6 78r7 5n5 6789b4 6789b6}
5 Eliminations --> r4c4<>79, r6c6<>68, r5c5<>3


but any deduction that can eliminate 3r5c5 will also allow for a two-step solution. i'm really fond of this one in particular, using more uniqueness :D

Code: Select all
.------------------.-----------------------.-------------------.
| 8     136   5    | 139     4       136   | 2     139   7     |
| 34    9     2    | 8      #13     7      | 5     6     134   |
| 347   1346  67   |U12359  *569-13 U12356 | 89    139   13489 |
:------------------+-----------------------+-------------------:
| 79    68    3    |U1279   *16789  U1268  | 6789  4     5     |
| 45    45    6789 | 379     6789-3  368   | 6789  12    12    |
| 1     2     6789 |U4579   *56789  U4568  | 3     79    689   |
:------------------+-----------------------+-------------------:
| 2359  358   89   |U13457  *178-35 U13458 | 67    2357  236   |
| 235   7     1    | 6      #35      9     | 4     8     23    |
| 6     358   4    | 357     2       358   | 1     3579  39    |
'------------------'-----------------------'-------------------'

extended unique rectangle + externals
guardians: 5r3c5, 1r4c5, 5r6c5, 1r7c5
whichever is true forms a naked triple with r28c5, solves with anti-gsp
XSudo Input: Show
10 Truths = {1R47 2R34 4R67 5R36 28N5}
3 Links = {135c5}
AUR points {aur 2r3c4 5r3c4 2r3c6 5r3c6 1r4c4 2r4c4 1r4c6 2r4c6 4r6c4 5r6c4 4r6c6 5r6c6 1r7c4 4r7c4 1r7c6 4r7c6 }
5 Eliminations --> r357c5<>3, r3c5<>1, r7c5<>5


this puzzle also has a great example of being able to use the strong link anti-gsp gives between a symmetric solution and an asymmetric one (3r5c5 = 3r9c9)
here that link can be used to form a swordfish with 3s in r28
=> -3r37c159
reduces to skfr 7.7

thank you for providing the lovely puzzle!
User avatar
shye
 
Posts: 275
Joined: 12 June 2021

Re: Anti-GSP

Postby shye » Sat Sep 09, 2023 4:17 pm

Code: Select all
+-------+-------+-------+
| . 7 6 | . . . | . . . |
| 3 5 8 | . . . | . . . |
| 4 2 . | . . 6 | . . 5 |
+-------+-------+-------+
| . . . | . 9 3 | . 1 . |
| . . . | 1 5 . | . 2 . |
| . . 4 | 7 . . | . . . |
+-------+-------+-------+
| . . . | . . . | . 8 9 |
| . . . | 9 8 . | 2 . 7 |
| 8 9 5 | . . . | 1 3 . |
+-------+-------+-------+
Switch
estimated rating: 8.4
.76......358......42...6..5....93.1....15..2...47............89...98.2.7895...13.

here is a new example i whipped up. first, as usual, we observe the puzzle has a near symmetry on the negative diagonal with a mapping of 1-9, 2-8, 3-7, 4-6, 5-5, which is an impossible mapping (5s would repeat in b159)

however there are two additional digits breaking the symmetry here, not one. what we can say with this which i find really interesting is that there is a weak link between 2r1c9 and 1r2c9, for the puzzle to have a unique solution they cannot both be true.
for this puzzle it is easiest to just notice that the 1s and 2s in b3 have to be switched, but to generalise it for other puzzles we can see it as an AIC: (1=2)r1c9 - (1=2)r2c9, with the elims -2r1c9 and -1r2c9
User avatar
shye
 
Posts: 275
Joined: 12 June 2021

Re: Anti-GSP

Postby 999_Springs » Tue Sep 26, 2023 6:11 pm

in this thread, mike metcalf was looking for sudokus that have 180 rotational symmetry without relabelling the digits. such a puzzle cannot have a unique solution, because it would require a palindromic solution grid, with for example r1c5 = r9c5. but that didn't stop him looking for near misses. he found this one with 2 solutions:
m_b_metcalf wrote:
Code: Select all
 . 6 1 8 . . 9 . 3
 8 . . 6 . . 2 4 1
 9 . 4 . . . . 8 .
 7 . 5 . . . . 9 .
 . . . . 5 . . . .
 . 9 . . . . 5 . 7
 . 8 . . . . 4 . 9
 1 4 2 . . 6 . . 8
 3 . 9 . . 8 1 6 .

No. of givens =  33

brute found 2 solution(s), 2 or 5 at r1c1

if you assume r1c1=2, the puzzle has a unique solution and is skfr 7.2. but by anti-GSP, if r1c1 is 2, then r9c9 cannot be 2 because that leads to an impossible symmetry. this immediately reduces the puzzle to all singles and becomes skfr 2.0
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Anti-GSP

Postby StrmCkr » Fri Sep 29, 2023 11:08 pm

Code: Select all
.------------.------------.------------.
| 25  6   1  | 8   47  24 | 9   57  3  |
| 8   57  37 | 6   39  59 | 2   4   1  |
| 9   23  4  | 13  12  57 | 67  8   56 |
:------------+------------+------------:
| 7   12  5  | 23  68  14 | 38  9   46 |
| 24  13  68 | 79  5   79 | 68  13  24 |
| 46  9   38 | 14  68  23 | 5   12  7  |
:------------+------------+------------:
| 56  8   67 | 57  12  13 | 4   23  9  |
| 1   4   2  | 59  39  6  | 37  57  8  |
| 3   57  9  | 24  47  8  | 1   6   25 |
'------------'------------'------------'

interesting puzzle that the sym causes every cell to only have 2 digits:

where 5 unravels the "logic" easily and yet the "2" stays tangled in sub-net space.

there is probably some unknown sym isolation rule for this rotation {every cell is paired and mirrored in the transpose}

idea is kinda far fetched
like removing 1 clue from a valid puzzle shows the sym: crash the puzzle down to the 2 solution state {using pair wise digit morphology} then apply the anti gsp rule with the clue back in-place: so it has 1 solution by contra-position of impossible sim resulting in no solution. thinking out loud on this one.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006


Return to Advanced solving techniques