[seqfan] Re: Minimal simple loop puzzle

[Elijah Beregovsky]

I’ve been idly surfing the net today, and stumbled upon this paper: https://arxiv.org/pdf/2202.02046.pdf. It presents an ingenious construction that proves that satisfiability of simple loop, as well as most other pencil puzzles, is NP-complete. It’s not that unexpected, considering most HCP-type problems are, but it still means solving thousands of them is bound to take forever whatever I do. So, I guess, the only thing that’s left if I am to continue using the try-until-successful approach is cleaning up the code and waiting. I wonder, is there a way to use already solved puzzles to quickly solve the next ones? Without running out of memory, that is?

Best wishes,
Elijah


As a sidenote, this is a neat polynomial-time heuristic for HCP: https://arxiv.org/pdf/1902.10337.pdf. The times I’m getting using Mathematica are of the same order of magnitude as their tests on cubic graphs, so, there’s likely no reason to try being clever and write my own hamiltonicity test.