gang of 44 , gang of 416

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

gang of 44 , gang of 416

Postby dukuso » Mon Jun 07, 2010 8:40 am

I think we should have an own thread about these "gangs"

these are classes of 3*9 subsudokugrids

Code: Select all
+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+


the number of ways to complete this to a full sudoku , having this as its first band
only depends on the numbers that are used in each minicolumn (=column of 3 numbers) and
not on their order in the minicolumn.

-------------------------------------------------------------------------------

see the long thread about sudoku's maths for the
"gang of the 44"

viewtopic.php?t=44&postdays=0&postorder=asc&start=225



each 3*9 chute in a sudoku is from one of the 44 classes.
Allowed operations are:
permute the symbols
permute columns 1,2,3
permute columns 4,5,6
permute columns 7,8,9
permute the 3 blocks
permute the entries in mini-column 1
permute the entries in mini-column 2
...
permute the entries in mini-column 9


this gives 6 numbers from 1..44 for the 6 chutes in a sudoku
to characterize the type of a sudoku.


you can permute the 3 entries in the 9 minicolumns in a band independently to get a new sudoku.
There are typically ~ 32 ways to do this.

-------------------------------------------------------------------------

this "gang of 44" is important when we want to count all the sudokugrids,
but our typical way to consider classes of bands would be to identify bands
that can be transformed into each other by

permuting the 3 rows
permuting the 3 minicolumns within one of the 3 blocks of 3 minicolumns
permuting the 3 blocks
permuting the symbols

this gives 416 classes of bands , the "gang of 416"
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby dukuso » Mon Jun 07, 2010 8:41 am

in a band, you either have only 3 different mini-row-sets (gangsters 1-21)
or all the 27 3-sets are different (gangsters 22-44) .

in case 1 the minimal isomorphic representative starts with

Code: Select all
123456789
456......
.........


in case 2 it starts with

Code: Select all
123456789
457......
.........



this gives a 4 bit characterization number for a sudokugrid S-class (symmetry class, 5.5e9 of them)
(how many bands have only 3 different minirows-sets ?)
how many towers have only 3 different minicolumn-sets ?)
2 sorted counts from {0,1,2,3} , 10 combinations ~ 3.32 bits
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby coloin » Mon Jun 07, 2010 7:35 pm

I believe some non-isomorphic grids share the same index416 - but these concerned grids with a band with a repeating minirow [0-30 /416 ] [~5% OF GRIDS]

With all bands above 30 in the 416 classification - maybe the signature is definitive eg [36,145,345: 67,178,378]

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: gang of 44 , gang of 416

Postby dukuso » Tue Jun 08, 2010 4:25 am

the run is finished after 7.5h with 3.2GHz .
11555445688 grids were created, 5734297654 of them had
a smaller ordered triple of 416-gangsters in bands than its transpose,
41091 had the same triple as its transpose.
10895 different ordered triples of 44-gangster-bands did occur
counts in http://magictour.free.fr/triples.44

3 numbers for the 44-gangster-indices of the bands
then occurrance count for that triple in the bands of the
~1.2e10 generated grids
then occurrance count for that triple in the towers of the
~1.2e10 generated grids

does it create a grid from each T-class ?
------edit------
no, e.g. no grid with bands 16,26,40 does occur in the list
of G-classes, but such grids do exist
-----edit again------
it does ! just 16,40,26 = #212938 so I had overlooked it
so the question whether all T-classes are created is still open
ince I don't remember what I did in July,August 2005
------------
a theoretical speed factor of 2 should be possible
by checking the bands only once per G-class
------------------------
now do the same for 416-3 tuples, the program could easily be adapted,
but it's much slower (~18days vs. ~7.5hours). This must be due to RAM-caching
(416^3/3!*4*2 bytes) since the program is almost the same.
Last edited by dukuso on Fri Jun 11, 2010 9:28 am, edited 3 times in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby dukuso » Tue Jun 08, 2010 5:21 am

make a list of all grids with same 416-sixtuple but from diffferent S-classes

make a list of all 5.5e9 S-classes sorted by their ordered 416-sixtuple


my numbering of the 44-gang an 416-gang is maybe not most canonical
we should agree on a standard numbering

lexicographically minimal for a sudoku with that gangster as first band ?
but we would also want it to be ordered such that 416-classes with same
44-class are adjacent, and classes are grouped by their properties
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby coloin » Tue Jun 08, 2010 12:28 pm

Yes Red Eds gang of 44 was different from yours.......

The thread canonical form approached some of the issues...

from there page 3
coloin wrote:Ah... Ive done it ..... 3 pairs of different grids out of 32247 had the same index416.

Code: Select all
 2  18   3  ,  24  24 259   - 123456789456789123789123465231594876594867312867231954315648297648972531972315648
 2  18   3  ,  24  24 259   - 123456789456789123789123465231867954594231876867594312315972648648315297972648531
 3  18  18  ,  24  24  71   - 123456789456789123789123564234567918567891432891234657345672891672918345918345276
 3  18  18  ,  24  24  71   - 123456789456789123789123564234891657567234918891567432345672891672918345918345276
 21 275 279  ,  25 390 331  - 123456789456789132789213456234895617597641328861327594348162975615978243972534861
 21 275 279  ,  25 390 331  - 123456789456789132789213456237568914591324867864971325375192648642837591918645273
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: gang of 44 , gang of 416

Postby dukuso » Tue Jun 08, 2010 1:10 pm

are you saying index416 is not working correctly ?

or it just uses a different enumeration of the gangsters
(not-lexminimal)

I did change Kjell's enumeration (don't remember the exact reason, maybe just historical,
it fits with an earlier enumeration)

maybe Kjell's original enumeration was lexminimal ?! shall I post the program with the original
enumeration ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby coloin » Tue Jun 08, 2010 9:12 pm

Looking through the canonical form thread - this is indeed the case [unfortunatly] see commennt from Kjellfp.

Thread was the forerunner for gsf to amass and compress the 5e9 grids

The duplicates tended to occur with 416 band 1-30. As above.

Maybe there needs to be more than 416 bands.

As I tried to work out in the thread.....

416^2 - = upper limit of essentially different B[1]2347s - which I believe must be an underestimate.

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: gang of 44 , gang of 416

Postby ronk » Tue Jun 08, 2010 11:19 pm

Would someone please provide links to where the gang of 44 and gang or 416 are enumerated? TIA
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: gang of 44 , gang of 416

Postby dukuso » Wed Jun 09, 2010 5:41 am

what is indeed the case ?
that index416 is not working correctly ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby dukuso » Wed Jun 09, 2010 5:44 am

gang of the 44
================

(1) (allowed sudoku-) 9-tupel of 3-sets for the 3 entries in the 9 columns
123456789123456789123456789 = ({1,2,3},{4,5,6},...)

147147147
258258258 satisfies this
369369369

(2) lfd.nr
(3) number of compatible 3*9 sudokus (sudoku-grids)
equivalence classes ? no *9! ? no , must be divible by 3!
(4) number of classes of compatible 3*9-sudokus (from the gang of 416)
(5) number of 9-tupels from T in the class
what's T ?
(6) (5)/1680/36
(7) number of sudokus with a band from (4) as upper band / 9!/6^4/2^7
--------------------------------------------------
123456789123456789123456789,1,1728,2,60480,1,13546872
123456789123456789123457689,2,576,3,4898880,81,346083192
123456789123456789124357689,3,192,3,29393280,486,668815056
123456789123456789124378569,4,192,2,9797760,162,225521136
123456789123456789147258369,5,96,2,6531840,108,72962040
123456789123457689123458679,6,576,4,6531840,108,455091264
123456789123457689123468579,7,864,7,6531840,108,688823352
123456789123457689124356789,8,192,6,58786560,972,1334816064
123456789123457689124358679,9,192,8,117573120,1944,2639418048
123456789123457689124367589,10,192,6,58786560,972,1322892864
123456789123457689124368579,11,288,24,235146240,3888,7997419008
123456789123457689124389567,12,192,6,58786560,972,1333594368
123456789123457689126345789,13,192,3,29393280,486,671794992
123456789123457689126347589,14,192,8,117573120,1944,2665795968
123456789123457689126348579,15,288,16,117573120,1944,3983962320
123456789123457689145267389,16,96,1,29393280,486,330914376
123456789123457689145268379,17,144,8,117573120,1944,1987093296
123456789123457689146258379,18,168,14,235146240,3888,4596811128
123456789123457689148259367,19,144,3,58786560,972,975856572
123456789124357689125348679,20,192,5,39191040,648,871266816
123456789124357689125367489,21,144,4,58786560,972,989360244
123456789124357689125368479,22,168,9,117573120,1944,2299821930
123456789124357689125378469,23,264,13,117573120,1944,3652048026
123456789124357689126358479,24,144,8,117573120,1944,1973476872
123456789124357689126378459,25,168,14,235146240,3888,4626249012
123456789124357689126389457,26,144,4,58786560,972,997250292
123456789124357689128345679,27,192,10,117573120,1944,2649236544
123456789124357689128356479,28,168,9,117573120,1944,2318867082
123456789124357689128359467,29,120,4,78382080,1296,1095439500
123456789124357689134258679,30,192,5,39191040,648,869683680
123456789124357689134268579,31,288,28,235146240,3888,7900690752
123456789124357689135268479,32,228,22,235146240,3888,6250718781
123456789124357689135278469,33,276,26,235146240,3888,7604258643
123456789124357689136258479,34,168,9,117573120,1944,2284590420
123456789124357689136278459,35,180,30,470292480,7776,9833024970
123456789124357689137268459,36,216,20,235146240,3888,5918022972
123456789124357689138259467,37,156,26,470292480,7776,8466321474
123456789124357689138269457,38,228,11,78382080,1296,2085113295
123456789124357689158267349,39,120,6,117573120,1944,1613192490
123456789124378569129356478,40,96,2,3265920,54,37222080
123456789124378569135279468,41,192,8,78382080,1296,1758335904
123456789124378569137245689,42,516,9,26127360,432,1595569911
123456789124378569157268349,43,168,6,39191040,648,756792918
123456789147258369159267348,44,120,2,4354560,72,59305360
-------------------------------------------------
sum:11352,416,4741632000,78400,110817071884

60713 out of the 85184=44^3 combinations of 3 gang44-members
can be joined to form a valid 9*9 sudoku.


==========================================================================

the 416 equivalence classes of 3*9 sudokugrid-bands


3 rows, index from the 44-gang , I don't remember what the 3rd column stands for
other than in the 44gang above here we list 3 rows and not 9 columns
----------------------------------------
123456789456789123789123456, 1 , 72
123456789456789123789123465, 2 , 1944
123456789456789123789123645, 4 , 1296
123456789456789123789132465, 7 , 648
123456789456789123789132564, 11 , 7776
123456789456789123789213465, 8 , 3888
123456789456789123789231564, 41 , 1296
123456789456789123789231645, 42 , 432
123456789456789123798132546, 15 , 3888
123456789456789123798132564, 15 , 3888
123456789456789123798213564, 32 , 3888
123456789456789123798213654, 38 , 1296
123456789456789123798231564, 34 , 3888
123456789456789123798312564, 33 , 3888
123456789456789123879213546, 7 , 648
123456789456789123897231564, 44 , 144
123456789456789123897231645, 41 , 1296
123456789456789132789123546, 3 , 3888
123456789456789132789132654, 8 , 3888
123456789456789132789213654, 17 , 3888
123456789456789132789231456, 13 , 3888
123456789456789132789231564, 33 , 3888
123456789456789132789321564, 18 , 7776
123456789456789132798213456, 11 , 7776
123456789456789132798231546, 28 , 7776
123456789456789132879231564, 32 , 3888
123456789456789231789123645, 5 , 432
123456789456789231789132546, 17 , 3888
123456789456789231789231564, 42 , 432
123456789456789231789312456, 40 , 432
123456789456789231798312654, 38 , 1296
123456789457189236689237514, 33 , 3888
123456789457189236689273541, 31 , 7776
123456789457189236689327154, 15 , 3888
123456789457189236689327514, 11 , 7776
123456789457189236689327541, 11 , 7776
123456789457189236689372451, 22 , 3888
123456789457189236689372514, 31 , 3888
123456789457189236689723154, 11 , 7776
123456789457189236689723415, 18 , 7776
123456789457189236689723451, 11 , 7776
123456789457189236689732514, 32 , 7776
123456789457189236689732541, 32 , 7776
123456789457189236698237145, 28 , 7776
123456789457189236698237415, 28 , 7776
123456789457189236698273145, 38 , 3888
123456789457189236698273415, 38 , 7776
123456789457189236698273541, 33 , 3888
123456789457189236698327145, 32 , 7776
123456789457189236698372145, 31 , 7776
123456789457189236698372541, 42 , 3888
123456789457189236869237415, 33 , 7776
123456789457189236869327514, 27 , 3888
123456789457189236869372415, 30 , 1296
123456789457189236869732145, 31 , 7776
123456789457189236869732451, 18 , 7776
123456789457189236869732541, 32 , 7776
123456789457189236896237145, 33 , 7776
123456789457189236896237415, 33 , 7776
123456789457189236896237514, 36 , 7776
123456789457189236896372145, 30 , 3888
123456789457189236896372154, 37 , 7776
123456789457189236896723451, 41 , 3888
123456789457189236896723514, 28 , 3888
123456789457189236896732415, 31 , 7776
123456789457189236968237154, 15 , 7776
123456789457189236968273145, 38 , 7776
123456789457189236968327154, 32 , 7776
123456789457189236968327514, 23 , 7776
123456789457189236968372514, 42 , 1296
123456789457189236968732154, 11 , 7776
123456789457189236968732541, 23 , 7776
123456789457189236986237514, 33 , 7776
123456789457189236986273541, 31 , 7776
123456789457189236986327154, 15 , 7776
123456789457189236986327415, 18 , 7776
123456789457189236986327451, 15 , 7776
123456789457189236986372154, 22 , 3888
123456789457189236986372451, 22 , 7776
123456789457189236986372514, 31 , 7776
123456789457189263689237145, 33 , 7776
123456789457189263689237514, 41 , 7776
123456789457189263689273154, 26 , 3888
123456789457189263689273415, 25 , 7776
123456789457189263689273451, 26 , 7776
123456789457189263689273514, 27 , 7776
123456789457189263689723415, 17 , 7776
123456789457189263689732514, 35 , 7776
123456789457189263698327415, 34 , 7776
123456789457189263698372154, 35 , 7776
123456789457189263698723451, 35 , 7776
123456789457189263698732154, 35 , 7776
123456789457189263698732415, 33 , 7776
123456789457189263698732541, 35 , 7776
123456789457189263869273145, 22 , 7776
123456789457189263869273451, 28 , 3888
123456789457189263869273514, 28 , 7776
123456789457189263869327514, 23 , 7776
123456789457189263869372415, 37 , 7776
123456789457189263869372451, 32 , 3888
123456789457189263869723415, 25 , 7776
123456789457189263869732145, 36 , 7776
123456789457189263869732451, 36 , 7776
123456789457189263896372145, 34 , 7776
123456789457189263896723541, 28 , 3888
123456789457189263896732154, 37 , 7776
123456789457189263896732451, 37 , 7776
123456789457189263968237514, 37 , 7776
123456789457189263968237541, 37 , 7776
123456789457189263968273154, 33 , 7776
123456789457189263968273415, 37 , 7776
123456789457189263968273451, 33 , 3888
123456789457189263968327145, 39 , 7776
123456789457189263968327514, 20 , 7776
123456789457189263968372145, 43 , 3888
123456789457189263968372451, 31 , 7776
123456789457189263968723451, 31 , 7776
123456789457189263968723514, 22 , 7776
123456789457189263968732451, 33 , 7776
123456789457189263986237514, 35 , 7776
123456789457189263986327514, 9 , 7776
123456789457189263986372451, 20 , 3888
123456789457189263986372541, 30 , 7776
123456789457189263986723514, 15 , 3888
123456789457189263986732154, 22 , 7776
123456789457189263986732541, 34 , 7776
123456789457189326689237154, 11 , 7776
123456789457189326689237451, 11 , 7776
123456789457189326689273154, 11 , 7776
123456789457189326689273451, 11 , 7776
123456789457189326689273514, 42 , 7776
123456789457189326689327154, 7 , 1296
123456789457189326689372541, 33 , 7776
123456789457189326689723145, 11 , 7776
123456789457189326689732415, 36 , 7776
123456789457189326689732541, 33 , 7776
123456789457189326698237541, 31 , 7776
123456789457189326698372154, 42 , 3888
123456789457189326869237514, 31 , 7776
123456789457189326869237541, 31 , 7776
123456789457189326869273451, 36 , 7776
123456789457189326869273541, 31 , 7776
123456789457189326869327451, 11 , 7776
123456789457189326869723541, 33 , 7776
123456789457189326869732415, 31 , 3888
123456789457189326896237415, 31 , 7776
123456789457189326986273145, 33 , 7776
123456789457189326986327451, 7 , 7776
123456789457189362689237541, 33 , 7776
123456789457189362689327154, 15 , 3888
123456789457189362689327415, 11 , 7776
123456789457189362689723154, 15 , 7776
123456789457189362689723451, 15 , 7776
123456789457189362689723514, 18 , 7776
123456789457189362698237415, 18 , 7776
123456789457189362698327514, 35 , 7776
123456789457189362869237514, 32 , 3888
123456789457189362869327415, 23 , 3888
123456789457189362896372451, 25 , 7776
123456789457189362968372514, 31 , 3888
123456789457189362986237514, 31 , 7776
123456789457189362986273154, 27 , 7776
123456789457189623689273541, 23 , 3888
123456789457189623689327154, 7 , 3888
123456789457189623689372514, 32 , 3888
123456789457189623689723154, 6 , 3888
123456789457189623689723415, 12 , 3888
123456789457189623689723451, 6 , 1296
123456789457189623689723514, 10 , 3888
123456789457189623689732415, 31 , 3888
123456789457189623698237154, 32 , 7776
123456789457189623698273145, 36 , 7776
123456789457189623698273514, 35 , 7776
123456789457189623698327514, 35 , 7776
123456789457189623698327541, 35 , 7776
123456789457189623698372154, 33 , 7776
123456789457189623698723145, 31 , 7776
123456789457189623698723154, 9 , 7776
123456789457189623698723514, 37 , 7776
123456789457189623698732154, 31 , 3888
123456789457189623698732514, 43 , 3888
123456789457189623869273145, 20 , 3888
123456789457189623869273451, 24 , 3888
123456789457189623869372415, 37 , 7776
123456789457189623869732451, 36 , 7776
123456789457189623869732541, 35 , 7776
123456789457189623896237451, 24 , 3888
123456789457189623896237514, 20 , 1296
123456789457189623896327145, 23 , 7776
123456789457189623896327451, 14 , 7776
123456789457189623896327514, 23 , 7776
123456789457189623896723154, 11 , 7776
123456789457189623896723415, 42 , 7776
123456789457189623896723541, 33 , 7776
123456789457189623896732145, 33 , 7776
123456789457189623896732451, 32 , 7776
123456789457189623896732514, 37 , 7776
123456789457189623968327415, 37 , 7776
123456789457189623968723154, 15 , 7776
123456789457189623986327145, 10 , 3888
123456789457189623986327415, 10 , 3888
123456789457189623986327451, 6 , 1296
123456789457189623986327514, 12 , 3888
123456789457189623986372145, 37 , 7776
123456789457189623986723145, 11 , 7776
123456789457189623986732415, 32 , 7776
123456789457189632689237145, 33 , 3888
123456789457189632689273154, 25 , 7776
123456789457189632689327154, 15 , 3888
123456789457189632689327514, 18 , 7776
123456789457189632689372145, 32 , 7776
123456789457189632689723415, 9 , 7776
123456789457189632689723514, 19 , 7776
123456789457189632689732415, 31 , 3888
123456789457189632689732541, 37 , 7776
123456789457189632698372145, 11 , 7776
123456789457189632698732541, 21 , 7776
123456789457189632869327145, 27 , 7776
123456789457189632869327154, 35 , 7776
123456789457189632896237145, 17 , 7776
123456789457189632896237415, 17 , 7776
123456789457189632896273451, 36 , 7776
123456789457189632896327451, 25 , 7776
123456789457189632896372415, 9 , 7776
123456789457189632896732541, 25 , 7776
123456789457189632968237415, 29 , 7776
123456789457189632968273154, 30 , 3888
123456789457189632968327154, 36 , 7776
123456789457189632968327415, 25 , 7776
123456789457189632968372145, 31 , 3888
123456789457189632986237154, 12 , 7776
123456789457189632986237451, 12 , 3888
123456789457189632986273415, 35 , 7776
123456789457189632986327145, 14 , 7776
123456789457189632986372154, 25 , 7776
123456789457198236689237451, 32 , 7776
123456789457198236689273154, 36 , 7776
123456789457198236689327154, 34 , 3888
123456789457198236689372154, 35 , 7776
123456789457198236698723415, 14 , 7776
123456789457198236698732415, 24 , 7776
123456789457198236869273541, 32 , 7776
123456789457198236869723154, 37 , 7776
123456789457198236869732145, 33 , 7776
123456789457198236896273154, 35 , 7776
123456789457198236896372541, 30 , 3888
123456789457198236968237451, 32 , 7776
123456789457198236986237154, 36 , 7776
123456789457198236986237415, 37 , 7776
123456789457198236986273415, 35 , 7776
123456789457198236986723415, 41 , 7776
123456789457198236986732541, 34 , 3888
123456789457198263689732154, 27 , 7776
123456789457198263689732541, 23 , 7776
123456789457198263698327415, 15 , 7776
123456789457198263869327451, 32 , 7776
123456789457198263896237154, 41 , 7776
123456789457198263896237451, 41 , 7776
123456789457198263896327514, 11 , 7776
123456789457198263896732514, 32 , 7776
123456789457198263968273145, 35 , 7776
123456789457198263986237514, 36 , 7776
123456789457198263986327415, 35 , 7776
123456789457198263986732541, 32 , 7776
123456789457198326698732451, 33 , 7776
123456789457198326968723514, 35 , 7776
123456789457198326986372145, 25 , 7776
123456789457198362689237154, 38 , 2592
123456789457198362689237451, 38 , 7776
123456789457198362689723415, 11 , 7776
123456789457198362869273451, 38 , 1296
123456789457198362896732154, 36 , 7776
123456789457198623689237154, 17 , 7776
123456789457198623698237451, 33 , 7776
123456789457198623698372145, 24 , 7776
123456789457198623698372514, 35 , 7776
123456789457198623698732154, 31 , 7776
123456789457198623869327415, 36 , 3888
123456789457198623896237154, 25 , 7776
123456789457198623896237514, 27 , 3888
123456789457198623896273415, 27 , 7776
123456789457198623896723541, 18 , 7776
123456789457198623896732145, 11 , 7776
123456789457198623896732541, 36 , 7776
123456789457198623968237145, 18 , 7776
123456789457198623968372145, 37 , 7776
123456789457198623968723145, 35 , 7776
123456789457198623968732154, 31 , 7776
123456789457198623986732541, 25 , 7776
123456789457198632689327154, 32 , 7776
123456789457198632689732154, 31 , 3888
123456789457198632698237154, 42 , 3888
123456789457198632698327541, 11 , 7776
123456789457198632869237415, 36 , 3888
123456789457198632869237451, 35 , 7776
123456789457198632869327541, 31 , 7776
123456789457198632869372154, 43 , 1296
123456789457198632869723154, 35 , 7776
123456789457198632896237145, 14 , 7776
123456789457198632896237514, 23 , 7776
123456789457198632986237145, 24 , 3888
123456789457198632986237154, 27 , 3888
123456789457198632986372145, 36 , 7776
123456789457198632986732514, 37 , 7776
123456789457289136689713542, 34 , 7776
123456789457289136869731254, 19 , 7776
123456789457289136896371254, 39 , 7776
123456789457289136968137452, 14 , 7776
123456789457289136968137542, 24 , 7776
123456789457289163689173452, 40 , 432
123456789457289163689713254, 21 , 3888
123456789457289163698137524, 39 , 7776
123456789457289163698173542, 38 , 3888
123456789457289163698317254, 39 , 3888
123456789457289163698713254, 43 , 3888
123456789457289163869317245, 34 , 7776
123456789457289163896137425, 24 , 7776
123456789457289163896317524, 37 , 7776
123456789457289163896731254, 39 , 7776
123456789457289163968317245, 44 , 1296
123456789457289163968731542, 39 , 3888
123456789457289316986137452, 25 , 7776
123456789457289316986137542, 23 , 7776
123456789457289361869713524, 35 , 7776
123456789457289361986173452, 27 , 3888
123456789457289613689173254, 21 , 3888
123456789457289613689317425, 31 , 7776
123456789457289613689371245, 37 , 7776
123456789457289613689371254, 24 , 3888
123456789457289613698317254, 19 , 7776
123456789457289613869173254, 25 , 7776
123456789457289613869173452, 22 , 3888
123456789457289613869713254, 14 , 7776
123456789457289613869731524, 43 , 3888
123456789457289613896317245, 10 , 7776
123456789457289613896731254, 34 , 3888
123456789457289613968731425, 37 , 7776
123456789457289613986137245, 26 , 7776
123456789457289613986173254, 23 , 7776
123456789457289613986173542, 23 , 3888
123456789457289613986731245, 38 , 3888
123456789457289631689137254, 14 , 7776
123456789457289631689173245, 43 , 1296
123456789457289631689713245, 37 , 7776
123456789457289631689731254, 9 , 7776
123456789457289631698371245, 32 , 3888
123456789457289631698371452, 31 , 7776
123456789457289631698713452, 35 , 7776
123456789457289631869713524, 37 , 7776
123456789457289631869731254, 18 , 7776
123456789457289631896137425, 29 , 2592
123456789457289631896317245, 23 , 3888
123456789457289631896317254, 22 , 3888
123456789457289631896371254, 37 , 7776
123456789457289631968137254, 8 , 3888
123456789457289631968317245, 41 , 3888
123456789457289631968731245, 26 , 3888
123456789457289631986137245, 28 , 3888
123456789457289631986731245, 28 , 7776
123456789457298136869173254, 37 , 7776
123456789457298136986317245, 37 , 7776
123456789457298316698137254, 35 , 7776
123456789457298361986731524, 18 , 7776
123456789457298613689137245, 10 , 7776
123456789457298613689713245, 37 , 7776
123456789457298613689731245, 9 , 7776
123456789457298613698713245, 29 , 7776
123456789457298613698731254, 35 , 7776
123456789457298613869317245, 18 , 7776
123456789457298613896137524, 27 , 7776
123456789457298613896317245, 16 , 7776
123456789457298613968713254, 36 , 3888
123456789457298613986371254, 35 , 7776
123456789457298631698731245, 29 , 7776
123456789457298631869713254, 35 , 7776
123456789457298631896137524, 21 , 7776
123456789457298631896713245, 11 , 7776
123456789457298631968713425, 10 , 3888
123456789457298631986137542, 20 , 3888
123456789457389126698172354, 42 , 7776
123456789457389126896127453, 12 , 3888
123456789457389126986721543, 15 , 7776
123456789457389162896217435, 18 , 7776
123456789457389162986712345, 22 , 7776
123456789457389162986721354, 14 , 7776
123456789457389216986127453, 9 , 7776
123456789457389261896217534, 35 , 7776
123456789457389261986127534, 8 , 3888
123456789457389261986721354, 13 , 3888
123456789457389612896127354, 11 , 7776
123456789457389612896172345, 3 , 3888
123456789457389612896172354, 17 , 3888
123456789457389612896271345, 5 , 1296
123456789457389612896712345, 4 , 3888
123456789457389612896712354, 13 , 7776
123456789457389612896721354, 15 , 3888
123456789457389612968127354, 38 , 7776
123456789457389612986127354, 8 , 7776
123456789457389621689127345, 9 , 7776
123456789457389621689721354, 6 , 3888
123456789457389621698127345, 36 , 3888
123456789457389621869127354, 12 , 7776
123456789457389621869721345, 25 , 7776
123456789457389621896172543, 36 , 7776
123456789457389621896217354, 15 , 3888
123456789457389621986271345, 17 , 3888
123456789457389621986721354, 2 , 3888
123456789457398216986217354, 33 , 7776
123456789457398612896127354, 8 , 7776
123456789457398612896172354, 18 , 7776
123456789457398612896217354, 11 , 7776
123456789457839612896271345, 3 , 7776
123456789457893612896127345, 1 , 216
123456789457893612896127354, 2 , 1944
123456789457893612896217354, 7 , 648
123456789457893612986217354, 7 , 648



