Isomorphs and Normalization

Advanced methods and approaches for solving Sudoku puzzles

Isomorphs and Normalization

Postby gurth » Thu Jan 04, 2007 12:21 pm

ISOMORPHS AND NORMALIZATION

Any Sudoku can be scrambled into many so-called ISOMORPHS. But it is held that these isomorphs are mathematically equivalent, and the method of solution is identical for all of them.

But that only holds true if we ignore Symmetry Techniques (ST), such as introduced and developed by gurth, udosuk and RW. Scrambling can destroy or create symmetry, and so radically affect the solving process, at least for the human who relies on a CLEARLY APPARENT symmetry in order to use ST effectively.

So in effect isomorphs are NOT equivalent if they disturb or create symmetry.

In order to use ST effectively, it is essential that the Sudoku be scrambled into a symmetrical form, if it is not already symmetrical and if indeed a symmetry can be created by scrambling.

By NORMALIZATION is meant the scrambling of any asymmetrical Sudoku into a symmetrical version, where that is possible. Where it IS possible, there will usually be more than one symmetrical possibility. But it makes no mathematical difference which one we select: all the symmetrical isomorphs will be in a TRUE sense isomorphs.

What I am saying is that it is in future necessary for all serious solvers, including solver programs, to carry out the normalization procedure in order to reveal any latent symmetry and make ST accessible.

If this is not done on a regular basis, then many simple ST techniques will be missed, and the rating of the puzzle will be inflated unrealistically.

The actual process of nornmalization is quite easy to carry out by hand, it is interesting work and not too tedious, so solvers should be happy to have this new toy foisted on them.

You start by figuring out the symmetry by reason, then you interchange a few rows and columns, and that is all there is to it. When you have finished the puzzle, you change it back to its original asymmetic form. (Because YOUR symmetrical isomorph might not be the same as someone else's!)

For examples and practice, refer to the ongoing CHALLENGE on the thread Gurth's Puzzles on the General/Puzzle forum.


SYMMETRY TECHNIQUES

There are two types of symmetry that lend themselves to the development of ST (Symmetry Techniques). I have accustomed the world to many Emeralds, both variant and non-variant, based on 180-degree rotational symmetry, and solving techniques have been developed for these, notably by udosuk and RW.

But Emeralds are not necessarily confined to rotational symmetry only. An Emerald is strictly defined as ANY Sudoku having a symmetrical SOLUTION. If the clues are also symmetrical, then the Emerald is non-variant; if the clues are NOT symmetrical, but rotational symmetry is a GIVEN, then the Emerald is variant.

So, what other types of symmetry are there? In the context of ST, none that I have seen so far.
Except for the SECOND type of symmetry: DIAGONAL SYMMETRY.

I have seen no examples of DIAGONAL SYMMETRY except in my own Sudokus, commencing with GC28. Apparently this is something new in the world, or if not so, would appear to have been well and truly forgotten.

I consider these new emeralds with DIAGONAL SYMMETRY to be more important than the older ones with rotational symmetry: there are more useful techniques that can be applied to non-variant examples, also the puzzles are more satisfactorily constructed, and are likely to become more plentiful and popular than the older symmetry.
_____________________________________________________________________
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby udosuk » Fri Jan 05, 2007 9:25 am

Now that you've describe it, it's indeed a very ingenious technique...:)

