The New Sudoku Players' Forum

[gsf]

first determine the cyclic permutation from the "minimal" puzzle (isomorphic to the original)

Code: Select all

g -p ...6..3.7...12.6.5.........2.7.4.9.......3.1.5.4...........9.4.6.5......8.2.7....

which produces

Code: Select all

r(149)(267)(358)c(168259347)

Does that mean r1 is replaced by r4, etc. ... or is r4 replaced by r1, etc. Given that mathematical assignment is almost unversally expressed ... assign right-side-value to left-side-variable, I would hope it's ...

tmp = r1; r1 = r4; r4 = r9; r9 = tmp;

... not that it makes any difference if your program is the only one to "read" the output.

good question ronk
first, the parenthesized parts are not my notation: wiki (so it does make a difference)
that's a beautiful concise notation, and the best part is someone else did the hard part (defining it in mathematic terms)

the sudokuized parts (r c v i x a) are mine:
r: row permutations
c: colum permutations
v: cell value permutations
i: identity (when all permutations are the identity)
x: transpose (row-col transposition)
a: number of non-trivial automorphisms (fallout from the underlying algorithm)

so its implemented equivalent to the assignment with the tmp var

note on the solver: for -p it now requires at least two input puzzles
its also possible that that post referred to the old canonical form
here is an updated example

Code: Select all

 sudoku -p 100406700050000030000207000000904600000802000070000010306000008000000000802000405 ...6..3.7...12.6.5.........2.7.4.9.......3.1.5.4...........9.4.6.5......8.2.7....

which results in these permutations

Code: Select all

v(19867425)r(149258367)c(175286394)

you can then apply the permutation to map the first puzzle to the second

Code: Select all

sudoku -p'v(19867425)r(149258367)c(175286394)' 100406700050000030000207000000904600000802000070000010306000008000000000802000405

not very useful in this example
but you may have a collection of equivalent puzzles or templates/exemplars that need to be transformed using the same permutation

[ronk]

Given that mathematical assignment is almost unversally expressed ... assign right-side-value to left-side-variable, I would hope it's ...

tmp = r1; r1 = r4; r4 = r9; r9 = tmp;

... not that it makes any difference if your program is the only one to "read" the output.

[...]
so its implemented equivalent to the assignment with the tmp var
[...]

Code: Select all

 sudoku -p 100406700050000030000207000000904600000802000070000010306000008000000000802000405 ...6..3.7...12.6.5.........2.7.4.9.......3.1.5.4...........9.4.6.5......8.2.7....

which results in these permutations

Code: Select all

v(19867425)r(149258367)c(175286394)

you can then apply the permutation to map the first puzzle to the second

Code: Select all

sudoku -p'v(19867425)r(149258367)c(175286394)' 100406700050000030000207000000904600000802000070000010306000008000000000802000405

I'm obviously not understanding something. When I apply that permutation manually, I come up with ...

Code: Select all

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

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

[gsf]

I'm obviously not understanding something. When I apply that permutation manually, I come up with ...

Code: Select all

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

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

you scared me ronk, after just posting sudoku 2007-11-05
the notation is beautiful but the code inside is tricky
there was more than one instantiation of the code that got it backwards or inside out

here is the sequence split into 3 parts, along with the suoku command line
the final part verifies the sequence by re-calculating the permutations to get from one puzzle to the next
the first puzzle permuted with 'i' (the identity) yields the puzzle unchanged
the second puzzle has just the value permutations applied, the third value+row, and the last value+row+col

Code: Select all

"sudoku -f%#pg -p'i' 100406700050000030000207000000904600000802000070000010306000008000000000802000405"

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

"sudoku -f%#pg -p'v(19867425)' 100406700050000030000207000000904600000802000070000010306000008000000000802000405"

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

"sudoku -f%#pg -p'v(19867425)r(149258367)' 100406700050000030000207000000904600000802000070000010306000008000000000802000405"

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

