Phistomefel's Theorem

Advanced methods and approaches for solving Sudoku puzzles

Phistomefel's Theorem

Postby Wecoc » Sat Nov 14, 2020 7:28 pm

Phistomefel's Theorem (sometimes also called Phistomefel's Ring) stipulates that if we divide any solved sudoku grid like this:
Code: Select all
AA.....AA
AA.....AA
..CBBBC..
..B...B..
..B...B..
..B...B..
..CBBBC..
AA.....AA
AA.....AA

then the contents on A equal the contents on B+C. In other words, if we know which digits go exactly on region A, those exact same digits will appear on B+C, and vice versa.
Further explanation on this can be found here: Neuer (?) Fund über Sudoku-Geometrie

Note: Probably this isn't news to you, but I couldn't find another topic about this here

This can probably be used on classic sudoku as a way to spot fishes like keith's technique, but where this property really shines is on figure-based sudoku variants like Killer, Arrow, etc.

I've seen some killer sudokus where JSudoku needs recursion with +30 guesses to find the solution, and a human can find it with a pretty straight-forward path using this technique (more on that later).

Furthermore, computers could use this technique in a more generalized way: columns, rows and stacks can be swapped, giving other patterns that are still perfectly valid since permutations don't affect the theorem, they simply move the regions around. The only distinction between B and C appart from the distinction used to prove the equality is that C shares a box with A; that difference is often omitted to simplify the possible patterns. A human can easily spot the symmetric ones, but there are exactly 729 (3^6) unique patterns.

Patterns: Show
Code: Select all
AA.....AA
AA.....AA
..CBBBC..
..B...B..
..B...B..  Default
..B...B..
..CBBBC..
AA.....AA
AA.....AA

AA.....AA
..CBBBC..
AA.....AA
..B...B..
..B...B..  Swapping r23
..B...B..
..CBBBC..
AA.....AA
AA.....AA

..CBBBC..
AA.....AA
AA.....AA
..B...B..
..B...B..  Swapping r13
..B...B..
..CBBBC..
AA.....AA
AA.....AA

(...)

....B..B.
....B..B.
....B..B.
...A.AA.A
BBB.C..C.  Swapping c23-c78-r23-r78-c{123|456}-r{123|456}
...A.AA.A
...A.AA.A
BBB.C..C.
...A.AA.A

You can download the full list here: phistomefel.txt


This is an example I made some days ago: Anti-King Little Rose (the Anti-King restriction must be included manually on JSudoku)
Example: Show
Image
Code: Select all
3x3::k:17:18:5645:19:20:21:5646:22:23:24:5645:25:2049:2049:2049:26:5646:27:5645:28:4870:4870:4357:3586:3586:29:5646:30:2055:4870:4357:4357:4100:3586:2051:31:32:2055:3850:3850:33:4100:4100:2051:34:35:2055:2825:3850:3851:3851:4620:2051:36:5648:37:2825:2825:3851:4620:4620:38:5647:39:5648:40:2056:2056:2056:41:5647:42:43:44:5648:45:46:47:5647:48:49:

JSudoku can only find 4 digits using "Deduce All Moves", and requires 13 guesses with "Recursively Solve", 20 if we use recursion from start.

But here's how it can be solved using this trick:
Solution path (first steps): Show
We use this pattern, which is symmetrical, therefore not hard to spot by a human:
Code: Select all
A.A...A.A
.C.BBB.C.
A.A...A.A
.B.....B.
.B.....B.  Swapping r23-c23-r78-c78
.B.....B.
A.A...A.A
.C.BBB.C.
A.A...A.A


The crucial point here is the 8-cages are {125} or {134} so they can't have a 6 or higher, and the 22-arrows are {679} or {589} so they can't have a 4 or lower.
Now it shouldn't be hard to see that {679} is impossible in an arrow because it uses two "non-fillable" cells using the BC region at once, that would mean another of the arrows must also be {679} making the disbalance even higher. In other words, all 22-arrows are {589}.

