The New Sudoku Players' Forum

[coloin]

Thoughts on puzzle transformations. I dont recall this has been done ... maybe it has.
Back in 2007 this was the chat

I was able to perform specific simple structure transformations on text strings with a python program here

Isomorphic transformations which retain struture have long been known

Structure - swaps of the rows, columns bands and stacks and one reflection
6^8 x 2 = 3359232 ways
Clue - swaps aka relabelling
9! = 362880 ways

Converting a puzzle / or grid solution from one representation to another involves a set amount of transformations.

The structure is easier to visualize for me .. as a binary number plus a 8 digit base 6 number. The order of proceedings is ? probably important.
So firstly a reflection 1 [0 no reflection] and then 8 numbers. 0 is staying the same and 1-5 represents a row,column, band or stack swap [x8 of].
Example 1 - 23,140,245
So there would be 3359232 combinations to change any one particular grid. I'm guessing the reflection and bands should be performed first.

The clue swap options are smaller but it is much more complicated !!
It seems clues either stay the same, have a direct swap or cycle with 3,4,5,6,7,8,9 other clues !

I have differentiated between 2 way cycles [aka direct swaps] and greater cycles , and maybe this is not the best way .
A 3 way cycle would be 1<->2,2<->3 which is actually 2 direct swaps....very confusing, as is this list of possibilities !

Direct swaps first .....

Code: Select all

4 direct swaps and 1 clue stays the same
3 direct swaps and 3 clues cycle
3 direct swaps and 3 clues stay the same
2 direct swaps and 3 clues cycle and 2 clues stay the same
2 direct swaps and 4 clues cycle and 1 clue stays the same
2 direct swaps and 5 clues cycle and 0 clues stay the same
2 direct swaps and 5 clues stay the same
1 direct swap and  7 clues stay the same
1 direct swap and  3 clues cycle  4 clues stay the same
1 direct swap and  4 clues cycle  3 clues stay the same
1 direct swap and  5 clues cycle  2 clues stay the same
1 direct swap and  6 clues cycle  1 clue stays the same
1 direct swap and  7 clues cycle  0 clues stay the same

but there are more if there are no direct swaps then

Code: Select all

0 clues stay the same
  3 cycle groups of 3 cycle
  2 cycle groups of 4 and 5
  2 cycle groups of 3 and 6
  1 cycle group of 9

1 clue stays the same
  2 cycle groups of 4 and 4
  2 cycle groups of 3 and 5
  1 cycle group of 8

2 clue stays the same
  2 cycle groups of 3 and 4
  1 cycle group of 7
 
3 clues stay the same
  2 cycle groups of 3 and 3
  1 cycle group of 6

4 clues stay the same   
  1 cycle group of 5

5 clues stay the same
  1 cycle group of 4

6 clues stay the same
  1 cycle group of 3

9 clues stay the same 

Just how the 362880 number relates to all this is unclear however !!

[coloin]

Adding to this.
I think its more complex than Ive outlined and indeed I have omited to observe that row swapping can be cyclic ... or should it be just 2 swaps perhaps.
On the clues side, of course there maybe only 8 clues in a puzzle and this changes things.
Also a cycle has direction [clockwise/anticlockwise] and this might well lead to a different transformation result.
And finally I didnt mention that it is possible to have a row and column swap which can nearly be the same as a clue swap.

Code: Select all

+---+---+---+
|1..|...|...|
|.9.|...|...|
|...|123|45.|
+---+---+---+
|..9|7..|..8|
|..5|.6.|.2.|
|..4|..8|3..|
+---+---+---+
|..6|..7|8..|
|..7|.5.|.4.|
|...|2..|..7|
+---+---+---+    1<->9 


Similarly automorphic grids will revert to the original after defined transformations.....
Perhaps it just is what it is.

[JPF]

After several readings, I'm still not sure I understand what you're looking for.

JPF

[coloin]

When someone posts a puzzle..... and it turns out to be an isomorph of a previously posted puzzle ....this has happened many times and recently.
Here and Here
and many times involving Artol's puzzle