"sudoku -f%#pg -p'v(19867425)r(149258367)c(175286394)' 100406700050000030000207000000904600000802000070000010306000008000000000802000405"

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

# combine above into one file p.dat

"sudoku -pl p.dat"

v(19867425)
r(149258367)
c(175286394)


[gsf]

ronk, I ran the following to see what you did

Code: Select all

sudoku -p 100406700050000030000207000000904600000802000070000010306000008000000000802000405 700000028000000056090040000201605000000000000006307000400900072000000045030010000


it lists the permutation that converts the first puzzle (the original) to the second (the one you got by hand)
those permutations are:

Code: Select all

v(19867425)r(176385294)c(149368257)


compared to the original

Code: Select all

v(19867425)r(149258367)c(175286394)


you applied the v permutation in the correct left-to-right order
but you either applied the r and c permutations in the incorrect right-to-left order
not that far off (my error is invariably off-by-one)
or
you didn't start with the original puzzle

[ronk]

it lists the permutation that converts the first puzzle (the original) to the second (the one you got by hand)
those permutations are:

Code: Select all

v(19867425)r(176385294)c(149368257)


compared to the original

Code: Select all

v(19867425)r(149258367)c(175286394)


you applied the v permutation in the correct left-to-right order
but you either applied the r and c permutations in the incorrect right-to-left order

I manually appled all permutations in the same order. One permutation in left-to-right order and the others right-to-left isn't exactly a poster child for consistency, is it

But even after reversing the r and c permutation order, I still haven't figured out the error in my manual method. I'll try again later.

[edit: OK aonother try using "right-shift" on the r and c permutation worked fine.

I still think the v, r and c permutation orders should all be the same.]

[Mauricio]

Can you actually come up with the same result by applying the v(19867425)r(149258367)c(175286394) permutation manually Even after reversing the r and c permutation order, I still cannot.

I corroborate gsf reply, you are not understanding the notation,
c(158347269) means you send c1 to c5, c5 to c8, c8 to c3, c3 to c4, c4 to c7, c7 to c2, c2 to c6, c6 to c9 and c9 to c1, but all at the SAME time.

I see it now, what ronk did, v(19867425)r(176385294)c(149368257)

the permutation (149368257)=(94)(39)(63)(86)(28)(52)(75)(17), aplying the transpositions from right to left. In other words, instead of doing the permutation (175286394), you swapped c1 and c7, THEN swapped c7 and c5, then c5 and c2 and so on.

[gsf]

I corroborate gsf reply, you are not understanding the notation,
c(158347269) means you send c1 to c5, c5 to c8, c8 to c3, c3 to c4, c4 to c7, c7 to c2, c2 to c6, c6 to c9 and c9 to c1, but all at the SAME time.

I see it now, what ronk did, v(19867425)r(176385294)c(149368257)

the permutation (149368257)=(94)(39)(63)(86)(28)(52)(75)(17), aplying the transpositions from right to left. In other words, instead of doing the permutation (175286394), you swapped c1 and c7, THEN swapped c7 and c5, then c5 and c2 and so on.

nice observation
to do it manually you always copy from the original into the new
this results in all at the same time

[gsf]

But even after reversing the r and c permutation order, I still haven't figured out the error in my manual method. I'll try again later.

try to follow the example where the row permutations are done (puzzle 2 to puzzle 3)
r1 from puzzle 3 goes to r4 in puzzle 4 and stays there

[Mauricio]

[edit: OK aonother try using "right-shift" on the r and c permutation worked fine.

I still think the v, r and c permutation orders should all be the same.]

They are the same, you still are not undersanding the notation, but you had fallen in an equality, ie, (149368257)=(41)(94)(39)(63)(86)(28)(52)(75). The right hand side being what I think you are doing (without noticing it).

[ronk]

[edit: OK another try using "right-shift" on the r and c permutation worked fine.

I still think the v, r and c permutation orders should all be the same.]

They are the same, you still are not understanding the notation ...

