The New Sudoku Players' Forum

[champagne]

OK thanks Champagne. I 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

I am not sure that this is correct. Usually getting the 12345678945 requires some column permutations and some relabeling.

[1to9only]

I believe that canonical.py (after my modifications (posted in another thread!)) is CORRECT in calculating true minlex.

Code: Select all

for i in range(1296):
    for j in range(1296):
        compare_and_update(least, data, i, j)
        compare_and_update(least, transposed, i, j)


It loops through 1296 x 1296 x 2 (the sudoku and its transpose) = 3,359,232 isomorphs.

It minlexes at a rate of about 2s per sudoku. It is slow compared to other minlexers currently floating about!

Instead of having to change the code for every sudoku to minlex, it needs a front end (main!) to accept an argument of either a single (81-chars) sudoku or a file containing sudokus.

[champagne]

I believe that canonical.py (after my modifications (posted in another thread!)) is CORRECT in calculating true minlex.
It minlexes at a rate of about 2s per sudoku. It is slow compared to other minlexers currently floating about!

Yes, very slow. I did not check, but I think that what I do is below the millisecond. The process could be summarized in the following way :

Find for each band/stack the corresponding 1-416 index
Take the smallest index as first band (defining bands or stacks as minimal)
take next lower index as second band
morph all to the minimal first band.

The code is slightly more complex due to cases where we have several bands/stacks with the same lows index.
The scan to find lows clues sudokus requires billions of canonical morphing.

[JPF]

-Edited for clarity-
Without wanting to hijack RichardGoodrich's thread, I cannot resist adding to what has been mentioned by eleven and Champagne:

Here are statistics on the set of the 5472730538 minlex (solution) grids. It turns out that in all cases, a minlex grid contains:

Code: Select all

+---+---+---+
|123|456|789|
|45.|...|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+


Furthermore, except for the grid XM given below, a minlex grid always contains two other elements: r2c5=8 and r2c6=9.

Code: Select all

+---+---+---+
|123|456|789|
|45.|.89|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+


The only minlex grid XM for which this property is not true is:

Code: Select all

+---+---+---+
|123|456|789|
|457|893|612|
|986|217|354|
+---+---+---+
|274|538|196|
|531|964|827|
|698|721|435|
+---+---+---+
|342|685|971|
|715|349|268|
|869|172|543|
+---+---+---+


Incidentally, XM = Max of the entire set of the minLex grids.

JPF

[champagne]

Without wanting to hijack RichardGoodrich's thread, I cannot resist adding to what has been mentioned by eleven and Champagne:

Furthermore, except for a single XM grid, a Minlex grid always contains two other elements: r2c5=8 and r2c6=9.

Code: Select all

+---+---+---+
|123|456|789|
|45.|.89|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+


JPF

hi JPF,

I am in trouble with this.

No problem with r4c1=2, this is trivial again.

In my list of 416 possible bands the last row is
"7893612896127345", "7893612896127354", "7893612896217354", "7893612986217354"

No doubt that if r2c3=6 then we have 456789 as start for the row 2, but I have a problem if r2c3= 7.
May be I did not catch your point in the proper way..
Or my table is not correct !!!!

[JPF]

Hi champagne,
I scanned the catalog of the 5472730538 grids some time ago. An error is always possible, but to better understand your argument, could you provide an example of a minlex grid that contradicts what I stated in my post?

JPF

[champagne]

Hi champagne,
I scanned the catalog of the 5472730538 grids some time ago. An error is always possible, but to better understand your argument, could you provide an example of a minlex grid that contradicts what I stated in my post?

JPF

I think that the answer is somehow in your post.
I remember that several of the 416 bands produce no lexical minimal solution grids. This is likely the case for the 4 last of the 416.
Thanks for the clarification.

[RichardGoodrich]

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

Leren, et al,

Here is my understanding so far on the minlex of Arto Inkala's puzzle:

Code: Select all

Jan 25, 2024  1250  Friday  BigSdk = Richard Goodrich's Python code

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

3. ........1.....2.93..6.4.8.....47......5.8.....3...9.7...47..5...2.....191........
4. ........1.....2.3...4.5.6.....6..7....678.....3...9.....8...5...9...7.1.12.....9.