Not only that, but if 5 is in the middle (C) of an arrow then we are defining on the A region two "non-fillable" cells at once again. Also, there will be four 5s in the A region which can only come from the 8-cages. All the 8-cages must be {125}.

That means we have this.

Code: Select all
  12  .   589 .   .   .   589 .   12
  .   89  .   125 125 125 .   89  .
  589 .   12  .   .   .   12  .   589
  .   125 .   .   .   .   .   125 .
  .   125 .   .   .   .   .   125 .
  .   125 .   .   .   .   .   125 .
  589 .   12  .   .   .   12  .   589
  .   89  .   125 125 125 .   89  .
  12  .   589 .   .   .   589 .   12


and from there there are various ways to proceed, the more obvious one is the 19-cage.

We still don't have any digit, but as a comparison, if we use that as a starting point on JSudoku, it can solve it without recursion and without many hard steps:

Code: Select all
79 Naked Single
2 Hidden Single
3 Unique Pair
5 Naked Pair
3 Hidden Pair
5 Unique Triplet
3 Intersection
3 Naked Triplet
1 Hidden Triplet
1 Odd Pairs
3 Odd Triplets
1 Conflicting Pair
4 Quadruple Innies & Outies
1 Pointing Pair
1 Generalized Naked Subset
5 Turbot Fish
1 Y-Wing
Last edited by Wecoc on Wed Nov 25, 2020 7:41 pm, edited 1 time in total.
Wecoc
 
Posts: 77
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Phistomefel's Theorem

Postby mith » Sat Nov 14, 2020 8:49 pm

It's been mentioned elsewhere, but Phistomefel is another way of looking at SK Loops (which are implemented in some computer solvers), at least in classic sudoku, and both are subsets of MSLS. As you say, it really shines in sum-based puzzles!
mith
 
Posts: 339
Joined: 14 July 2020

Re: Phistomefel's Theorem

Postby coloin » Sun Nov 15, 2020 4:19 pm

Yes that a good way to demonstrate eliminations
Code: Select all
+---+---+---+
|12.|...|.34|
|3..|...|.21|
|...|...|...|
+---+---+---+
|...|56.|...|
|...|7.8|...|
|...|.9.|...|
+---+---+---+
|...|...|...|
|21.|...|..3|
|43.|...|.12|
+---+---+---+

which solves to pm grid
Code: Select all
+-------------------+-------------------+-------------------+
| 1     2     56789 | 689   578   5679  | 56789 3     4     |
| 3     56789 56789 | 4689  4578  5679  | 56789 2     1     |
| 56789 56789 4     | 123   123   123   | 56789 56789 56789 |
+-------------------+-------------------+-------------------+
| 789   4789  123   | 5     6     123   | 123   4789  789   |
| 569   4569  123   | 7     123   8     | 123   4569  569   |
| 5678  5678  123   | 123   9     4     | 123   5678  5678  |
+-------------------+-------------------+-------------------+
| 56789 56789 56789 | 123   123   123   | 4     56789 56789 |
| 2     1     56789 | 4689  4578  5679  | 56789 56789 3     |
| 4     3     56789 | 689   578   5679  | 56789 1     2     |
+-------------------+-------------------+-------------------+


Need to go back to SK-loops ... because I thought it was a 3 clue diagonal pattern in the corner boxes ..
coloin
 
Posts: 1930
Joined: 05 May 2005

Re: Phistomefel's Theorem

Postby Wecoc » Sun Nov 15, 2020 8:43 pm

mith wrote:It's been mentioned elsewhere, but Phistomefel is another way of looking at SK Loops [...] and both are subsets of MSLS.

That's right, I forgot to mention that.
I've seen very extended explanations on that on Tom Collyer's blog (including the comments section): Puzzle 350 & The MSLS: Revolutions

Wecoc wrote:A human can easily spot the symmetric ones, but there are exactly 729 (3^6) unique patterns.