Gang of the 44:
a collection of 44 9-tupels of 3-sets which classifies
each sudokubands. (link to Frazer)
A sudokugrid is sometimes characterized by the numbers
of the "gangsters" for its 6 chutes.


416: (give it a name ?) (link)
the number of different equivalence classes for a band
in a sudokugrid.
A sudokugrid is sometimes characterized by the 6 numbers
of the 416-classes of its 6 chutes.
This is often, but not always sufficient to uniquely
determine the equivalence-class of a sudokugrid


Equivalence-Class of a sudokugrid:
two sudokugrids are equivalent, if one can be transformed into
the
other by
permuting the 9 symbols
permuting rows in a band
permuting columns in a stack
permuting bands
permuting stacks
transposing
This gives 545655555 essentially different sudokugrids or
Equivalence classes
link


http://www.sudoku.com/forums/viewtopic.php?t=2


------------------------------------------------

here is a repost of the enumeration method using
the "gang44"-representatives. I couldn't find the original post,
but maybe it's still there. Anyway, here is it again:


Let S be the collection of the 84 subsets of {1,..,9} of size 3.
Let T be the collection of the 4741632000 9-tupels (S1,..,S9)
with members from S such that
S1+S2+S3=S4+S5+S6=S7+S8+S9={1,2,3,4,5,6,7,8,9} ,
where "+" is set-union.
Let 2 members from T be equivalent if one can be obtained
from the other by one of the known obvious 6^4*9! operations.
Then we get the collection E of the known 44 minimal elements from T,
one from each equivalence class, called "the gang of the 44".
For M in T let C(M) be its equivalent representative in E.
For M in E let Z(M) be the size of its equivalence class.
For M in E let N(M) be the number of partial 3*9 sudoku grids
compatible with M with respect to the 6^9 operations
of permuting inside a column.
The 2*44 values of N(M),Z(M) are constant within one class and
can be calculated quickly.
For each M=(M1,..,M9) in T let U(M) be the set of the 175616
3-tupels (M,A,B) in T^3 , A=(A1,..,A9),B=(B1,..,B9)
such that Mi+Ai+Bi={1,2,3,4,5,6,7,8,9} for each 1<=i<=9.
----------------------------------------------------------
then the total number of sudokus is the sum over all M in E,
over all (M,A,B) in U(M)
of Z(M)*N(M)*N(C(A))*N(C(B)).
----------------------------------------------------------
This indeed adds up to 6670903752021072936960.
There are 7727104 summands in total, but since many of the
N(x) and Z(x) coincide, only 1398 summands are different.

