Automorphic sudokues

Advanced methods and approaches for solving Sudoku puzzles

Automorphic sudokues

Postby Mauricio » Sun Aug 12, 2007 9:18 am

I'll write about a technique that uses the automosphisms of a sudoku. It is a uniqueness technique that can be applied when the sudoku has a nontrivial automorphism. This property has been discussed before, but I have not seen a formal topic about that.

Nontrivial automosphism of a given sudoku are not trivial to discover, unless the sudoku is given in such a way that it is easy to discover it; moreover, if one scrambles the sudoku it can be almost impossible for the human eye to see the automorphism.

When this technique can be applied, it can be very useful though. Furthermore, it is very useful when the automosphism has fixed cells, and so this technique excels with diagonal automorphisms.

If we assume uniqueness of the solution, we have the following proposition:
  • If A is an automorphism of the puzzle , then A is too an automorphism of its solution.
Proof: By contradiction, suppose that A is an automorphism of the puzzle and not an automorphism of its solution. If we apply the automorphism A to the solution, the puzzle remains the same, and the solution changes (as A is not an automorphism of the solution, the solution must change when we apply the automorphism to the solution). We have constructed 2 different grids that complete the puzzle, the original solution and the morphed solution, and so the original puzzle has 2 solutions, a contradiction to the uniqueness of the solution.


To see how that proposition can be applied I give an example:
Code: Select all
#Example 1
. . .|. . 7|. 6 .
. 5 .|3 . .|8 . .
. . 9|. 4 .|. . 3
-----+-----+-----
. 7 .|1 . .|4 . .
. . 6|. 5 .|. 2 .
3 . .|. . .|. . 8
-----+-----+-----
. 2 .|6 . .|1 . .
4 . .|. 8 .|. . .
. . 7|. . 2|. . 5     ER 10.4

Note that after reflecting the sudoku along the main diagonal (r1c1-r9c9, r1 on top) and doing the permutation of digits 1->1,2->8,3->7,4->6,5->5,6->4,7->3,8->2,9->9, we obtain the same sudoku, so that must be an automorphism of the sudoku. If we assume uniqueness of the solution, then that automorphism is too an automorphism of the solution.
Code: Select all
.------------------.------------------.------------------.
| 128   1348  12348| 2589  129   7    | 259   6     1249 |
| 1267  5     124  | 3     1269  169  | 8     1479  12479|
| 12678 168   9    | 258   4     1568 | 257   157   3    |
:------------------+------------------+------------------:
| 2589  7     258  | 1     2369  3689 | 4     359   69   |
| 189   1489  6    | 4789  5     3489 | 379   2     179  |
| 3     149   1245 | 2479  2679  469  | 5679  1579  8    |
:------------------+------------------+------------------:
| 589   2     358  | 6     379   3459 | 1     34789 479  |
| 4     1369  135  | 579   8     1359 | 23679 379   2679 |
| 1689  13689 7    | 49    139   2    | 369   3489  5    |
'------------------'------------------'------------------'

Now we focus on r1c1, if we suppose the solution has r1c1=2, then applying the automorphism to the solution we obtain a solution in which r1c1=8, it will certainly be a different solution. In the same way, if r1c1=8, then we can obtain a solution in which r1c1=2. Therefore the only choice for r1c1 is 1. Analogously we can deduce that r6c6=9, r8c8=9. We have reached
Code: Select all
.------------------.------------------.------------------.
| 1     348   2348 | 2589  29    7    | 259   6     249  |
| 267   5     24   | 3     1269  16   | 8     147   12479|
| 2678  68    9    | 258   4     1568 | 257   157   3    |
:------------------+------------------+------------------:
| 2589  7     258  | 1     236   368  | 4     35    69   |
| 89    1489  6    | 478   5     348  | 379   2     179  |
| 3     14    1245 | 247   267   9    | 567   157   8    |
:------------------+------------------+------------------:
| 589   2     358  | 6     379   345  | 1     3478  47   |
| 4     136   135  | 57    8     135  | 2367  9     267  |
| 689   13689 7    | 49    139   2    | 36    348   5    |
'------------------'------------------'------------------'

Here we can apply a sworfish on 9's and the rest is singles. We did not use a single complicated chain that Sudoku Explainer sees.

In this example the automorphism had fixed cells, and we could take advantage of those fixed cells to fill them.

A more extreme example is:
Code: Select all
#Example 2
1 . .|. 6 .|. . 5
. 9 .|. . 2|. 7 .
. . .|8 . .|3 . .
-----+-----+-----
. . 2|1 . .|. 4 .
4 . .|. . .|. . 8
. 8 .|. . 9|6 . .
-----+-----+-----
. . 7|. . 4|. . .
. 3 .|6 . .|. 1 .
5 . .|. 2 .|. . 9     ER 10.5

We observe that this sudoku is automorphic along the main diagonal and along the antidiagonal. Applying the technique we obtain r3c3=r5c5=r7c7=5, and r6c4=r4c6={3,7}. The rest is singles.

When the automorphism has a lesser number of fixed cells, less information can be deduced:
Code: Select all
# Example 3
. . .|7 . .|3 . .
. 2 .|. . 6|. 5 .
. . 8|. 2 .|. . 9
-----+-----+-----
. 3 .|1 . .|. . 4
. . 9|. . .|1 . .
6 . .|. . 9|. 7 .
-----+-----+-----
1 . .|. 8 .|2 . .
. 5 .|4 . .|. 8 .
. . 7|. . 3|. . .     ER 10.5

If we rotate this sudoku 180 degrees and do the permutation 1->9,2->8,3->7,4->6,5->5,6->4,7->3,8->2,9->1, the sudoku remains the same, the only fixed cell of that automorphism is r5c5, and the only fixed number is 5, so r5c5=5, and so
Code: Select all
. . .|7 . .|3 . .
. 2 .|. . 6|. 5 .
. . 8|. 2 .|. . 9
-----+-----+-----
. 3 .|1 . .|. . 4
. . 9|. 5 .|1 . .
6 . .|. . 9|. 7 .
-----+-----+-----
1 . .|. 8 .|2 . .
. 5 .|4 . .|. 8 .
. . 7|. . 3|. . .    ER=9.3

In this example, the automorphism technique only allowed us to reduce the complexity of chains to use, but it is still a improvement.

So far I have only used the automorphism technique to fill in cells, it can be used too to fill cells that are the automorphic image of an already filled cell, but that information is not very useful (as a deduction to fill a cell can be morphed to fill another cell) and I have decided not to explain it.

To end this post, I'll leave you with a puzzle that has "sticks symmetry", a symmetry that ravel pointed out:
Code: Select all
#Exercise 1
1 . .|. . .|. . .
. . .|4 . .|. 6 5
. . .|. 9 8|. . .
-----+-----+-----
2 . 7|. 3 .|9 . .
. 5 .|2 . .|. . 3
. 1 .|. . 7|. 4 .
-----+-----+-----
3 7 .|. . 2|8 . .
. . 6|3 . .|. 2 .
. . 1|. 7 .|. . 4   ER 10.0

It has a nontrivial automorphism with 9 fixed cells, after we apply the technique, the puzzle can be solved with singles only.

Questions? Suggestions?

Mauricio.

Many thanks to sudocue, it provided the nice pencilmarks.
Last edited by Mauricio on Sat Oct 20, 2007 7:06 pm, edited 2 times in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby RW » Sun Aug 12, 2007 11:00 am

Very nice examples Mauricio. Isn't this essentially the same as Gurths Symmetrical Placement technique? Anyway, you are right, there hasn't been a formal topic about this so I'm glad you started this thread.

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

Postby Mauricio » Sun Aug 12, 2007 11:17 am

RW wrote:Isn't this essentially the same as Gurths Symmetrical Placement technique? Anyway, you are right, there hasn't been a formal topic about this so I'm glad you started this thread.

Yes, it is the same idea.
BTW, what happened to gurth?
Mauricio
 
Posts: 1174
Joined: 22 March 2006


Return to Advanced solving techniques