The New Sudoku Players' Forum

[RichardGoodrich]

So, this minlex canonical form thing got me to thinking - Oh No!

Code: Select all

1. 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
2. ........1.....2.93..6.4.8.....47......5.8.....3...9.7...47..5...2.....191........
3. 572398641841562793396147852269475138715283964438619275984731526627854319153926487

4. 812753649943682175675491283154237896369845721287169534521974368438526917796318452
5. 123456789745892316986713245258364197314279568679185432497621853532948671861537924
6. 1..........58......8..1.2...5...4.......795.....1...3...7....53..29...7..6....9..

1. Arto Inkala givens
2. Arto Inkala givens in minlex form based on given string
3. Arto Inkala solved based on minlex version of given string

4. Arto Inkala solved
5. Arto Inkala Solved in minlex form based on solved string
6. Arto Inkala givens in minlex form based on solved string


So I took #6 and used it as my input string; naively thinking I would get the canonicalized output back. No! It crashed. HoDoKu did NOT like it either. Evidently NOT a valid thing to do! Seems can't take a canonical output string then punch the proper "holes" in it to make it of the form of the input and expect it to work!

Comments?

[Leren]

1 2 and 3 look consistent. 5 looks superficially like a minlex form of 4 but to check it, minlex 3 and you should also get 5.

6 doesn't look like anything to me. It's not a unique solution puzzle, it's not in minlex form, and the clue positions are the same as in 1 (which is practically impossible).

When you go from 4 to 5 you juggle the 81 cell positions in 3,359,232 ES preserving different ways and then re-label them according to the relabelling table 812753649 -> 123456789 and then pick the smallest of the 3,359,232 resulting integers.

What you should get is a puzzle in non-minlex form with the clues juggled around which should solve to 5, so you have to record all the cell juggling as you go and apply the chosen case juggling and the relabelling to 1 to get a valid 6.

Here is an example of what 6 and 5 should look like, based on some SudokuX puzzles which were provided to me by Mathimagics some years ago.

The nice thing about SudokuX is that the ES preserving transformations drop from 3,359,232 to just 96, so it's a low cost process that can be done with spreadsheets.

I never bothered to develop the functionality to produce 6 but I can do all the other things. So here is the 6 and 5 SudokuX example.

......78.......6.....2........7........9........5....1........2.......45....8....: 123456789457891623869273154695714238214938567378562491536149872981627345742385916

Minlexing and solving 6 to get the equivalents of 2 and 3.

............................................1..2345...56.......1......7....8..23.: 871926345236584917954173682689217453345698721712345869568732194123469578497851236

Minlexing 3 to get 5 again :123456789457891623869273154695714238214938567378562491536149872981627345742385916. Yep, works like a treat.

Leren

[RichardGoodrich]

1 2 and 3 look consistent. 5 looks superficially like a minlex form of 4 but to check it, minlex 3 and you should also get 5.

627345742385916. Yep, works like a treat.

Leren

Well it will take me some time to process your reply as you mentioned several things that I am not familiar with. So I will at least make some attempt to do so!

[Leren]

Ask me a straight up question and I'll give you a straight up answer. Just tell me what it is that you don't understand and I'll explain it as best I can.

Code: Select all

1 2 and 3 look consistent.

Actually I've just realised that 2 is not a minlexed form of 1. How do I know that ?

........1.....2.93..6.4.8.....47......5.8.....3...9.7...47..5...2.....191........

When you have seen enough minlexed puzzles as I have it becomes second nature. The first two clues look OK. The first clue must be 1 and the second clue must be 1 or 2. The third clue must be 1, 2 or 3, not 9.

I'll try to put this clueset in clue minlex order : Reading the digits of 1 from left to right gives you the relabelling table for this puzzle : 129364875 => 123456789

Applying this to the above puzzle gives you :

........1.....2.93..6.4.8.....47......5.8.....3...9.7...47..5...2.....191........
........1.....2.34..5.6.7.....68......9.7.....4...3.8...68..9...2.....131........

PS

I think at this stage we need to stop completely and verify what the minlexed version of the original puzzle is.

from the previous thread I have

Code: Select all

in_ = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'
       000000000001200000030040500060003000000076300000800010008000020000600080040000700

but that is rubbish because in the second line there are only 8 different digits whereas in the first line there are nine different digits./