You can easily save a factor of 2 by discarding triples
in U(M) with A>B.
Maybe another factor of 3 can be saved by requiring M<A<B,
but that makes things more complicated.


How can we calculate the total number of sudoku-classes
as defined by RedEd but discarding transposition
with this method ? 5472730538

sum over all M in E,
over all (M,A,B) in U(M)
of Z(M)*Q(M)*Q(C(A))*Q(C(B))
gives 19859770556




E = "gang" of the 44
=====================

(1) M, element of E, minimal in its class ("ganger" or "gangster" ?)
(2) C(M)
(3) N(M) , number of compatible 3*9 sudokus (bands)
(4) Q(M) number of classes of compatible bands (from the gang of 416)
(5) Z(M) , number of 9-tupels from T in the class
--------------------------------------------------
123456789123456789123456789,1,1728,2,60480
123456789123456789123457689,2,576,3,4898880
123456789123456789124357689,3,192,3,29393280
123456789123456789124378569,4,192,2,9797760
123456789123456789147258369,5,96,2,6531840
123456789123457689123458679,6,576,4,6531840
123456789123457689123468579,7,864,7,6531840
123456789123457689124356789,8,192,6,58786560
123456789123457689124358679,9,192,8,117573120
123456789123457689124367589,10,192,6,58786560
123456789123457689124368579,11,288,24,235146240
123456789123457689124389567,12,192,6,58786560
123456789123457689126345789,13,192,3,29393280
123456789123457689126347589,14,192,8,117573120
123456789123457689126348579,15,288,16,117573120
123456789123457689145267389,16,96,1,29393280
123456789123457689145268379,17,144,8,117573120
123456789123457689146258379,18,168,14,235146240
123456789123457689148259367,19,144,3,58786560
123456789124357689125348679,20,192,5,39191040
123456789124357689125367489,21,144,4,58786560
123456789124357689125368479,22,168,9,117573120
123456789124357689125378469,23,264,13,117573120
123456789124357689126358479,24,144,8,117573120
123456789124357689126378459,25,168,14,235146240
123456789124357689126389457,26,144,4,58786560
123456789124357689128345679,27,192,10,117573120
123456789124357689128356479,28,168,9,117573120
123456789124357689128359467,29,120,4,78382080
123456789124357689134258679,30,192,5,39191040
123456789124357689134268579,31,288,28,235146240
123456789124357689135268479,32,228,22,235146240
123456789124357689135278469,33,276,26,235146240
123456789124357689136258479,34,168,9,117573120
123456789124357689136278459,35,180,30,470292480
123456789124357689137268459,36,216,20,235146240
123456789124357689138259467,37,156,26,470292480
123456789124357689138269457,38,228,11,78382080
123456789124357689158267349,39,120,6,117573120
123456789124378569129356478,40,96,2,3265920
123456789124378569135279468,41,192,8,78382080
123456789124378569137245689,42,516,9,26127360
123456789124378569157268349,43,168,6,39191040
123456789147258369159267348,44,120,2,4354560
-------------------------------------------------
sum:11352,416,4741632000


