Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Mathematical equivalence

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Wed Oct 26, 2005 7:28 pm    Post subject: Mathematical equivalence Reply with quote

Reading this:

http://www.csse.uwa.edu.au/~gordon/sudokumin.php

What's the best way to ensure/generate puzzles that are not mathematically equivalent? Does anybody have a good list of non-equivalent puzzles? I'm looking for a few thousand ideally, or at least a good method of generating them. Does anybody have any experiences of this?

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Oct 26, 2005 8:07 pm    Post subject: Reply with quote

Considering the set of possible puzzles is so large, I'm not sure you can prevent mathematical equivalence; but I'm also sure most generators would never be in any danger of creating equivalent puzzles, either, even in very long runs.

Even though every asymmetrical puzzle should have 8x9! equivalent forms (symmetrical puzzles have 4x9!, 2x9!, or 9! depending on the type of symmetry), the odds of actually generating two like puzzles are astronomical because there are many many times more puzzles than solution grids. The number of minimal puzzles per grid (which likely varies by grid) is unknown, but is probably some fraction (at a guess, maybe 1-5%?) of a number between C81,17 and C81,27, likely about the latter. This is a very very large number, so even if a very small percentage of the possible sets of givens yields minimal puzzles, you'll still have a very very large number of puzzles per solution. I don't believe it's possible for two puzzles with the same solution grid to be equivalent, so again there's no additional worry there.
Back to top
View user's profile Send private message
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Wed Oct 26, 2005 8:53 pm    Post subject: Reply with quote

Out of interest, what method do you use to generate completed grids? I use a templating method, by picking one template at random and working through the rest for each number until I find a working combination, which gives a valid puzzle.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Oct 26, 2005 9:06 pm    Post subject: Reply with quote

Gaby,

The following procedure may help you in determining whether 2 sudokus are 'probably' equivalent:

1. For each of the 729 candidates (each cell-digit combination), count the number of times it is prevented, either by a peer that contains the digit, or because the cell contains another digit. Each of the 729 counters can be 0-4 after you performed this test.

2. Take, per digit, the sum of all effective eliminations (the number of counters > 0), and, also per digit, the sum of all redundant eliminations (count-1, where count > 1)

3. Sort the digits by a) effective eliminations and b) redundant eliminations.

4. 2 equivalent sudokus should produce the same result. For easy comparison, put all the numbers in a long string and calculate a SHA1 checksum for it.

It could be that non-equivalent puzzles produce the same checksum, but I haven't seen it yet. You could decide to try and permutate to find out if 2 puzzles are indeed equivalent if they have the same checksum, if you want to be 100% sure.

To test the algorithm, use a completed grid. it should have 72 effective eliminations and 180 redundant eliminations per digit.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Oct 28, 2005 6:07 pm    Post subject: Reply with quote

> Reading this:
>
> http://www.csse.uwa.edu.au/~gordon/sudokumin.php
>
> What's the best way to ensure/generate puzzles that are not
> mathematically equivalent? Does anybody have a good list of
> non-equivalent puzzles? I'm looking for a few thousand
> ideally, or at least a good method of generating them. Does
> anybody have any experiences of this?
>
> Gaby

I first compute the six 416-numbers of the 6 bands.
(using Kjell's program, just uploaded to
http://magictour.free.fr/index416.exe)
This is very fast. When they don't coincide the grids
are not equivalent. When they do coincide, there is a
real chance they are isomorphic, 90% or such.
I convert the sudoku into a 117*117-graph, and use "Nauty"
(by Brendan McKay) to find a canonical form.
The sudokus are isomorphic iff their canonical forms
coincide. This method always works but it is slower
and requires much HD, I don't use it for more than
100000 sudokus.
You could always compute more invariants like cycles
etc. this will very likely distinguish non-isomorphic
puzzles but you can't be sure. No suitable set of invariants
has been proven to distinguish all non-equivalent
9*9 sudokus AFAIK.

OK, I just did it with 1e6 random sudokugrids, took
some minutes, not fully automized.
There were 116 pairs with coinciding 416-numbers,
the 116 graphs were easy to handle now and
there were 107 pairs of equivalent grids, so 9 pairs
were not equivalent although their 416-numbers did coincide.
Statistically we'd expected 1e6*1e6/2/5.5e9 = 91 such pairs.


> Considering the set of possible puzzles is so large, I'm not
> sure you can prevent mathematical equivalence; but I'm also
> sure most generators would never be in any danger of creating
> equivalent puzzles, either, even in very long runs.
>
> Even though every asymmetrical puzzle should have 8x9!
> equivalent forms (symmetrical puzzles have 4x9!, 2x9!, or 9!
> depending on the type of symmetry), the odds of actually
> generating two like puzzles are astronomical because there are
> many many times more puzzles than solution grids. The number
> of minimal puzzles per grid (which likely varies by grid) is
> unknown, but is probably some fraction (at a guess, maybe
> 1-5%?) of a number between C81,17 and C81,27, likely about the
> latter. This is a very very large number, so even if a very
> small percentage of the possible sets of givens yields minimal
> puzzles, you'll still have a very very large number of puzzles
> per solution. I don't believe it's possible for two puzzles
> with the same solution grid to be equivalent, so again there's
> no additional worry there.

6.7e21 sudokugrids from 5.5e9 equivalence classes,
most with 6^8*2*9! members. 1e47 estimated sudokus 1e37 of which
are minimal, 1e25 classes of minimal sudokus.
Probability that some sudokus are equivalent in a truly random
database of a million minimal sudokus is smaller 1e-13




> Out of interest, what method do you use to generate completed

often I just take my database of 306693 "G-classes" and generate
one member from each by permuting minicolumns. This is very fast
and ensures one grid from each G-class.
It doesn't generate each grid with same probability,though.
I could weight the 306693 members so to get each grid
with (approximately) same probability- haven't yet done this.
Or I could generate one sudoku from each of the 5e9 equivalence
classes and store them on a big HD, that takes days and is
a bit complicated. I'm not aware that anyone has already
done it.

> grids? I use a templating method, by picking one template at
> random and working through the rest for each number until I
> find a working combination, which gives a valid puzzle.

yes, (template = 1-rookery ? , template not in your list of terms !)
how fast is it ?

another idea is to
Back to top
View user's profile Send private message Send e-mail Visit poster's website
gaby

Joined: 02 Jul 2005
Posts: 120
:

Items
PostPosted: Fri Oct 28, 2005 10:20 pm    Post subject: Reply with quote

Quote:
I first compute the six 416-numbers of the 6 bands. (using Kjell's program, just uploaded to http://magictour.free.fr/index416.exe)


I've not heard of this program. How does one go about naming a 416 number? Surely they can only be relative to each other? What is the reference point for these numbers? I'm not totally sure I grasp the concept here...

I have added some terms to the database:

http://vanhegan.net/sudoku/dictionary.php?letter=c#canonical
http://vanhegan.net/sudoku/dictionary.php?letter=e#equivalence%20class
http://vanhegan.net/sudoku/dictionary.php?letter=s#strangely%20familiar
http://vanhegan.net/sudoku/dictionary.php?letter=f#four%20one%20six
http://vanhegan.net/sudoku/dictionary.php?letter=t#template

Do these make sense? Have I completely missed any understanding here?

Also, I have no idea what the 'gang of 44' means, or is related to. Can you fill me in on this?

Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Oct 29, 2005 1:13 am    Post subject: Reply with quote

http://www.shef.ac.uk/~pm1afj/sudoku/ed44.html
http://www.shef.ac.uk/~pm1afj/sudoku/sudoku.pdf
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron