From ecee6895458d8e06934c95b687a133eddd754dad Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 8 Nov 2026 18:24:35 +0100 Subject: Fix table generation (breaking change) There was a small (but kinda silly) error in the prunin table generation for H48 solvers, resulting in some positions showing a higher lower bound than they actually had. This means that the solvers where in theory broken and could have skipped some solutions - but we have not found any example, as this would be an extremely rare situation. This affected all tables from H48h2 to H48h11. This bug was found by LLM-based coding analysis in the context of the development of egg-solver: https://github.com/ArhanChaudhary/egg-solver Thanks to Arhan Chaudhary for reporting the bug. --- src/solvers/h48/checkdata.h | 74 +++++++++++----------- src/solvers/h48/gendata_h48.h | 2 +- utils/egg-tables | 140 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 178 insertions(+), 38 deletions(-) create mode 100644 utils/egg-tables diff --git a/src/solvers/h48/checkdata.h b/src/solvers/h48/checkdata.h index e2fa38c..749cfc7 100644 --- a/src/solvers/h48/checkdata.h +++ b/src/solvers/h48/checkdata.h @@ -43,90 +43,90 @@ struct { .max = 3, .table = { [0] = 6391286, - [1] = 55494785, + [1] = 55494787, [2] = 252389935, - [3] = 155993794, + [3] = 155993792, }, }, [3] = { .max = 3, .table = { [0] = 6686828, - [1] = 63867852, - [2] = 392789689, - [3] = 477195231, + [1] = 63867855, + [2] = 392789704, + [3] = 477195213, }, }, [4] = { .max = 3, .table = { - [0] = 77147213, - [1] = 543379415, - [2] = 1139570251, - [3] = 120982321, + [0] = 77147216, + [1] = 543379445, + [2] = 1139570223, + [3] = 120982316, }, }, [5] = { .max = 3, .table = { - [0] = 82471284, - [1] = 687850732, - [2] = 2345840746, - [3] = 645995638, + [0] = 82471289, + [1] = 687850794, + [2] = 2345840739, + [3] = 645995578, }, }, [6] = { .max = 3, .table = { - [0] = 85941099, - [1] = 804752968, - [2] = 4077248182, - [3] = 2556374551, + [0] = 85941105, + [1] = 80475305, + [2] = 4077248291, + [3] = 2556374347, }, }, [7] = { .max = 3, .table = { - [0] = 88529761, - [1] = 897323475, - [2] = 6126260791, - [3] = 7936519573, + [0] = 88529771, + [1] = 897323586, + [2] = 6126261227, + [3] = 7936519016, }, }, [8] = { .max = 3, .table = { - [0] = 1051579940, - [1] = 8136021316, - [2] = 19024479822, - [3] = 1885186122, + [0] = 1051580076, + [1] = 8136022157, + [2] = 19024479157, + [3] = 1885185810, }, }, [9] = { .max = 3, .table = { - [0] = 1102038189, - [1] = 9888265242, - [2] = 38299375805, - [3] = 10904855164, + [0] = 1102038343, + [1] = 9888266493, + [2] = 38299376032, + [3] = 10904853532, }, }, [10] = { .max = 3, .table = { - [0] = 1133240039, - [1] = 11196285614, - [2] = 64164702961, - [3] = 43894840186, + [0] = 1133240200, + [1] = 11196287163, + [2] = 64164706157, + [3] = 43894835280, }, }, [11] = { .max = 3, .table = { - [0] = 1150763161, - [1] = 12045845660, - [2] = 91163433330, - [3] = 136418095449, + [0] = 1150763320, + [1] = 12045847349, + [2] = 91163441021, + [3] = 136418085910, }, }, }; diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index 0b85e49..be06588 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h @@ -308,7 +308,7 @@ gendata_h48_runthread(void *arg) wrapthread_mutex_lock(dfsarg->shortcubes_mutex); kv = h48map_nextkvpair(dfsarg->shortcubes, dfsarg->next); - if (*dfsarg->next == dfsarg->shortcubes->capacity) { + if (kv.val == MAP_UNSET_VAL) { wrapthread_mutex_unlock(dfsarg->shortcubes_mutex); break; } diff --git a/utils/egg-tables b/utils/egg-tables new file mode 100644 index 0000000..d331e59 --- /dev/null +++ b/utils/egg-tables @@ -0,0 +1,140 @@ +Table distribution generated by egg-solver (https://github.com/ArhanChaudhary/egg-solver) + +[gen] h0 base 7: 0.03 GiB, 16 threads +[gen h0] depth 0: 1 entries +[gen h0] depth 1: 1 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 2: 4 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 3: 34 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 4: 331 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 5: 3612 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 6: 41605 entries (forward, 0.0s step, 0.0s total) +[gen h0] depth 7: 474128 entries (forward, 0.0s step, 0.1s total) +[gen h0] depth 8: 4953846 entries (forward, 0.0s step, 0.1s total) +[gen h0] depth 9: 34776317 entries (forward, 0.1s step, 0.2s total) +h0 base 7 distribution [519716, 4953846, 34776317, 77317571] + +[gen] h1 base 8: 0.06 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h1 base 8 distribution [6012079, 45822302, 142018732, 41281787] + +[gen] h2 base 8: 0.11 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h2 base 8 distribution [6391286, 55494787, 252389935, 155993792] + +[gen] h3 base 8: 0.23 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h3 base 8 distribution [6686828, 63867855, 392789704, 477195213] + +[gen] h4 base 9: 0.45 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h4 base 9 distribution [77147216, 543379445, 1139570223, 120982316] + +[gen] h5 base 9: 0.91 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h5 base 9 distribution [82471289, 687850794, 2345840739, 645995578] + +[gen] h6 base 9: 1.81 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h6 base 9 distribution [85941105, 804753057, 4077248291, 2556374347] + +[gen] h7 base 9: 3.62 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h7 base 9 distribution [88529771, 897323586, 6126261227, 7936519016] + +[gen] h8 base 10: 7.25 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h8 base 10 distribution [1051580076, 8136022157, 19024479157, 1885185810] + +[gen] h9 base 10: 14.50 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h9 base 10 distribution [1102038343, 9888266493, 38299376032, 10904853532] + +[gen] h10 base 10: 28.99 GiB, 16 threads +[gen] prefix depth 1: 1 h11 entries +[gen] prefix depth 2: 4 h11 entries +[gen] prefix depth 3: 34 h11 entries +[gen] prefix depth 4: 333 h11 entries +[gen] prefix depth 5: 3815 h11 entries +[gen] prefix depth 6: 45382 h11 entries +[gen] prefix depth 7: 548562 h11 entries +[gen] prefix depth 8: 6839723 h11 entries +h10 base 10 distribution [1133240200, 11196287163, 64164706157, 43894835280] + +[gen] h11 base 10: 57.99 GiB, 16 threads +[gen h11] depth 0: 1 entries +[gen h11] depth 1: 1 entries (forward, 1.5s step, 12.0s total) +[gen h11] depth 2: 4 entries (forward, 1.2s step, 15.6s total) +[gen h11] depth 3: 34 entries (forward, 1.2s step, 19.1s total) +[gen h11] depth 4: 333 entries (forward, 1.2s step, 22.6s total) +[gen h11] depth 5: 3815 entries (forward, 1.2s step, 26.1s total) +[gen h11] depth 6: 45382 entries (forward, 1.2s step, 29.7s total) +[gen h11] depth 7: 548562 entries (forward, 1.2s step, 33.2s total) +[gen h11] depth 8: 6839723 entries (forward, 1.2s step, 36.7s total) +[gen h11] depth 9: 85659526 entries (forward, 1.5s step, 40.6s total) +[gen h11] depth 10: 1057665939 entries (forward, 6.8s step, 49.8s total) +[gen h11] depth 11: 12045847349 entries (forward, 69.6s step, 121.9s total) +[gen h11] depth 12: 91163441021 entries (forward, 638.1s step, 761.7s total) +h11 base 10 distribution [1150763320, 12045847349, 91163441021, 136418085910] -- cgit v1.3