For C14n....

Everything about Sudoku that doesn't fit in one of the other sections

For C14n....

Postby Papy » Thu Sep 28, 2006 11:45 am

And how do you canonized?
What is the method to detect isomorphs?
Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Re: For C14n....

Postby udosuk » Thu Sep 28, 2006 12:17 pm

Papy wrote: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!:D
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ab » Thu Sep 28, 2006 12:34 pm

I think this is what you're after Papy:
http://forum.enjoysudoku.com/viewtopic.php?t=3054&start=0
ab
 
Posts: 451
Joined: 06 September 2005

No..

Postby Papy » Thu Sep 28, 2006 3:30 pm

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

Papy:D:D:D:D
Papy
 
Posts: 131
Joined: 15 August 2006

Isomorph

Postby Papy » Thu Sep 28, 2006 3:50 pm

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
Papy
 
Posts: 131
Joined: 15 August 2006

Re: Isomorph

Postby gsf » Thu Sep 28, 2006 4:55 pm

Papy wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

C14n

Postby Papy » Thu Sep 28, 2006 5:51 pm

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
Papy
 
Posts: 131
Joined: 15 August 2006

Re: C14n

Postby gsf » Thu Sep 28, 2006 7:23 pm

Papy wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Canon

Postby Papy » Fri Sep 29, 2006 6:48 am

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
Papy
 
Posts: 131
Joined: 15 August 2006

Re: Canon

Postby ravel » Fri Sep 29, 2006 7:53 am

Papy wrote: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.
ravel
 
Posts: 998
Joined: 21 February 2006

Thanks

Postby Papy » Fri Sep 29, 2006 9:20 am

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
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Fri Sep 29, 2006 9:43 am

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Canon

Postby gsf » Fri Sep 29, 2006 11:53 am

ravel wrote:
Papy wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Fri Sep 29, 2006 11:59 am

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:D

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Papy » Fri Sep 29, 2006 5:59 pm

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
Papy
 
Posts: 131
Joined: 15 August 2006

Next

Return to General