We make this blanket statement because either the minlex puzzle is the same or the puzzle in the minlex solution grid is the same

Essentially the rows and columns can be swapped and the puzzle relabelled and we get the same puzzle.

So i am looking at just how one gets [maps] from one puzzle A to one puzzle B, and if its possible to define it..

Issues to address perhaps
The minlex bug in the minlexing programs available
Automorphic puzzles can be mapped ... but how do you show it ?

[champagne]

We make this blanket statement because either the minlex puzzle is the same or the puzzle in the minlex solution grid is the same

Essentially the rows and columns can be swapped and the puzzle relabelled and we get the same puzzle.

So i am looking at just how one gets [maps] from one puzzle A to one puzzle B, and if its possible to define it..

May be an idea

Express both permutations to get the minlex morph, and combine the 2 permutations.

[JPF]

In the following, "puzzle" refers to a subgrid solution (including a solution grid).
Indeed, one method consists of using the Minlex of a puzzle.

If the puzzle P is not automorphic, there exists a unique transformation t such that tP = M, where M is the minlex of P.

Proof: If t1 and t2 were two distinct transformations leading from P to its MinLex, we would have t1P = t2P = M.
And thus (t'2t1)P = P , where t'2 is the inverse of t2.

And since P is not automorphic, t'2t1 = e, and therefore t1 = t2 , which is in contradiction with the initial hypothesis.

So, to compare two puzzles P and Q , we calculate their MinLex, M1 and M2, along with the associated transformations f and g

M1=fP
M2=gQ

P and Q are equivalent if M1 = M2 and in that case : fP=gQ ; hence: Q=(g'f)P

JPF

[eleven]

Well the hard step is to find the transformations of one puzzle's cells to the other (as well as from both solutions to a minimal representation of the solution grid).
Of course with a program you can quickly try all ([corrected]2*6⁸) possible transformations.
Then the digit swap is trivial, if a digit would change to different digits, the puzzles are not equivalent.
[Edit: you have to check all possible transformations of one puzzle's cells to the other, i.e. if the puzzle is already a solution grid, you have to check the digits for each possible transformation]

[champagne]

I think that JPF gave the right way. The comparison has to use the solution grid.
And if the solution grid has auto morphisms, Automorphisms have to be applied on one of the results to have all equivalent patterns.

Note: Automorphism in solution grids is not so common. The band 1 must have automorphism and only 32 out of the 416 band have more than 1 auto morph.

[eleven]

Yes, you can do it that way, but it is all but straightforward.
You need a puzzle solver, a minlex program, which tells you, what transformations it used, and one, which calculates automorphisms.
Neither a solver nor a minlex program are needed to check, if 2 puzzles are equivalent (and list basic transformations for it).

[coloin]

Well the hard step is to find the transformations of one puzzle's cells to the other......

Yes it is.... and transforming to a min lex version and comparing has been the workaround !

Thinking aloud... to go from [reference]puzzle1 to [isomorph]puzzle2...

I guess somehow summating the minlexgrid transformations theoretically would achieve this.

For the structure transformations to be reversible you need to define a reference box and a clue within this box.
It could be any cell within any box in the reference puzzle, but r1c1 and box 1 would be the obvious choice.

Without minlexing both puzzles, how to determine this equivalent cell in puzzle2 is not clear !
Its not clear either how to determine if a reflection is necessary.

Defining the reference box/clue [01-81] in puzzle2 would use up 2 band swaps and 2 row/col swaps.
The other band and row swaps I think are not order dependant...

The clues are actually the easy transformations.

[JPF]

So let P and Q be two isomorphic puzzles.

Code: Select all

P               Q
+---+---+---+   +---+---+---+
|1..|...|..2|   |..1|..7|...|
|.9.|4..|.5.|   |.6.|2..|...|
|..6|...|7..|   |9..|.3.|.5.|
+---+---+---+   +---+---+---+
|.5.|9.3|...|   |5..|.8.|4..|
|...|.7.|...|   |..2|1..|...|
|...|85.|.4.|   |.7.|..6|...|
+---+---+---+   +---+---+---+
|7..|...|6..|   |4..|...|89.|
|.3.|..9|.8.|   |...|.9.|.3.|
|..2|...|..1|   |...|...|5.7|
+---+---+---+   +---+---+---+

P : 1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
Q : ..1..7....6.2.....9...3..5.5...8.4....21......7...6...4.....89.....9..3.......5.7



A possible research avenue would be:
The transformation t that leads from P to Q is:

(01 03 12 10)(02 21 11 19)(04 57 15 64 05 75 13 55 06 66 14 73)(07 48 16 46)(08 30 17 28)(09 39 18 37)(22 56 24 65 23 74)(25 47)(26 29)(27 38)(31 62 33 71 32 80)(34 53)(36 44)(40 63 42 72 41 81)(43 54)(49 61 51 70 50 79)(58 60 69 68 77 76)(59 78 67)

This transformation belongs to conjugacy class 187 as calculated by Red Ed.
Conjugacy class 187 was determined by 'footprint' of the length of the cycles (cycle type) : 12-6-6-6-6-6-4-4-4-4-4-3-2-2-2-2-2-2

This class has only 46656 members.

and... the rest of the reasoning remains to be specified

JPF

[champagne]

Yes, you can do it that way, but it is all but straightforward.
You need a puzzle solver, a minlex program, which tells you, what transformations it used, and one, which calculates automorphisms.
Neither a solver nor a minlex program are needed to check, if 2 puzzles are equivalent (and list basic transformations for it).

As all the transformation don't change the clue count per band/stack, I agree that a no match is often trivial to see.
For the same reason, in many cases, the possible move to get a match is unique and easy to point.
The same happens when you are looking for a min lexical morph.

[eleven]

I made a test now to clarify things. Not surprising it can be done in the way i described, but with 2 drawbacks:
- it is painfully slow, in my sample (with this non optimized python hack) it took about 20 seconds each for the 2 samples.
- though i can list the basic transformations, this is only one possible presentation (for sure not the simplest), since it depends on the order, in which they are tried.

I calculated all possible cell transformations, and printed those with the same cells as the target puzzle (in both samples there have been no number swaps):

Code: Select all

puzzles (jpf)
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
..1..7....6.2.....9...3..5.5...8.4....21......7...6...4.....89.....9..3.......5.7
results:
..6..2....1.7.....9...3..5.5...8.4....76......2...1...4.....89.....9..3.......5.7      [1, 5, 5, 1, 0, 2, 2, 1, 5]  7->2 and 7
..1..7....6.2.....9...3..5.5...8.4....21......7...6...4.....89.....9..3.......5.7      [1, 5, 5, 4, 3, 2, 5, 4, 5]  <<<< same


Code: Select all

puzzles (airto1's mangled)
..36....1.4..1..3.7....59.......36......8..2....4....7..1.....9.7..2..8.3....95..
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..
results:
1....7.9..9..6...5..32..8....18..2...5..3...96....4...3......1..7......3..4...7..      [1, 0, 3, 5, 1, 1, 2, 4, 2]  9->9 and 3
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..      [1, 0, 3, 0, 0, 2, 3, 3, 3]  <<<< same
1....3.6..9..7...5..34..1....87..2...5..3...99....1...7......4..6......3..2...8..      [0, 2, 5, 2, 1, 1, 5, 4, 2]  9->6 and 9
1....3.6..3..4...1..97..5....53..9...8..7...29....1...7......4..2......8..6...3..      [0, 2, 5, 3, 0, 2, 0, 3, 3]  3->3 and 9


Transformations were tried in the order reflection, stacks, bands, cols in stack 1,2,3, rows in band 1,2,3
The numbers mean: numbers 012 (of bands, stacks, cols in stack, rows in band) goes to
0:012, 1:102, 2:201, 3:210, 4:120, 5:021

side note: for fun i asked an AI to program it, to get a start. Many bugs were obvious, but others hidden, so it took me longer than doing it from scratch

[champagne]

Code: Select all

puzzles (airto1's mangled)
..36....1.4..1..3.7....59.......36......8..2....4....7..1.....9.7..2..8.3....95..
1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..


Hi Eleven,

With no computer help, I expected more something as this, done on the second example.
We keep in mind that all morphs have the same number of clues in band/stacks and boxes

here is another view of the 2 puzzles

Code: Select all

..3 6.. ..1
.4. .1. .3.  =9
7.. ..5 9..

... ..3 6..
...  .8 ..2.
... 4.. ..7  =6

..1 ... ..9
.7. .2. .8.
3.. ..9 5..  =8

6   8   9

Code: Select all

1.. ..7 .9.
.3. .2. ..8
..9 6.. 5.. =9

..5 3.. 9..
.1. .8. ..2
6.. ..4 ... =8

3.. ... .1.
.4. ... ..7
..7 ... 3.. =6

9    6    8


Both have a clue 6;8;9 in bands and stacks
both have a box distribution 0;2;3;3;3;3;3;3;3
so a match can not be excluded.

We can start moving the empty box as box 1 and the box with 2 clues as box 5, giving

Code: Select all

... ..3 6..
... .8. .2.
... 4.. ..7  =6

..1 ... ..9
.7. .2. .8.
3.. ..9 5..  =8

..3 6.. ..1
.4. .1. .3.  =9
7.. ..5 9..

6   8   9


Code: Select all

... .1. 3..
... ..7 .4.
... 3.. ..7  =6

3.. 9.. ..5
.8. ..2 .1.
..4 ... 6..  =8

..7 .9. 1..
.2. ..8 .3.
6.. 5.. ..9  =9
6   8   9


Again, a possible match, with a priority to align box 5

As the diagonal move is possible, we put the box 5 with all clues on the diagonal (this is true for the box 9), so we align the view2 on the view 1
To keep the box 5 aligned, we can exchange digits 2<=>9, but we have another digit 9 in band 2 of the first morph and in stack 2 of the second morph

So, to have a match, we can't touch digits 2;9 and we have to use the diagonal morph for the second view
box 5 morphed

Code: Select all

... 1.. 3..
... .7. .4.
... ..3 ..7   

..4 ... 6.. 
.8. .2. .1.
3.. ..9 ..5   

..7 9.. 1..
.2. .8. .3.
6.. ..5 ..9   

and the diagonal morph

Code: Select all

... ..3 ..6
... .8. .2.
... 4. .7..

1.. ... 9..
.7. .2 ..8.
..3 ..9 ..5

3.. 6.  .1..
.4. .1 . .3.
..7 ..5 ..9

A simple comparison with the view 1 show that moves in columns 1<=>3 and 7<=>9 gives the match, but from here, digits maps if needed would be easy to see as well.

[coloin]

I think eleven has crackered it ..... as has champagne !

although its almost always possible to piuck out a reference clue in a puzzle which is special/uniquely identifiable.

whether it be a single clue in a box/row/column, or one of a clue value, or indeed the only clue which is non mutable ot is not within {-1+1] of another puzzle....
this property is consistent in isomprphic puzzles, as champagne points out.

Maybe there will be a counter example in some puzzles ..and in artols puzzle its quite tricky to identify a reference clue

Code: Select all

+---+---+---+
|1..|..7|.9.|
|.3.|.2.|..8|
|..9|6..|5..|
+---+---+---+
|..5|3..|9..|
|.1.|.8.|..2|
|6..|..4|...|
+---+---+---+
|3..|...|.1.|
|.4.|...|..7|
|..7|...|3..|
+---+---+---+


and champagne is doing this - identifying the only box with 2 clues and the clue with 2 occurrances is the 2.

So the isomorph can be transformed with this box and row/column as a start - EDIT - actually use the whole box - as champagne demonstrates .

Regarding the clue "problem" and direct swaps / cycle swops...

There isnt a problem if we just go to an intermediate clue and the 9! options is evident [ also with both 8 clue values, as the 9th is a null with 9 options]

Code: Select all

1>A>2
2>B>1
3>C>5
4>D>6
5>E>7
6>F>8
7>G>9
8>H>3
9>J>4     this would be 1 direct swap and 7 cycle