From 2 above we have a corrected version

Code: Select all

........1.....2.34..5.6.7.....68......9.7.....4...3.8...68..9...2.....131........

I also have a version from Mike Metcalf which is a lexicologically smaller

Code: Select all

........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.

Can at least 2 other people verify whether this is correct or not ? I see little point in continuing on unless this issue is resolved.

Leren

[1to9only]

Yes. #2 is not the minlex form of #1, so no need to spend too much time on the rest...

I think you're trying to obtain an isomorph (#6) of the original (#1) based on its solution (#4) in minlex form (#5).

gsf's program (either gsf.exe or sudoku.exe) will caculate the solution-minlex (#6) of a puzzle (#1) as follows:
I've added extra steps to show #1 morphed to #6:

Code: Select all

sudoku.exe -qFN -f%#mc 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. <- gives minlex
sudoku.exe -a          8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. <- gives solution
sudoku.exe -qFN -f%#mc 812753649943682175675491283154237896369845721287169534521974368438526917796318452 <- gives minlex of solution
sudoku.exe -qFN -f%#.c 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. <- gives isomorph
sudoku.exe -qFN -f%#mc 1.....7...5...9....98.....5....1.36......2..89...6.1..3...7.......6.......2..5..4 <- gives minlex of isomorph

Output:
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.
812753649943682175675491283154237896369845721287169534521974368438526917796318452 # 96796 FNBTYK S8.f
123456789457189236698723415285914367761532948934867152346278591579641823812395674
1.....7...5...9....98.....5....1.36......2..89...6.1..3...7.......6.......2..5..4
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.



[JPF]

I confirm 1to9only's results with my own programs:

Code: Select all

1. 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..  P   initial puzzle
2. ........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.  Q = Minlex(P)
3. 582376941769412835314958672251634789946781253837529164478193526695247318123865497  S = Solution(Q)


4. 812753649943682175675491283154237896369845721287169534521974368438526917796318452  T = Solution(P)
5. 123456789457189236698723415285914367761532948934867152346278591579641823812395674  U = Minlex(T) = f(T)
7. 1.....7...5...9....98.....5....1.36......2..89...6.1..3...7.......6.......2..5..4  V = f(P)



Line 7 is obtained by applying to Line 1 the same transformation that transitions from 4 to 5
Note that :

- P, Q, V are equivalent
- S = Solution(Minlex(P)) is not equal to Minlex(Solution(P)) = U

JPF

[Leren]

Code: Select all

........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.  Mike
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.  1 to 9
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.  JPF

Thanks to Mike, 1 to 9 and JPF for verifying the minlex form of the puzzle. So 2 should be that. JPF's solution, which I agree with, is this

Code: Select all

582376941769412835314958672251634789946781253837529164478193526695247318123865497

So this should be 3.

Also JPF's 5 and 7 are the correct versions of your 5 and 6.

So at this stage it's over to you Richard. How did you arrive at your 2? Did you use the public domain program you used in the previous thread, or some other method ?

Your 2 was a valid morph of the puzzle, but not the right positional case and not in Minlex form.

Code: Select all

........1.....2.34..5.6.7.....68......9.7.....4...3.8...68..9...2.....131........
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.

You got the first 3 clues in the right location, but the fourth clue in the correct case was to the right of the one in your case, so maybe bit of a tweak in your method is all that is required.

Leren

[JPF]

To go from the initial puzzle 2 to its actual minlex, here are the missing steps:

Code: Select all

initial puzzle 2 (top of the thread):
+---+---+---+
|...|...|..1|
|...|..2|.93|
|..6|.4.|8..|
+---+---+---+
|...|47.|...|
|..5|.8.|...|
|.3.|..9|.7.|
+---+---+---+
|..4|7..|5..|
|.2.|...|.19|
|1..|...|...|
+---+---+---+
........1.....2.93..6.4.8.....47......5.8.....3...9.7...47..5...2.....191........

after diagonal symmetry:
+---+---+---+
|...|...|..1|
|...|..3|.2.|
|..6|.5.|4..|
+---+---+---+
|...|4..|7..|
|..4|78.|...|
|.2.|..9|...|
+---+---+---+
|..8|...|5..|
|.9.|..7|.1.|
|13.|...|.9.|
+---+---+---+
........1.....3.2...6.5.4.....4..7....478.....2...9.....8...5...9...7.1.13.....9.