Sadly we couldn't apply it to every sudoku puzzle, e.g. Ocean's SE 11.0 puzzle...:(

I'll try to get going in your challenges... One thing to set straight first: if we have a puzzle with diagonally symmetrical givens, does it guarantee the solution grid will be diagoally symmetrical too? I believe we have "proved" it in the rotational symmetry case... But it'd be nice if you can write up a formal proof for the diagonal symmetry scenario too...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby StrmCkr » Fri Jan 05, 2007 10:54 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:27 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby StrmCkr » Fri Jan 05, 2007 1:06 pm

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:27 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby gsf » Fri Jan 05, 2007 4:37 pm

StrmCkr wrote:i have a question/idea

has any one attempted to identify polymorphic grids as one and the same? ie.


search for isomorphism and canonicalization on the programmers' forum
isomorphism is a precise mathematical term used to describe objects that are indistinguishable under a set of permutations
the sudoku permutations are also defined on the forums

two mutually isomorphic sudoku are mathematically indistinguishable
the fact that a particular solver, human or machine, finds differences between the puzzles,
say in methods used to solve the puzzles, exposes a bias in the solver, not a flaw in "isomorphism"

for example, most machine solvers have inner loops that scan grids in specific patterns,
like row order or column order, and these patterns come into play when ties due to methods percieved to
be equal are broken by arbitrary choice, say, the first of many x-wings in row order
a different isomorphic permutation might expose a different x-wing that could lead down a
different solution path
to be specific, to the solver the x-wings may be equivalent, but under isomorphism they
may be mathematically distinct, and the distinction is just not uncovered by the solver
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Fri Jan 05, 2007 10:39 pm

deleted
Last edited by StrmCkr on Sat Dec 13, 2014 6:27 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby gsf » Fri Jan 05, 2007 10:49 pm

StrmCkr wrote:yes i understand that position, i was implying that there is technically only 1 solution to all puzzles not a singluar solution for each grid.

what does 1 solution to all puzzles mean?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Fri Jan 05, 2007 11:42 pm

All solutions are not equivalent. There are billions of different solutions, some big number starting with a 6:!: This number takes into account row and column swapping and interchanging numbers as you describe, only you can also exchange 3 numbers cyclically or 4 or 5 etc.

With 4x4 sudoku there are only 2 different solution grids, but that's a different matter.
ab
 
Posts: 451
Joined: 06 September 2005

Postby StrmCkr » Sat Jan 06, 2007 8:10 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:27 am, edited 3 times in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby RW » Sat Jan 06, 2007 8:18 am

StrmCkr wrote:yes there is a singular solution.

changing the position/rotation the solution is still the same solution.

StrmCkr, if you are double posting, could you at least read the replies to both threads. I gave you the exact amount of essentially different solutions in the other thread. Changing position and rotating is still the same solution, but there is still billions of solutions that cannot be transformed to the same solution. There's 5,472,730,538 different solutions and there's 6,670,903,752,021,072,936,960 solution morphs (source). If you manage to morph all of these 6e21 grids into one same puzzle I'll bake you a cake.

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

Postby StrmCkr » Sat Jan 06, 2007 8:34 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:28 am, edited 5 times in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby RW » Sat Jan 06, 2007 8:38 am

Here's two:
593876214481295763762143589236914875847652391159738426675381942328469157914527638
589732614621854379743916825835129746417568293296347158968471532372695481154283967

You can probably take any two solutions to two randomly chosen puzzles and they will be different.

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

Postby RW » Sat Jan 06, 2007 9:44 am

StrmCkr wrote:heres a weird way to get them all equal

You do not get them all equal by doing that. I'm not sure what you're trying to say, but it seems to me that you are using two subgrids from the same solution to solve the first one. If you don't know the solution, from where do you get the other subgrid?

There's variants where you must have multiple subgirds to find the original solutions (twin equivalent and twin corresponding sudokus), but these are variants. Normally you only have one grid to work from.

And please, do not say again that all grids are equal until you can show by valid permutations how to make the two grids I gave you equal (and tell me when you tried hard enough without any succes and I can give you a very simple proof on why they cannot be made equal).

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

Postby StrmCkr » Sun Jan 07, 2007 6:53 am

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:28 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 729
Joined: 05 September 2006

Postby udosuk » Mon Jan 08, 2007 12:49 pm

Human evolution is an amazing thing... First as a baby we learn to crawl, and as a toddler we learn to walk, as a kid we learn to run, and then (some) adults learn to drive a vehicle, or even pilot a plane... And some lucky ones even get to ride a shuttle/rocket to the space...

With these symmetric techniques, we first work out the fundamental rule (symmetrical clues -> symmetrical solution), then do more with the Emeralds and stuffs, and now this beautiful morphing technique...

And when we get familiar of morphing the grids back and forth, it's time to evolve even more... In fact we can just skip the morphing! The key is to identify the "matching digits"... And afterwards you can just manipulate the original grid... That's if you're observant and careful enough...

To know what it's all about, just check out the "gurth's puzzles" thread where I will post the details later on...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005


Return to Advanced solving techniques