5. 123456789745892316986713245258364197314279568679185432497621853532948671861537924
6. 123456789457189236698723415285914367761532948934867152346278591579641823812395674

1. Arto Inkala  given string
2. Arto Inkala  solved string

3. Arto Inkala  bad minlinx input string from BigSdk
4. Arto Inkala  minlinx     input string (concensus from this forum thread)

5. Arto Inkala  bad minlinx output string from BigSdk
6. Arto Inkala  minlinx     output string (concensus from this forum thread)


Python Code for BigSdk (specifically canoninical.py) posted Jan 22, 2024 is at:
http://forum.enjoysudoku.com/bigsdk-4-grid-sudoku-perfect-player-software-source-code-t42405.html

Refactored code: canon.py was posted today at: (missing perm.py which is 1298 lines long)
http://forum.enjoysudoku.com/latest-python-minlex-for-bigsdk-from-richardgoodrich-big-t42413.html

[RichardGoodrich]

BTW, BigSdk with a newly added MinLexCanon - Jan2024 which contains canon.py and perm.py is open to ALL here:

https://www.dropbox.com/home/root/public/Sudoku

While I do have a github account, I have not learned to use it, yet.

This code is my contribution to the Sudoku Community at large which of course includes this forum.
Do I really need to license it? If so my inclination is the 'permissive' MIT one. I should get permission from Ali Asaf (for dancing_links.py) as
basically his "Algorithm X in 30 lines" and Mortiz Lenz for his "canonical.py" My feeling is both the guys would be "happy" to make that
contribution to the Sudoku Community. I have recently tried to email Mortiz Lenz. I have corresponded to Ali Asaf by email in the
past and he was comfortable with GPL 3 and even mentioned he might be open to an MIT license. I will attempt to close those loops.

Would someone fix "canonical.py" - Please! What I know about mathematical graph theory would fit in a very small thimble!

Blessings, Big (AKA RichardGoodrich)

[Leren]

Code: Select all

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..  P   initial puzzle
8..........75....9.3....18..6...1.5...9.4.......75......2.7...4.....361.......8..  T   transposed puzzle

Hi Richard, to check what might be wrong with BigSdk, put the transposed puzzle as an input and see what turns up for 3 above.

Leren

[1to9only]

Having multiple threads about the same subject matter is confusing...

[eleven]

Richard,
if you want a program that works, you can find it for free.
You asked for many things, and got many useful answers, but you did not use them.
If you want a code by your own, do your homework.
Sorry, but at least me have better things to do.
PS: you may be old, but you seem to have the expectations of youngsters: the internet should give me all for free, and right now.

[RichardGoodrich]

Sudoku minlex canon guys,

Here are folks I been trying to reach for help with minlex and use of code (Ali Asaf, Moritz Lenz) that was sent to me in past. If you know of them or a better way to contact them let me know. Here is a list of my recent emails to them. Have Glen Fowler and/or Gordon Royle been active on the forum recently?

Code: Select all

        2024-01-26-1745   asking to use MIT license for his code
        2024-01-23-1818   moritz.lenz@gmail.com
                          https://moritzlenz.de/
        2024-01-22-1732   michael@radigan.co.uk   Michael Radigan  PyPi: pynauty-nice
                          https://www.linkedin.com/in/michael-radigan-1a0802207/?originalSubdomain=uk
        2024-01-22-1356   pdobsan@gmail.com  PyPi:  pynauty

                          gordon.royle@uwa.edu.au  gfroyle @ NSPF
                          https://research-repository.uwa.edu.au/en/persons/gordon-royle

        2021-03-24-1411   ali.assaf.mail@gmail.com
                          "Algorithm X In 30 Lines"
                          https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html


[RichardGoodrich]

Richard,
if you want a program that works, you can find it for free.
You asked for many things, and got many useful answers, but you did not use them.
If you want a code by your own, do your homework.
Sorry, but at least me have better things to do.
PS: you may be old, but you seem to have the expectations of youngsters: the internet should give me all for free, and right now.

What code are you referring to? If you mean minlex code, I have tried and so far not much luck. As to Sudoku in general I know of several and of course am writing my own in Python - I call BigSdk. Which I am also giving away to any who want it.

[m_b_metcalf]

Have Glen Fowler and/or Gordon Royle been active on the forum recently?

Not for over a decade.

Mike