after permutation digits (2 3)(4 6):
+---+---+---+
|...|...|..1|
|...|..2|.3.|
|..4|.5.|6..|
+---+---+---+
|...|6..|7..|
|..6|78.|...|
|.3.|..9|...|
+---+---+---+
|..8|...|5..|
|.9.|..7|.1.|
|12.|...|.9.|
+---+---+---+
........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.



JPF

[eleven]

Richard, you can immediately see, that your nr. 5 is wrong.
A minlexed solution grid has to start with 12345678945.
(by the way, that puzzle is all but the hardest)

[Leren]

JPF : For the puzzles it seems that two things may be missing in Richards method. 1. Transposition about the main diagonal, and 2. Minlexing of the clues for the positional case.

eleven : For the minlex solutions I didn't know about the 45 in r2c12, so r1c4 == r2c1 and r1c5 == r2c2. Is there a proof of that somewhere ?

As far as the difficulty of the puzzle is concerned, there is a certain advanced but well known move at the start that may make it a bit easier. Still difficult but not as hard as the hardest puzzles currently known.

Leren

[RichardGoodrich]

Hey Guys,

I did NOT mean to cause all this consternation. #5 I just made up! And later I realized NO way it could be right - I was just playing around. I have not read all the response yet, but will. Sure to learn something. I am just EXCITED to produce the unique min-lex for the original given and solved puzzle.

[RichardGoodrich]

OK,

I am tired and must sleep, but I think y'all are saying at least that the minlex for the puzzle givens is not right. Be great if y'all could come to an agreement on the correct answers. I got this code from a fellow named Moritz Lenz - Sudoku Garden about 10 years ago. No way do I understand what is going on!

I'll check back tomorrow.

[champagne]

JPF : For the puzzles it seems that two things may be missing in Richards method. 1. Transposition about the main diagonal, and 2. Minlexing of the clues for the positional case.

eleven : For the minlex solutions I didn't know about the 45 in r2c12, so r1c4 == r2c1 and r1c5 == r2c2. Is there a proof of that somewhere ?

As far as the difficulty of the puzzle is concerned, there is a certain advanced but well known move at the start that may make it a bit easier. Still difficult but not as hard as the hardest puzzles currently known.

Leren

Hi Leren,

The 45 in line 2 is "nearly trivial", you can always permute stacks to get it. The list of the 416 min lexical starts for a band is well known. I add below the rest of the 416 minimal .

BTW, I use this table to produce my Canonical form of a given band, and later as basis to produce the canonical form of a solution grid.

Hidden Text: Show

