|
View previous topic :: View next topic |
Author |
Message |
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Wed Oct 26, 2005 7:28 pm Post subject: Mathematical equivalence |
|
|
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 |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Wed Oct 26, 2005 8:07 pm Post subject: |
|
|
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 |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Wed Oct 26, 2005 8:53 pm Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Oct 26, 2005 9:06 pm Post subject: |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Fri Oct 28, 2005 6:07 pm Post subject: |
|
|
> 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 |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
|
Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|