Band Signatures and Uses

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

Band Signatures and Uses

Postby holdout » Tue Jul 20, 2010 10:03 pm

Band Signatures and Uses

Did you know that the signature of a band can be used to quickly determine:
1) the gangster class (1-44), and
2) the number 3-row permutations that have the given signature?

The "signature" of a band is a 9-long array of digits which appear in each column. For convenience, the three digits in each column are concatenated in ascending order and listed as a single quantity. For example:
Code: Select all
  2 6 9  5 4 3  8 1 7
  3 4 7  8 1 2  6 9 5  Signature = { 238, 146, 579, 568, 147, 239, 468, 139, 257 }
  8 1 5  6 7 9  4 3 2

This is how it is done: 1) an inexpensive statistic is computed, and 2) the statistic is then correlated to the known answer. The trick is to find a statistic which correlates 100% of the time. Of course, the statistic should be invariant to chute swaps and column swaps within a chute.

In one attempt, the statistic took on 41 different values, and these values correlated with 100% accuracy to the 16 grid completion choices. See routine SignatureTriples(), below. The statistic failed to predict the gangster class.

Later, a modified statistic took on 44 values and correlated precisely to 44 gangster class values. See routine Signature44(), also below.

In each case a statistic is accumulated over triples of columns (one from each chute), afterwhich pairs of columns are compared and "hits" are counted. The modified statistic also uses the count of the unique digits in the three chosen columns.

Code: Select all
/*******************************************************************************
             Compute Population Count Table for 9-bit Quantities

PopCount[i], i=0,...,511 will be the number of bit 1-bits in integer 'i'.

*******************************************************************************/
int PopCount[512] = {-1};

void PopCount_Init ()
{
  int i;
  if ( PopCount[0] == 0 ) return;   // Already done!
  PopCount[0] = 0;
  for ( i=1; i < 512; i++ )
      PopCount[i] = (i & 1) + PopCount[i >> 1];
}

/*******************************************************************************
Purpose:
  Given the signature of a band:
  1) Compute the "class44" number [1,44].
  2) Compute the number of permutation configurations for this band, given
     that column-1 digits are in ascending order.  This value is returned.

Note:
  In array "signature", exactly three of the nine low-order bits of each
  value are set to 1, one bit for each value in the column.
*******************************************************************************/
int Signature44 (int signature[9], int *class44)
{
  // Binary search list, given "stat" computation.
  int SigStatList[44] = {
     189000, 705240, 963360,1083040,1152260,1242243,1243330,1261060, //  7
    1341160,1343220,1432240,1441040,1503520,1511360,1520160,1530050, // 15
    1530060,1602421,1611240,1620040,1620043,1620060,1620151,1631021, // 23
    1701220,1710150,1721040,1800000,1800009,1800330,1801221,1802203, // 31
    1802220,1810021,1820000,1900023,1900131,2000005,2000022,2100003, // 39
    2101002,2103000,2200002,2400000 };                               // 43

  // Class44 Number, given SigStatList index in [0,43].
  int SigStatClass[44] = {
    41,17,31,24, 4,38, 9,32,16,18,14, 8,19,15, 7, 1,26,20, 3, 0, 6, 5,
    33, 2,11,10,21,25,42,37,22,23,28,13,36,12,27,34,35,29,30,40,39,43 };

  // Number of Permutation Triples, given "kat44" in [0,43].
  int SigStatTriples[44] = {
    46,48,48,28,26,38,28,36,38,32,32,44,24,48, 24,20,30,20,28,24,32, 28,
    32,16,28,86,32,32,24,32,32,28,32,32,32,32,144,96,24,96,16,20,16,288 };

  // Other declarations
  static once = 1;
  int f[82], pick[11] = { 0,6,7,10,12,15,20,32,40,48,81 };
  int stat, kat44, i, j, k, n;

  // Onetime code
  if (once) { PopCount_Init(); once=0; }

  // Compute statistic: only six elements (not 11)
  // of "f" are needed to make the statistic unique.
  for ( i=0; i < 6; i++ ) f[pick[i]] = 0;

  for ( i=0; i < 3; i++ )
  { for ( j=3; j < 6; j++ )
    { for ( k=6; k < 9; k++ )
      { n = PopCount[ signature[i] & signature[j] ] *
       PopCount[ signature[i] & signature[k] ] *
       PopCount[ signature[j] & signature[k] ] *
            PopCount[ signature[i] | signature[j] | signature[k] ];
        f[n]++;
      }
    }
  }
 
  // Finish "stat" computation.
  for ( stat=i=0; i < 6; i++ ) stat = (10*stat) + f[pick[i]];

  // Find statistic in list (binary search).
  for ( kat44 = i = -1, j = 44; j > i+1; )
  { k = (i+j)/2;
    if ( SigStatList[k] == stat )
       { kat44 = SigStatClass[k]; break; }
    if ( stat < SigStatList[k] ) j = k; else i = k;
  }

  // Error check
  if ( kat44 == -1 )
  { fprintf(stderr,"*** SignatureTriples(): Fatal error.\n");
    fprintf(stderr,"    Statistic \"%d\" not found in list.\n",stat);
    exit(1);
  }

  // Debug
  //fprintf(fp,"%2d %3d %7d ::",kat44,SigStatTriples[kat44],stat);
  //for ( i=0; i < 6; i++ ) fprintf(fp,"%3d",f[pick[i]]);
  //fprintf(fp,"\n");

  // All is well!
  (*class44) = kat44+1;
  return( SigStatTriples[kat44] );
}

