The New Sudoku Players' Forum

[Papy]

And how do you canonized?
What is the method to detect isomorphs?
Papy

[udosuk]

And how do you canonized?

According to this, to get canonized you have to devote yourself into religion and do a lot of good charitable deeds. And hopefully after you die some miracles will happen. Considering this: even Mother (Blessed) Teresa hasn't been canonized. So good luck on your quest to become St. Papy one day!

[ab]

I think this is what you're after Papy:
http://forum.enjoysudoku.com/viewtopic.php?t=3054&start=0

[Papy]

I can become Mother Theresa : I'm God!!!

Papy

[Papy]

I'm looking a mlethod to add (If I found a grid) my probleme to the Gordon file.
How can I be sure thet my sudoku is not in the original set?
Papy

[gsf]

I'm looking a mlethod to add (If I found a grid) my probleme to the Gordon file.
How can I be sure thet my sudoku is not in the original set?

roll your own algorithm/program
or look for a sudoku solver that can canonicalize
mine does
in unix-ese:

Code: Select all

# canonicalize gordon's 17's (once)
sudoku -qFN -f%#0c sudoku17.dat > sudoku17.can
# canonicalize the candidate puzzle
sudoku -qFN -f%#0c papynew17.dat > papynew17.can
# see if the new one is in the catalog
fgrep -f papynew17.can sudoku17.can
# repeat the last two steps for each new candidate


note that canonicalized forms may be algorithm/program specific
even though different canonicalization algorithms/programs must produce mathematically equivalent results
comparisons should only be done on data produced by the same algorithm/program

[Papy]

Well,

I progress . Thanks
The iimportant point is that you can detect isomorph if you always ude the same software you canonicalize : There is not a standard!

To add a grius I have to solve it, canonicalize it and solve the 36000 Gordon Grids canonicalize and compare?
It's exact?

But how can I be sure that my software make good canonicalize and don't forget isomomorph?

For example I canonized the Gordon file and I found only 10000 grids. Where is the mistake: I apply te same algo at each grids and I found txins! If I take a ggrid maake isomorphs I always findthe original so my algo seems to be good.
1 grid give 50 000 isom. and I found back One grid.
How many times tus necessary to add a grid at the gordon file?

How can I detect if my method is more efficace or buged?
I don't understood.

PAPY

[gsf]

How can I detect if my method is more efficace or buged?
I don't understood.

to debug your algorithm/implementation start with data from a trusted source
gordon's 17 collection is a good start
it contains 36628 mutually non-isomorphic puzzles
(all of the puzzles are mathematically distinct)
this property has been verified by at least two different methods
one by gordon using brendan mckay's nauty
the other using my solver
I believe a few others on the forum may have implemented canonicalization too

if your algorithm produces a result other than "all 36628 of gordon's 17's are different"
then you have a bug
but that's not a sufficient test
you should also test the canonicalization algorithm against valid sudoku
permutations of one puzzle and verify that all permutations are the same

also note that canonicalization based on counting or other properties other
than the valid sudoku permutations is doomed to failure -- there will always
be some puzzle that will foil a counting/property scheme

[Papy]

Hi gsf

Happy to see you again I was thinking that one of my message bless you...


I have progreeed and I think that I found two methods to c14n(wikipedia)
I do what you said and the result us strange: all the morph taht i makes ar(e detected but I always have the same (10000) resut for the Gordon!!!

Perhaps my morphs are particular: have you ou do you know a soft to generate a file with a lmot of iso?
I'm going to extract of the gordon fi:les grids that I found equal
Perhaps I can find the problem.

To c14n a grid is it necessary to solve it or no?

Papy

[ravel]

To c14n a grid is it necessary to solve it or no?

No.
[edit:]Maybe this is wrong, because i dont know a c14n canonicalization for sudokus (which are no xml documents), if there is one, please send a link. One method to normalize sudokus can be to solve it, normalize the solution grid and look where the original givens are then. But you also can normalize it without solving (e.g. using nauty), which leads to another normalized form.

[Papy]

I found my bug with the gordon files:
Now I can search new 17 clues for it!

Is someone interrested if I write a 'nauty'? (perhaps on line?)

Papy

[coloin]

Im glad your are seeing the light Papy !

What about morphing all of Gordon's [all different !] 17s to this isomorph pattern of 7 clues [+10]

Code: Select all

+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.6.|...|
|...|...|...|
+---+---+---+
|..5|...|...|
|...|...|.7.|
|...|...|...|
+---+---+---+

and/or

+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.6.|...|
|...|...|.7.|
+---+---+---+
|..5|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

This tend to be a very common partial "rook" pattern in Gordons series of 17s [if you disregard the clue label]

C

[gsf]

To c14n a grid is it necessary to solve it or no?

No.
[edit:]Maybe this is wrong, because i dont know a c14n canonicalization for sudokus

c14n is a contractualization like i18n==internationalization and l10n==localization
although this is the first time I've seen c14n
the programmer's forum thread url'd above has a good discussion on canonicalization
including some details on the alogorthm I used based on ideas used by the 9x9 sudoku counting

[tarek]

I've programmed my solver to canonicise puzzles according to the methods you described gsf.........

very effective........puzzle generation would go in circles without it

tarek

[Papy]

he programmer's forum thread url'd above has a good discussion on canonicalization

Where is the link????

I introduce C14n because le entire word is gard for me:
I don't see enaight and and ot have to n
I know you can find this funny (no mater for me) but it"s the true
I begin to generate 17 clues but my generator is slow: 20 by hour
I thgink that I ask you to control them before add to GORDPN

The challenge is creazy but I have imagined to add 3400 grids to the gordon file It's a little more than 10%

Papy