I want to extend a bit more on that as well. There are only 3 fully symmetrical patterns; the "default" ring, r23-c23-r78-c78 and r13-c13-r79-c79.
Symmetrical Patterns: Show
Code: Select all
AA.....AA
AA.....AA
..CBBBC..
..B...B..
..B...B..
..B...B..
..CBBBC..
AA.....AA
AA.....AA

A.A...A.A
.C.BBB.C.
A.A...A.A
.B.....B.
.B.....B.
.B.....B.
A.A...A.A
.C.BBB.C.
A.A...A.A

C..BBB..C
.AA...AA.
.AA...AA.
B.......B
B.......B
B.......B
.AA...AA.
.AA...AA.
C..BBB..C

The total number of patterns comes from every permutation, but filtering out the repeated patterns. Columns and rows can only permutate inside the same "stack".
default [1] -> column permutations [9] -> row permutations [81] -> column box permutations [243] -> row box permutations [729]

For comparison, here's the same applied on a 6x6 sudoku grid
default [1] -> column permutations [4] -> row permutations [36] -> column box permutations [63] -> row box permutations [105]

6x6 Patterns: Show
Code: Select all
AA..AA
..BB..
..BB..
..BB..
..BB..
AA..AA

B....B
B....B
.AAAA.
.AAAA.
B....B
B....B

(...)

You can download the full list here: phistomefel6x6.txt

Edit: here's the same applied on a 8x8 sudoku grid
default [1] -> column permutations [4] -> row permutations [64] -> column box permutations [128] -> row box permutations [192]

8x8 Patterns: Show
Code: Select all
AAA..AAA
...BB...
...BB...
...BB...
...BB...
...BB...
...BB...
AAA..AAA

(...)

You can download the full list here: phistomefel8x8.txt

The theorem can also be generalized for Latin Squares ;)
Last edited by Wecoc on Wed Nov 25, 2020 10:28 pm, edited 2 times in total.
Wecoc
 
Posts: 77
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Phistomefel's Theorem

Postby StrmCkr » Sun Nov 15, 2020 10:59 pm

coloin wrote:Yes that a good way to demonstrate eliminations
Code: Select all
+---+---+---+
|12.|...|.34|
|3..|...|.21|
|...|...|...|
+---+---+---+
|...|56.|...|
|...|7.8|...|
|...|.9.|...|
+---+---+---+
|...|...|...|
|21.|...|..3|
|43.|...|.12|
+---+---+---+

which solves to pm grid
Code: Select all
+-------------------+-------------------+-------------------+
| 1     2     56789 | 689   578   5679  | 56789 3     4     |
| 3     56789 56789 | 4689  4578  5679  | 56789 2     1     |
| 56789 56789 4     | 123   123   123   | 56789 56789 56789 |
+-------------------+-------------------+-------------------+
| 789   4789  123   | 5     6     123   | 123   4789  789   |
| 569   4569  123   | 7     123   8     | 123   4569  569   |
| 5678  5678  123   | 123   9     4     | 123   5678  5678  |
+-------------------+-------------------+-------------------+
| 56789 56789 56789 | 123   123   123   | 4     56789 56789 |
| 2     1     56789 | 4689  4578  5679  | 56789 56789 3     |
| 4     3     56789 | 689   578   5679  | 56789 1     2     |
+-------------------+-------------------+-------------------+


Need to go back to SK-loops ... because I thought it was a 3 clue diagonal pattern in the corner boxes ..


4 clue pattern over 4 boxes they just happen to land on the diagonals. (for the first versions published)
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 1196
Joined: 05 September 2006

Re: Phistomefel's Theorem

Postby Wecoc » Wed Nov 25, 2020 11:00 pm

I edited my last post to include the patterns on a 8x8 grid, since cam made a puzzle about it: Phistomefel Tribute
There are other grid sizes but they are not very interesting: 4x4 (2x2 boxes), 12x12 (4x3 boxes), 16x16 (4x4 boxes)... :roll:
Wecoc
 
Posts: 77
Joined: 08 April 2019
Location: Girona, Catalonia


Return to Advanced solving techniques