The New Sudoku Players' Forum

[kjellfp]

Red Ed (or anybody else for that matter),

It has been mentioned that you started the counting on the number of essentially different 5x2 grids. Did you get the number? I have started the counting on my own, after first confirming the numbers 49 for 3x2 and 1673187 for 4x2, but I understand 5x2 will take time. I use the same method as you, counting fixed grids for one element inside each conjugacy class of legal operations. I have no idea about when the counting can complete - the current implementation will take weeks, but there are shortcuts I have discovered but not implemented yet.

By dividing the number of grids by the number of legal operations, we get an estimated minimal limit of essentially different grids which is pretty close to the exact answer for dimensions greater than 3x2.

Code: Select all

Dim     #diff.grids  Estimated min     Rel.err.
-----------------------------------------------
2x2 T   2            0,09375           -95,3%
2x2 N   3            0,1875            -93,8%
3x2     49           11,33333333       -76,9%
4x2     1673187      1633552           -2,37%
5x2     n/a          4743929631232717  n/a
3x3 T   5472730538   5472447995        -0,00516%
3x3 N   10945437157  10944895989       -0,00494%
3x4     n/a          6,56848258e+28    n/a
3x5     n/a          2,7733e+59(*)     n/a
4x4     n/a          4,4916e+71(*)     n/a
4x5     n/a          2,7456e+138(*)    n/a
5x5     n/a          3,1560e+258(*)    n/a
 
T = Transposing included
N = No transposing included
(*) based on estimated number of grids

This should give an idea about what to expect from 5x2.

[Red Ed]

Hi,

I didn't get very far with the 5x2 essentially-different-grids problem. I boiled it down to a smallish list of conjugacy classes that needed to be checked then, feeling that the process was going to take a long time (and knowing that my program was inefficient), abandoned the job.

How quickly does your code handle the 3x3 case? My somewhat naive effort took about 40 minutes on 1.4GHz, AFAIR.

Ed.

[kjellfp]

The code I wrote last year to confirm the 3x3 case did not use Burnside's lemma, and that took me 10 hours.

The code I've written now is specially designed for 2xC. It does 4x2 in about 15 seconds. I have 3.0 GHz.

Btw, I don't use GAP. You can find the conjugacy classes for the row operations and for the column operations by hand, and then combine to find all conj.classes in general.

[Red Ed]

15 seconds? That's loads quicker than my 4x2 code which takes a couple of minutes.

You mentioned speed-ups. Just off the top of my head now, so could be talking nonsense ... when calculating the number of grids essentially-fixed by some operation g, do you save work by using the centraliser C(g) to group together grids whose top bands (or whatever) are related by transformations in C(g)?

I guess it would work something like this. If p is a set of cell positions, define H(p,g) to be the subgroup of C(g) that maps p to itself. Let v1 and v2 be a couple of different ways of assigning values to the cells at positions p; then the number of completions from v1 or v2 to a whole g-invariant grid is the same if v1 = hv2 for some h in H(p,g). In other words, you can partition the outer loop of your work --- namely assigning values to p-cells --- just like the old "gang of 416" method calculating 6.67e21.

The trick would be picking a good p-set, for which H(p,g) is large, for any given g.

[frazer]

I hope it's OK with Ed -- I've put up his list of interesting conjugacy classes for the 2x5 grids that he sent me in February on my web page (even though it is all his work!): http://www.afjarvis.staff.shef.ac.uk/sudoku/sud25gp.html just in case it is useful to you. Good luck with the count -- I'm looking forward to seeing the results!

[kjellfp]

Thanks for the list.

I already have a list by hand. As there are 35 conjugacy classes for row permutations and 36 for column permutations (or was it the opposite?), I knew about the 35*36=1260 classes. I have done the counting for most of them already, but of course the hard ones remain - those where all the cycles in the permutations have length 2. I have ideas about how to take symmetry advantages from most of them, though... I'll do more whenever I have time.

[kjellfp]

I have eventually ended up with 4743933602050718 essentially different 5x2 grids. I'll give the fix point counts of the various operations later. I think I'm right - for most of the conjugacy classes, the number of fix points times the size of the conjugacy class is not divisible by the total number of operations, but still the total sum is (as expected).