"6789123789123456", "6789123789123465", "6789123789123564", "6789123789132465",
"6789123789132546", "6789123789132564", "6789123789231564", "6789123789231645",
"6789123798132465", "6789123798132546", "6789123798132564", "6789123798213564",
"6789123798213654", "6789123798231564", "6789123798231645", "6789123897231564",
"6789123897231645", "6789132789123546", "6789132789132546", "6789132789132564",
"6789132789213456", "6789132789213645", "6789132789213654", "6789132789231546",
"6789132789231564", "6789132879231564", "6789231789123645", "6789231789132546",
"6789231789231564", "6789231789312456", "6789231798213645", "7189236689237145",
"7189236689237154", "7189236689237415", "7189236689237451", "7189236689237514",
"7189236689237541", "7189236689273145", "7189236689273154", "7189236689273415",
"7189236689273451", "7189236689273514", "7189236689273541", "7189236689327145",
"7189236689327154", "7189236689327415", "7189236689327451", "7189236689327514",
"7189236689327541", "7189236689372145", "7189236689372154", "7189236689372415",
"7189236689372451", "7189236689372514", "7189236689372541", "7189236689723145",
"7189236689723154", "7189236689723415", "7189236689723514", "7189236689723541",
"7189236689732145", "7189236689732154", "7189236689732415", "7189236689732514",
"7189236689732541", "7189236698237145", "7189236698237154", "7189236698237415",
"7189236698237514", "7189236698237541", "7189236698273145", "7189236698273154",
"7189236698273415", "7189236698273514", "7189236698273541", "7189236698327145",
"7189236698327154", "7189236698327415", "7189236698327541", "7189236698372145",
"7189236698372154", "7189236698372415", "7189236698372514", "7189236698372541",
"7189236698723145", "7189236698723154", "7189236698723415", "7189236698723514",
"7189236698732145", "7189236698732154", "7189236698732415", "7189236698732514",
"7189236869237145", "7189236869237514", "7189236869273145", "7189236869273154",
"7189236869273415", "7189236869273514", "7189236869327154", "7189236869327415",
"7189236869327514", "7189236869372145", "7189236869372154", "7189236869372415",
"7189236869372514", "7189236869723145", "7189236869723154", "7189236869723514",
"7189236869732145", "7189236869732154", "7189236896237145", "7189236896237154",
"7189236896237514", "7189236896273145", "7189236896273154", "7189236896273514",
"7189236896327145", "7189236896327154", "7189236896327514", "7189236896372145",
"7189236896372154", "7189236896372514", "7189236896723154", "7189236896723514",
"7189236896732154", "7189236896732514", "7189236968237154", "7189236968237514",
"7189236968273514", "7189236968327154", "7189236968327514", "7189236968372154",
"7189236968372514", "7189236968723154", "7189236968732154", "7189236986237154",
"7189236986273154", "7189236986327154", "7189236986372154", "7189263689237145",
"7189263689237415", "7189263689237451", "7189263689237514", "7189263689273154",
"7189263689273415", "7189263689273451", "7189263689273514", "7189263689273541",
"7189263689327154", "7189263689327415", "7189263689327514", "7189263689327541",
"7189263689372145", "7189263689372154", "7189263689372415", "7189263689372451",
"7189263689372514", "7189263689723145", "7189263689723154", "7189263689723451",
"7189263689732145", "7189263689732154", "7189263689732415", "7189263689732451",
"7189263689732514", "7189263689732541", "7189263698237154", "7189263698237415",
"7189263698237451", "7189263698237514", "7189263698273145", "7189263698273415",
"7189263698273451", "7189263698273514", "7189263698327145", "7189263698327154",
"7189263698327415", "7189263698327451", "7189263698327514", "7189263698372154",
"7189263698372415", "7189263698372514", "7189263698372541", "7189263698732145",
"7189263698732154", "7189263698732451", "7189263869237154", "7189263869237415",
"7189263869237514", "7189263869273451", "7189263869327415", "7189263869327451",
"7189263869327514", "7189263869372145", "7189263869372154", "7189263869372514",
"7189263896237145", "7189263896237154", "7189263896237451", "7189263896327145",
"7189263896327154", "7189263896327415", "7189263896327451", "7189263896327514",
"7189263896327541", "7189263896372145", "7189263896372154", "7189263896372451",
"7189263968327145", "7189263968327154", "7189263968327415", "7189263968327514",
"7189263968327541", "7189263968372145", "7189263986327145", "7189263986327154",
"7189263986327451", "7189326689237451", "7189326689237514", "7189326689237541",
"7189326689273145", "7189326689273451", "7189326689273541", "7189326689327154",
"7189326689327451", "7189326689327541", "7189326689372415", "7189326689372541",
"7189326689723145", "7189326689723415", "7189326689732145", "7189326689732415",
"7189326689732514", "7189326689732541", "7189326698237145", "7189326698237541",
"7189326698273514", "7189326698273541", "7189326698732415", "7189326869372514",
"7189623689237145", "7189623689237154", "7189623689273145", "7189623689273154",
"7189623689273541", "7189623689327145", "7189623689327154", "7189623689372145",
"7189623689372154", "7189623689372514", "7189623689723145", "7189623689723154",
"7189623689723415", "7189623689723451", "7189623689723514", "7189623689723541",
"7189623689732145", "7189623689732154", "7189623689732415", "7189623689732451",
"7189623689732514", "7189623689732541", "7189623698237145", "7189623698237154",
"7189623698237541", "7189623698273145", "7189623698273154", "7189623698327145",
"7189623698327154", "7189623698327514", "7189623698372145", "7189623698372154",
"7189623698732145", "7189623698732154", "7189623698732415", "7189623698732514",
"7189623698732541", "7189623869237145", "7189623869273145", "7189623869273154",
"7189623869273451", "7189623869327154", "7189623869372145", "7189623869372154",
"7189623896237145", "7189623896237154", "7189623896237415", "7189623896237451",
"7189623896237514", "7189623896237541", "7189623896327145", "7189623896327154",
"7189623896327415", "7189623896327451", "7189623896327514", "7189623896372145",
"7189623896372154", "7189623896372451", "7189623968327145", "7189623968327154",
"7189623968327415", "7189623968372145", "7189623968372154", "7189623986327145",
"7189623986327154", "7189623986327415", "7189623986327451", "7189623986327514",
"7189623986327541", "7189632689237145", "7189632689273145", "7189632689273154",
"7189632689273514", "7189632689327154", "7189632689372145", "7189632689372154",
"7189632689723145", "7189632689723514", "7189632689732145", "7189632689732154",
"7189632689732514", "7189632689732541", "7189632698237145", "7189632698237154",
"7189632698237514", "7189632698273145", "7189632698327145", "7189632698327154",
"7189632698327541", "7189632698372154", "7189632698732145", "7189632698732514",
"7189632869273145", "7189632869372145", "7189632896237145", "7189632896237415",
"7189632896327145", "7189632896327154", "7189632896327451", "7189632896327541",
"7189632896372145", "7189632896372154", "7189632896372451", "7189632968327145",
"7189632968327154", "7189632968327451", "7189632986327145", "7289163689173452",
"7289163689713254", "7289163698137425", "7289163698137524", "7289163698317254",
"7289163698317524", "7289163698713254", "7289163869713245", "7289163869731245",
"7289163869731524", "7289163896317245", "7289163896731524", "7289613689173245",
"7289613689713245", "7289613689713254", "7289613698137254", "7289613698317245",
"7289613698317254", "7289613698713245", "7289613869713245", "7289613869731245",
"7289613869731254", "7289613896137245", "7289613896137254", "7289613896317245",
"7289613896317425", "7289613896731245", "7289613896731254", "7289613968137245",
"7289613968137254", "7289613968731245", "7289613986137245", "7289631689173245",
"7289631689713254", "7289631698317254", "7289631869713245", "7289631869713254",
"7289631869731245", "7289631869731254", "7289631896137245", "7289631896137254",
"7289631896137425", "7289631896317245", "7289631896317254", "7289631896731245",
"7289631968137254", "7289631968731245", "7289631968731254", "7289631986137245",
"7289631986137254", "7389612896127345", "7389612896127354", "7389612896172345",
"7389612896172354", "7389612896217345", "7389612896217354", "7389612896271345",
"7389612896271354", "7389612896712354", "7389612896721354", "7389612986172354",
"7389612986217354","7389621896127345", "7389621896217354"," 7389621986127354",
"7893612896127345", "7893612896127354", "7893612896217354", "7893612986217354",