60713 out of the 85184=44^3 tupels of 3 members
from the list can be joined to form a valid 9*9 sudoku.


-----------------------------

there are 6670903752021072936960 sudokugrids from
5472730538 equivalence classes ("S-classes")

where grids are S-equivalent, if they can be transformed into
each other by

permuting symbols
permuting the 3 rows in some stack
permuting the 3 columns in some band
permuting the 3 stacks
permuting the 3 bands
transposing

these 6 groups of transformations do commute and give
9!*6^8*2 transformations in total.


When we omit transposition, we get 10945437157 "T-classes",
23919 S-classes have only 1 T-class, the other S-classes
have 2 T-classes.


there are only 306693 classes ("G-classes"), when we also allow
permuting the 3 entries in any minicolumn but remove (not allow?) transposition.
These 306693 classes generate 11555445688 sudokugrids,
by permuting minicolumns modulo permuting rows in a band,
at least one from each S-class. They can be generated in about
5 hours but storing them requires too much memory.

Many sudoku-properties are an invariant of the S-class and thus
an invariant of the T-class and some can be checked by checking
these 11555445688 generated sudokus.


10895 ordered 3-tuples of "gangsters" from the "gang of the 44"
occur in sudokugrids.
Between 1 and 985 G-class-representatives
correspond to one such triple. Many triples have just only a few
G-class members - half of them less than 10.
Most (985) "belong" to the triple (18,35,37).
Remember, these 18,35,37 were among the most
frequent in random sudokus and in Gordon's 17s.