By not "the same", I'm referring to a cyclic left-shift of digit values and a cyclic right-shift of the contents of rows and columns. For the v(19867425)r(149258367)c(175286394) permutation being discussed ...

Code: Select all

v(  1  9  8  6  7  4  2  5

  /  /  /  /  /  /  /  /   (left cyclic shift)
 v  v  v  v  v  v  v  v

5  1  9  8  6  7  4  2

Digit 1 replaces digit 5, 9 replaces 1, etc.


r(1  4  9  2  5  8  3  6  7)

    \  \  \  \  \  \  \  \  \   (right cyclic shift)
     v  v  v  v  v  v  v  v  v

      4  9  2  5  8  3  6  7  1

The contents of r7 replaces the contents of r1, r6 replaces r7, etc.

For consistency sake all I'm saying is ... I think the cyclic shifts should all be in the same direction.

If I didn't now understand the notation, would I be able to duplicate gsf's "step-by-step" results here? I think not.

[gsf]

By not "the same", I'm referring to a cyclic left-shift of digit values and a cyclic right-shift of the contents of rows and columns. For the v(19867425)r(149258367)c(175286394) permutation being discussed ...

Code: Select all

v(  1  9  8  6  7  4  2  5  )

  /  /  /  /  /  /  /  /   (left cyclic shift)
 v  v  v  v  v  v  v  v

5  1  9  8  6  7  4  2


Digit 1 replaces digit 5, 9 replaces 1, etc.

all of the cyclic notation for my solver (and from the wiki refernced above) reads from left to right:

Code: Select all

1 => 9
9 => 8
8 => 6
6 => 7
7 => 4
4 => 2
2 => 5
5 => 1
3 => 3  (identities implicit in cyclic notation)


reading from right to left perfoms the inverse

thinking about it in terms of shifts may be getting in the way
the cyclic notation is basically a compact representation of the map of each original value to its permuted value
compact because it does not list identity maps and only lists other values once

[Red Ed]

Reading (19867425) as a permutation of the symbols 1...9, mathematicians would interpret it as the simultaneous replacement of

• 1s with 9s
• 2s with 5s
• (3s left untouched)
• 4s with 2s
• etc.

This is bog-standard.

On the other hand, reading (149258367) as a permutation of rows 1...9 in a matrix, there can be some confusion. Either ...

• move r1 to r4
• move r2 to r5
• (leave r3 where it is)
• move r4 to r2
• etc.

... which is how gsf intended it and how most of us (me included) read it; or ...

• replace r1 with r4
• replace r2 with r5
• (leave r3 where it is)
• replace r4 with r2
• etc.

... which is how ronk interpreted it and which arguably looks more consistent with the digits description ("replace X with Y").

The fact is, the notation's confusing when applied to rows in a matrix.

To my eyes, MathWorld suggests that, in fact, ronk's interpretation is better.

For example, in the permutation group {4,2,1,3}, (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering {1,2,3,4}, the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., 1->4->3->1.

[gsf]

The fact is, the notation's confusing when applied to rows in a matrix.

To my eyes, MathWorld suggests that, in fact, ronk's interpretation is better.

For example, in the permutation group {4,2,1,3}, (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering {1,2,3,4}, the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., 1->4->3->1.

thanks for figuring this out

I didn't have a chance of seeing it because I don't consider the row/col permutations a matrix operation
because I don't code the grid as a matrix
the row/col/box houses are coded by indirect indexing
and permutations basically treat the indirect indices as labels
as such there is no difference between value/row/col permutations
they are all treated as label permutations
so the cyclic notation for labels reads as a left-to-right, from=>to map, just like the wiki
I'll clarify this with an example in the --man documentation

[Pat]

#16

21 clues ( = layout #132 minus the clue in r1 )

Code: Select all


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



[Pat]

#17

5..3.6.....9.1.4.....5...7.37....6..8.......9..1....87.6...8.....8.4.1.....7.9..3

[ play ]

24 cells given
(layout 203 of the Patterns Game)

Code: Select all


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