Puzzles needing lots of locked candidates

Everything about Sudoku that doesn't fit in one of the other sections

Re: re(2): #7

Postby gsf » Sun Nov 04, 2007 7:22 pm

ronk wrote:
gsf wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: re(2): #7

Postby ronk » Tue Nov 06, 2007 11:41 pm

gsf wrote:
ronk wrote: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 . | . . .
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: re(2): #7

Postby gsf » Wed Nov 07, 2007 12:13 am

ronk wrote: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
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: re(2): #7

Postby gsf » Wed Nov 07, 2007 12:23 am

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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: re(2): #7

Postby ronk » Wed Nov 07, 2007 4:37 am

gsf wrote: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.]
Last edited by ronk on Wed Nov 07, 2007 2:50 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: re(2): #7

Postby Mauricio » Wed Nov 07, 2007 5:37 am

ronk wrote: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.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: re(2): #7

Postby gsf » Wed Nov 07, 2007 6:36 am

Mauricio wrote: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
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: re(2): #7

Postby gsf » Wed Nov 07, 2007 6:39 am

ronk wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: re(2): #7

Postby Mauricio » Wed Nov 07, 2007 9:14 am

ronk wrote:[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).
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: re(2): #7

Postby ronk » Wed Nov 07, 2007 1:51 pm

Mauricio wrote:
ronk wrote:[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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: re(2): #7

Postby gsf » Wed Nov 07, 2007 4:40 pm

ronk wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Wed Nov 07, 2007 8:37 pm

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.
MathWorld wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Mon Nov 12, 2007 11:48 am

Red Ed wrote: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.
MathWorld wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

#16

Postby Pat » Wed Feb 09, 2011 1:20 pm


#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

User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Pat # 203 # (225478) #

Postby Pat » Wed Mar 20, 2013 4:29 pm


#17

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

    [ play ]

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

User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

PreviousNext

Return to General