commit b7bb88cd6eb2a8c8e3f26e276ab849d52168668a
parent de04d37e8520079f5bba3b1a87d42313297543db
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 19 Dec 2025 15:59:35 +0100
Minor improvement
Add a trivial check to H48 solver. The benchmarks show, surprisingly,
a more noticeable improvement for larger solvers (h10, h11). I was expecting
it to be more noticeable for smaller solvers.
It is likely that this change is irrelevant to performance and all changes
in the benchmark results are just random chance.
Diffstat:
2 files changed, 31 insertions(+), 26 deletions(-)
diff --git a/benchmarks/results_h48.py b/benchmarks/results_h48.py
@@ -1,36 +1,36 @@
h48_single_thread = {
- 6: {17: 52.7302, 18: 405.7879, 19: 2032.4602},
- 7: {17: 26.4977, 18: 212.7314, 19: 1074.2251},
- 8: {17: 19.8239, 18: 151.7597, 19: 639.6197},
- 9: {17: 9.0082, 18: 62.0400, 19: 293.2197},
- 10: {17: 6.2190, 18: 31.1395, 19: 158.3581, 20: 1118.7513, "superflip": 48.7016},
- 11: {17: 3.5879, 18: 19.5970, 19: 93.5762, 20: 651.2212, "superflip": 20.2721},
+ 6: {17: 52.9727, 18: 407.1435, 19: 2055.8785},
+ 7: {17: 26.8541, 18: 214.7064, 19: 1053.9732},
+ 8: {17: 19.8408, 18: 152.2214, 19: 639.4834},
+ 9: {17: 8.9053, 18: 61.6760, 19: 294.6517},
+ 10: {17: 5.8445, 18: 30.0880, 19: 154.5389, 20: 1087.6552, "superflip": 48.8410},
+ 11: {17: 3.2420, 18: 18.3482, 19: 85.6898, 20: 581.9588, "superflip": 19.2614},
}
h48_4_threads = {
- 6: {17: 15.2794, 18: 116.1387, 19: 577.3595},
- 7: {17: 7.7522, 18: 59.8914, 19: 293.4824},
- 8: {17: 5.8807, 18: 42.7619, 19: 180.4499},
- 9: {17: 2.7609, 18: 18.4867, 19: 84.1350, 20: 610.8914, "superflip": 25.3932},
- 10: {17: 1.9215, 18: 9.1287, 19: 43.7573, 20: 338.4877, "superflip": 14.2593},
- 11: {17: 1.1997, 18: 5.8332, 19: 26.6060, 20: 176.8453, "superflip": 6.1932},
+ 6: {17: 15.2251, 18: 115.3688, 19: 605.5267},
+ 7: {17: 7.8799, 18: 61.3355, 19: 303.0388},
+ 8: {17: 5.8624, 18: 43.4193, 19: 179.8491},
+ 9: {17: 2.7696, 18: 17.6190, 19: 87.1236, 20: 640.3405, "superflip": 25.3726},
+ 10: {17: 1.8676, 18: 9.0543, 19: 44.7847, 20: 310.3914, "superflip": 14.0333},
+ 11: {17: 1.1173, 18: 5.6240, 19: 24.1467, 20: 174.4689, "superflip": 5.9548},
}
h48_16_threads = {
- 6: {17: 5.3639, 18: 37.6695, 19: 191.8620},
- 7: {17: 2.8213, 18: 20.1045, 19: 96.7922},
- 8: {17: 2.0779, 18: 14.6013, 19: 60.4149},
- 9: {17: 1.0796, 18: 6.1831, 19: 27.5530, 20: 200.9519, "superflip": 10.7149},
- 10: {17: 0.7511, 18: 3.2061, 19: 15.0046, 20: 103.8125, "superflip": 5.6217},
- 11: {17: 0.5173, 18: 2.1196, 19: 8.6965, 20: 56.4344, "superflip": 2.4857},
+ 6: {17: 5.3309, 18: 37.8142, 19: 193.5352},
+ 7: {17: 2.8657, 18: 20.8215, 19: 99.9139},
+ 8: {17: 2.0775, 18: 14.2672, 19: 60.0995},
+ 9: {17: 1.0595, 18: 6.2074, 19: 27.5523, 20: 201.2200, "superflip": 10.7739},
+ 10: {17: 0.7600, 18: 3.1980, 19: 14.5771, 20: 105.1686, "superflip": 5.5616},
+ 11: {17: 0.4946, 18: 2.0381, 19: 8.3613, 20: 55.4269, "superflip": 2.4087},
}
h48_all_solutions = {
- 6: {17: 17.1940, 18: 203.6879, 19: 2286.7364},
- 7: {17: 9.0219, 18: 105.0559, 19: 1166.1059},
- 8: {17: 5.9919, 18: 68.8215, 19: 686.0935},
- 9: {17: 3.0192, 18: 31.9398, 19: 319.0297},
- 10: {17: 1.7972, 18: 17.8931, 19: 167.6695, 20: 1464.2636, "superflip": 48.9035},
- 11: {17: 1.1838, 18: 10.5628, 19: 96.0518, 20: 808.8516, "superflip": 22.6335},
+ 6: {17: 17.1587, 18: 204.6182, 19: 2296.3135},
+ 7: {17: 9.1380, 18: 106.0127, 19: 1177.4728},
+ 8: {17: 6.1641, 18: 67.9895, 19: 685.6033},
+ 9: {17: 3.0422, 18: 31.9821, 19: 323.2516},
+ 10: {17: 1.7822, 18: 17.4947, 19: 168.2516, 20: 1465.2950, "superflip": 48.6248},
+ 11: {17: 1.1364, 18: 10.2076, 19: 92.3419, 20: 791.1480, "superflip": 21.8014},
}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
@@ -115,10 +115,15 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1])
arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES;
arg->nodes_visited++;
- /* Preliminary probing using last computed bound, if possible */
-
n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
target = arg->target_depth - n;
+
+ /* We'll never get a bound higher than base + 3 */
+ if (arg->base + 3 <= target)
+ return false;
+
+ /* Preliminary probing using last computed bound, if possible */
+
if ((arg->use_lb_normal && arg->lb_normal > target) ||
(arg->use_lb_inverse && arg->lb_inverse > target))
return true;
