The New Sudoku Players' Forum

[RichardGoodrich]

For BigSdk my 4-grid Sudoku software I am trying to develop a "canon.py" Python module to create a "minimal lexographics" canonical Sudoku string based on the Python package:

pynauty.py

As my first trial string I am using the one below.

Here is the 81-char string for Arto Inkala's "hardest sudoku puzzle"

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..

Here is the 81-char string solved for same puzzle:

812753649943682175675491283154237896369845721287169534521974368438526917796318452

I have just emailed both Gordon Royle and the "pynauty" author/maintainer: Peter Dobsan

Does anyone already have such a canonical string? And if so how did you create it?

Thanks and Blessings,

[eleven]

Hi Richard,
strange post for me.
What you call a '"minimal lexographics" canonical Sudoku string' is just a puzzle for us, given in string form. That's how we post puzzles, so that they easily can be copied into a solver.
Copying from or to another presentation does not need a python library (but it could do the job for you for a 2-dim array), as well as solving puzzles e.g. with backtracking.
Or are you searching for such a string presentation for 4-grid Sudokus ?

[RichardGoodrich]

eleven,

Well aware that minlex is NOT needed just to post or solve a sudoku puzzle. It is something I want in my program. It is a "many to one" mapping issue. There is much talk on this forum about MinLex form. The idea is that many puzzles are "essentially the same" And this can be done on the unsolved puzzle or the solved one. I prefer doing it at this time on the solved one. Just something I want to do!

[Leren]

I haven't written any code for minlexing vanilla Sudoku puzzles but for the solutions it should be dead easy.

The first 9 digits of the solved puzzle are 812753649 and in row based minlex form they must be 123456789. So you have a re-labelling table 8 > 1, 1 > 2 etc. Apply this to the whole solution string and you are done.