[Leren]

OK thanks Champagne. I have produced many minlexed solutions for SudokuX and they also all have 45 in r2c12. I think this means that you can ignore all positional morphs in which r1c4 <> r2c1 or r1c5 <> r2c2.

Leren

<edit> Referring to Champagne's comment on the next page, perhaps I can express myself better.

I am not sure that this is correct. etc

Obviously you have to consider all 3,359,232 cases of row, column, box and transposition cell juggling, but you can skip the relabelling part of a case unless after the cell juggling r1c4 = r2c1, r1c5 = r2c2 and apparently r4c1 = r1c2. I gather that the jury is still out on the 89 in r2c456, so I'll pass on that.

In SudokuX r2c12 is always 45 but r4c1 is not always 2. That had me worried in the list I have produced, but fortunately I have some old lists from the much missed Mathimagics and r4c1 is not always 2 there either. Phew !

Leren

[Leren]

HI Richard.

There is agreement on 2, which is ........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.

You can see how to get it from your 2 using JPF's post above. It looks like the program you are using is not including cases where you transpose the clues around the top left to bottom right diagonal, but you can fix this without changing the program at all. Just input the original puzzle and the transposed puzzle and take the smallest result.

For a correct 5, you have to do this as well, but you can ignore all positional morphs in which r1c4 <> r2c1 or r1c5 <> r2c2, which will reduce the number of cases you have to further check by a factor of 30. I'm guessing this may be enough to get the right answer, which is 123456789457189236698723415285914367761532948934867152346278591579641823812395674.

Leren