(planning to fill in the missing numbers and some updates later...)
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby coloin » Wed Jun 09, 2010 9:22 am

dukuso wrote:what is indeed the case ?
that index416 is not working correctly ?


well it seems to work for grids which start >31- 416

but I dont understand how it can

Is the number of essentially different B12347 greater than 416^2 ?????

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: gang of 44 , gang of 416

Postby ronk » Wed Jun 09, 2010 10:02 am

dukuso wrote:gang of the 44
================

(1) (allowed sudoku-) 9-tupel of 3-sets for the 3 entries in the 9 columns
123456789123456789123456789 = ({1,2,3},{4,5,6},...)

Why listed in this order? Why not as they would have to appear in an allowed sudoku-grid, just row-order lexicographically minimal :?:

As in ... 123456789456789123789123456

gsf, shouldn't -gtm.0 -e"uniq(%#mc)" on the template below generate all 44 subgrids :?: I get only one (using version 20090116).

Code: Select all
 1        2        3        | 4        5        6        | 7        8        9       
 4        5        6789     | 123789   123789   123789   | 1236     1236     1236     
 6789     6789     6789     | 123789   123789   123789   | 123456   123456   123456   
----------------------------+----------------------------+---------------------------
 .        .        .        | .        .        .        | .        .        .       
 .        .        .        | .        .        .        | .        .        .       
 .        .        .        | .        .        .        | .        .        .       
