[seqfan] Re: Minimal simple loop puzzle

[Rob Pratt]

I have confirmed via integer linear programming that your results for n <= 8 are optimal.  You can reduce the search space by approximately a factor of 8 by imposing symmetry-breaking constraints.  For example, remove at least as many nodes from the top half of the grid as from the bottom half.

> On Feb 27, 2022, at 9:31 PM, Elijah Beregovsky <elijah.beregovsky at gmail.com> wrote:
> 
> 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.
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/