/*******************************************************************************
Purpose:
  Given the signature of a band, return the number of permutation
  configurations for the band, given that column-1 digits are in
  ascending order.  This is a bit faster than "Signature44".

Note:
  In array "signature", exactly three of the nine low-order bits of each
  value are set to 1, one bit for each value in the column.
*******************************************************************************/
int SignatureTriples (int signature[9])
{
  int SigStatTriples[41] = {
    20, 20, 28, 26, 24, 28, 30, 38, 32,  28, 36, 16,  38, 46, // 13
    20, 24, 28, 28, 28, 24, 48, 44, 86,  24, 32, 16,  32, 16, // 27
    48, 48, 32, 32, 32, 32, 32, 32, 32, 144, 96, 96, 288 };   // 40

  int SigStatList[41] = {
     54,  66,  72,  82,  84,  86,  92, 100, 102, 104, 106, 108, 114, 128, // 13
    130, 138, 142, 150, 152, 160, 168, 178, 180, 192, 194, 196, 202, 222, // 27
    248, 262, 280, 286, 336, 368, 372, 410, 504, 880, 936,1092,2268 };    // 40

  // Other declarations
  static int t[1108] = {0};
  int stat, i, j, k, n;

  // Onetime code: compute look-up table.
  if ( t[0] == 0 )
  { PopCount_Init();
    for ( i=1; i < 1108; i++ ) t[i] = 0;
    for ( i=0; i < 41; i++ ) t[ (SigStatList[i]-54) >> 1 ] = SigStatTriples[i];
  }

  // Compute statistic
  for ( stat=i=0; i < 3; i++ )
  { for ( j=3; j < 6; j++ )
    { for ( k=6; k < 9; k++ )
      { n = PopCount[ signature[i] & signature[j] ] *
       PopCount[ signature[i] & signature[k] ] *
       PopCount[ signature[j] & signature[k] ] ;
       stat += n*(n+1);
      }
    }
  }

  // Error check
  if ( stat < 54 || stat > 2268 || t[ n=(stat-54)>>1 ] == 0 )
  { fprintf(stderr,"*** SignatureTriples(): Fatal error.\n");
    fprintf(stderr,"    Statistic \"%d\" not found in list.\n",stat);
    exit(1);
  }

  // Return number of configurations
  return( t[n] );
}
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Return to General