This seems to be all you want at this stage, so I could stop here. Nevertheless, for your info, finding the minlex form of the puzzle is a lot more complicated, because you have to generate all possible 3,359,232 non relabelling morphs of the puzzle (the tedious bit), and re-label each morph in minlex order (the easy bit that I've done below).

For example, to change the given puzzle digits to minlex order you have

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....7..

but this won't be the minlex form of the puzzle overall, because you will be able to find morphs of the puzzle that lead to smaller digits than the one shown. eg just reverse the puzzle string, which will be a morph, and the first 3 digits will be ..1

Leren

<edit> I can see below that my manual minlex relabelling of the digits contained an error at the end. The last 7 should have been an 8.

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....7..

The correct relabelling should be

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....8..

[m_b_metcalf]

... re-label each morph in minlex order (the easy bit that I've done below).

For example, to change the given puzzle digits to minlex order you have

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....7..

Leren,

I think that's not quite right. The 2 versions above are not morphs of one another:

Code: Select all

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..   ED=10.7/10.7/ 9.7
1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....7..   ED=10.5/ 1.2/ 1.2

as shown here. The two minlex versions are

Code: Select all

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

which differ in one digit.

For the record, I wrote my own minlex program (in Modern Fortran) based on a previous program I'd written to find symmetries in puzzles in the hardest-puzzles thread, a project associated with the late-lamented Puzzles Game. Because of its origins, my program isn't very fast, but a major speed-up comes from noting that any given newly tested morph must have at least as many leading zeros (empty cells) as the current best.

HTH

Mike


P.S. The minlex versions of the 2 solution grids, after correction, are:

Code: Select all

123456789457189236698723415285914367761532948934867152346278591579641823812395674
123456789457189236869732145278913654635824971914567823392675418541298367786341592

[1to9only]

Code: Select all

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
........................................8.....................................7.. <- 4 maps to 2 numbers

1..........23......4..5.6...7...4.......874.....9...2...9....31..17...9..5....8.. <- correct


[RichardGoodrich]

I have not been on the forum in a long time. I am a
retired R&D electronics engineer (born Nov 1952) I
program in Python and do Sudoku to keep my brain alive!

First, Thanks so much for all the answers! Obviously not all of you agree. Most of us engineers have good "bullshit" filters. So I have to decide who to
listen to. I have done a bit of homework. I was on the forum once but it was years ago.

As of this reply, I have heard from:
eleven
Leren
1to9only looked at my video!
m_b_metcalf

I am friends with Gordon Fick who keeps up with Sudoku people and the forum much more than I do. So,
having just recently returned I am very "rusty" on the forum "how to" and and who may still be active there.
I have some idea of the credibility of Gordon Royle and some of his colleagues. (Why did he never
give us a procedure to use nauty!)

So I want to refer to this post from 2006:

gfroyle on forum
post19848.html#p19848
2006 Jan Tue 31, 2006 6:54 am response to Wolfgang

Perhaps m_b_metcalf gave me the most thoughtful response but REALLY appreciate 1to9only looking at
my YouTube and it appears source code!

Of course it would be helpful to know your backgrounds and expertise. SO, on "canonical.py" I got that maybe
10 years ago from a very bright German fellows named Moritz Lentz. I have not been back in contact since.
There is now a Moritz Baer-Lentz out there as a venture capitalist. Is it the same guy? Will he respond to me?

All of you have helped in one way or another! Seems many of our graph theory experts live in Australia. I
have emails into Gordon Royle, Peter Dobsan (author of pynaughty.py) and I think the creator of pynaughty-nice.
No responses yet.

This is getting long ... want to say more about Gordon Royle's post from 2006 ... maybe on another post!

[RichardGoodrich]

More from Big (AKA RichardGoodrich) ...

More thoughts on the minlex canonical form and reference again to following post in 2006.

gfroyle on forum
post19848.html#p19848
2006 Jan Tue 31, 2006 6:54 am response to Wolfgang

All who responded to my post thanks for helping me with the "obvious" I got hung up on just using pynaughty.py

I also read some threads in which gsf (Glen S. Fowler) was a participant. Have not heard about him in a while! He is
certainly a very smart guy. So one thing that has become obvious to me now. There is a HUGE difference between
minlex on just the "givens" (puzzle with holes!) vs a solved puzzle (time to calculate mostly). And those will NOT look
the same. The one "with holes" will take a lot less time. That firstrow being 1 to 9 makes sense - duh! I also saw a thread
involving gsf with Block 1 having a 'standard' numbering (trying to find a better term?) So, I think I will work on the
'puzzle with holes' first. But, would like to see some discussion about the 'wisdom' and trade-offs of doing it one way or another.

Now because of 1to9only, I want to spend more time trying to get canonical.py (from Moritz Lentz?) to work. And
of course trying to contact him!

Thanks to All

[1to9only]

I want to spend more time trying to get canonical.py (from Moritz Lentz?) to work.

I got canonical.py to run by:
- fixing 'next_map = 1'
- there are sone indenting issues in canonical_form()
- remove the last 3 lines (about 'main')
Running the python program gives the minlex form of the hardcoded puzzle (in variable 'in_')

And of course trying to contact him!

Code: Select all

http://sudokugarden.de/
http://perlgeek.de/


[Leren]

I think what I said in my post about minlexing solutions is not correct.

I think the correct answer is that you still have to generate all 3,359,232 non relabelling morphs of the puzzle and then relabel whatever digits turn up in Row 1 to 123456789. So the only "easy" bit for solutions is the relabelling table.

For puzzles the relabelling is done "on the fly" for each case, but there is a shortcut here. When you generate your non relabelling morphs you can ignore all relabellings except those that have the first clue in the right hand most position.

There will probably be more than one such case but you can than look at the second clue and only relabel the ones that have the 2nd clue in the right hand most position, and so on if there are more than one of these cases.

So for solution minlexing the easy bit is that there is only one re-labelling table. For puzzles whilst there is more than one relabelling table you don't have to do them all.

One other issue is that when you have determined your minlexed solution, you will proabably want to apply all it's morhing operations to the puzzle.

The clues will move about and change value but they will solve to the minlexed solution, but the modified puzzle will in general not be in minlexed format.

Leren

[RichardGoodrich]

I want to spend more time trying to get canonical.py (from Moritz Lentz?) to work.

I got canonical.py to run by:
- fixing 'next_map = 1'
- there are sone indenting issues in canonical_form()
- remove the last 3 lines (about 'main')
Running the python program gives the minlex form of the hardcoded puzzle (in variable 'in_')

And of course trying to contact him!

Code: Select all

http://sudokugarden.de/
http://perlgeek.de/


Thanks so much! I have not taken a serious run at this code. I just found it in some old stuff and just recently added it to my project. I think it was from a Moritz Lenz who used to run "Sudoku Garden" not the same guy as the venture capitalist Moritz Baer-Lentz me thinks! Tell me more about your background if you will?

Leren you too. Blessings, Big

[RichardGoodrich]

[quote="1to9only"][quote="RichardGoodrich"]
I got canonical.py to run by:
....
Running the python program gives the minlex form of the hardcoded puzzle (in variable 'in_')


1to9only Got it to run and I put the two versions of Arto Inkala's puzzle in there. The one "with holes" and the solved one. Here is what I got:

Code: Select all

in_ = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'
         000000000001200000030040500060003000000076300000800010008000020000600080040000700

in_ = '812753649943682175675491283154237896369845721287169534521974368438526917796318452'
         012345678875602134634781205147253086568074321203168457421837560750426813386510742


I have an email into Mortiz Lenz of Sudoku Garden who I think sent me this code some years back...

[RichardGoodrich]

The confusing thing to me is the "fully loaded puzzle" returned a "0" as the first char in its minlex result?

Comments? - Please!

[RichardGoodrich]

1to9only Got it to run and I put the two versions of Arto Inkala's puzzle in there. The one "with holes" and the solved one. Here is what I got:

Code: Select all

in_ = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'
         000000000001200000030040500060003000000076300000800010008000020000600080040000700

in_ = '812753649943682175675491283154237896369845721287169534521974368438526917796318452'
         012345678875602134634781205147253086568074321203168457421837560750426813386510742


OK, Now I know! 1to9only told me about a correction he made and I thought I had fixed it but had not! After fixing it, I got the following for the solved puzzle string:

Code: Select all

123456789457189236698723415285914367761532948934867152346278591579641823812395674


BTW, it did not seem to take that much longer for the solved string than it did for the one with holes in it!

[RichardGoodrich]

So let me repost the two minlex results for both cases of Arto Inkala's puzzle (givens, solved) Now that I have made the correction 1and9only gave me:

Code: Select all

000000001000002030004050600000600700006780000030009000008000500090007010120000090
123456789457189236698723415285914367761532948934867152346278591579641823812395674