----------------------------+----------------------------+---------------------------
 .        .        .        | .        .        .        | .        .        .       
 .        .        .        | .        .        .        | .        .        .       
 .        .        .        | .        .        .        | .        .        .       
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: gang of 44 , gang of 416

Postby dukuso » Wed Jun 09, 2010 12:50 pm

coloin wrote:
dukuso wrote:what is indeed the case ?
that index416 is not working correctly ?


well it seems to work for grids which start >31- 416

but I dont understand how it can

Is the number of essentially different B12347 greater than 416^2 ?????

C



even if it is ... no problem.
5.5e9 is also greater than 416^3.
You may permute columns in a tower (of a band) - but only simultaneously !
If you have two compatible bands then permuting each may give only 416 classes
but you are not allowed to permute them both independently.
So there are more classes of B123456 than 416^2

For B12347 block 1 is special, 9 ways to select it, and the digits in it are also
non-invariant
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: gang of 44 , gang of 416

Postby dukuso » Wed Jun 09, 2010 12:54 pm

> Why listed in this order? Why not as they would have to appear in an allowed sudoku-grid,
> just row-order lexicographically minimal :?:
> As in ... 123456789456789123789123456

historically ...
I used them as bitmaps, the order in a minicolumn doesn't matter
the above gangster 123456789123456789123456789
would encode as 14,112,896,14,112,896,14,112,896

I see, it's confusing, so I changed it now.
dukuso
 
Posts: 479
Joined: 25 June 2005

Next

Return to General