The New Sudoku Players' Forum

[eleven]

Seems, that you have achieved, what you wanted.

If you still want to use nauty, you would have to do the work to write functions to convert a sudoku to a graph and back (like Gordon said in his post), i.e. define a graph with 81 nodes (representing the cells in the sudoku), edges between all nodes, where the cells are in the same box/column/row, and 'colored' by the given numbers.
You can then use nauty's functions to canonicalize or color the whole graph (= solve the sudoku).
Unfortunately Mathimagics died in December, so he can't help you anymore.
See e.g. here, how it can be done.

[1to9only]

Code: Select all

000000001000002030004050600000600700006780000030009000008000500090007010120000090
123456789457189236698723415285914367761532948934867152346278591579641823812395674


These are correct.

Interestingly, canonical.py can be modified to calculate MaxLex (MAXimal LEXicographical) sudoku grids - for solved grids the 1st row maps to 987654321.

perm_copy() changes:

Code: Select all

next_map = 1                            next_map = 9
next_map += 1                           next_map -= 1


compare_and_update() changes:

Code: Select all

next_map = 1                            next_map = 9
next_map += 1                           next_map -= 1
if map_[ a] < canon[ count]:            if map_[ a] > canon[ count]:
elif map_[ a] > canon[ count]:          elif map_[ a] < canon[ count]:


canonical_form() changes:

Code: Select all

least = [9 for _ in range(81)]          least = [0 for _ in range(81)]


MaxLex of the 2 sudoku grids that were minlex'ed:

Code: Select all

in_ = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'
980700000700800600005040000300000700002000065000060020001020004000300900000008000

in_ = '812753649943682175675491283154237896369845721287169534521974368438526917796318452'
987654321653921874412387695825196743349578162176243958764832519531469287298715436


[1to9only]

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.

I dont know if this will be useful to you:
I've seen some speed improvements in my own code when swapping STACKS and COLUMNS by:
transposing the sudoku so the columns are now rows, swapping the required bands/rows, and transposing rows back to columns.

[m_b_metcalf]

I dont know if this will be useful to you:
I've seen some speed improvements in my own code when swapping STACKS and COLUMNS by:
transposing the sudoku so the columns are now rows, swapping the required bands/rows, and transposing rows back to columns.

Yes, I do something along those lines:

in each stack and band sort the columns/rows so that the fullest are rightmost/bottom-most;

sort the stacks/bands in the same manner;

if the new top row has more clues than the leftmost column, transpose the whole puzzle.

This pre-conditiong speeds up my code by a factor of over three as it gets the zeros near the front of the puzzle string straight away. And it works for patterns as well as puzzles.

Thanks,

Mike

[coloin]

Not sure if this is in a language you can use.
But this software program doesnt have the gsf bug
minlex-routine-t39261.html