[seqfan] Re: Minimal simple loop puzzle

Elijah Beregovsky elijah.beregovsky at gmail.com
Sun Feb 27 21:29:29 CET 2022

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,

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.

More information about the SeqFan mailing list