When I have decided to automate the process, I started by reading the Mortal Coil threads.

I was really happy that the hard work is done by example bot. The " "->"\t\t\t" replacement was easy to debug out.

For start I changed path to qpath interface, than I have added backtracking to the random search to search all paths for the starting point. This allows me to shrink the set of possible starts

(parity excluding starts at some levels was implemented as first improvement).

I have added degree one square dynamic detection to stop searching in earlier stages.

This itself lead to solving levels till 160 overnight.

(OK there was surprise that qpath requires first direction even on degree one starting square, and the search was several times stopped due to slow http request.)

I am planning to add dynamic disconnection detection as the next easy search stop in earlier stages.

The main problem of the search is lack of sharing information among different starting points.

I am tending to rewrite the code not to work on grid, but to work on graph based on grid, but with path shortcuts ... researching paths with all vertices with degree 2 is surely waste of time. This should be done well to allow extensions based on MortalCoil rules forced paths (as I would do manually)... so probabbly the edges will be directed. I expect in later stages the shortcut edges would require decision labels as well. (But this requires some assumptions about starting points).

BTW: I have proved that finding Hamiltonian path on a subgrid is NP complete (Tron AI challenge) ... based on Plasnik's prove that it's NP complete for planar deg 3 graphs. I was not thinking yet about NP completness of the MortalCoil. In the case of possivie answer ... there would be interesting generator of difficult levels. ... Now probably transformation from directed version of Plesnik's constructions would be easier.

... Hmm, either I am blind or it's difficult/impossible to make such a construction ... it could add interesting insides to the easines of solvability

I should look carefully at some levels for inspiration.

... I have added zero degree detection and heuristic for chosing starting point rather near places which were rarely visited on best fills from already tested starting points. This allows me to reach level 168 from level 0 in 2 and half hour. Not starting inside paths of degree 2 have not improved the solving time significantly. Disconnection detection and graph representation were not implemented yet.

Wow, lvl 170 ... not done after 9 hous of computation ... good time for next level of codding.

Hmmm, unconditional shortcuts gave small if any improvements so I had to add shortcuts based on assumption start is not in given region ... I hope it will help a lot, but one should be carefull in maintaining the assumption sets well ... dynamic discontinuity log^2 algorithm still not incorporated, even when no leaf producing branching factor of level 170 leads to long computations even from single start. I bet implementation of conditional shortcuts would improve the search decisions and speed much more so this was delayed.

Hmm, its unbelievable how many bugs I made when converting to conditional shortcuts ... I am debugging it for about a month and there are still bugs. Of course some of them mean better problem understanding, but I have expected to receive next unbuggy version faster to be able to start thinking about further improvements. ... no crossing solutions yet ... no discontinuity tests during the search, no "dead end tests of subgraphs", but better start/end sets filtering.

Now it fails on level 88. BTW: It's slower on almost all levels than the search which lead me to solving lvls upto 174. I hope it's thanks to preprocessing, which will pay on higher levels.

OK level 88 shows how carefull one should be when using conditional shortcuts ... the correct solution has end in conditional shortcut assumption set (on neighbouring shortcut). And the solution fill goes opposite direction through a modified path ... this almost says the conditional shortcuts could rarely be used...

Now when I think about implementing connectivity constraints, I am tending to use EulerTrees of Monika Rauch Henzinger and Tarjan variant of Top Trees of Mikkel Thorup uff ... that would use shortcuts implicitly and I could use constraints for conditional shortcuts to stop further searching if violated. The idea is to use TopTrees to detect first branching vertex on path in O(log n), and maintaining ET for a minimum spanning tree would garantee the connectivity. Search would "delete" unused nontree edges. Maintaining edge levels (and chain of (log n) ET forests) and maintaining invariant that ET tree on level i as at most n/2^i vertices finding replacements of tree edges using amortization argument that levels of edges could only increase ... and pays work with them ...

Removing as much as able edges before making next decision should lead to pruning faster...

OK ... I find next bug ... passed the 88 level and got stuck on 99. The conditional shortcuts works better then the original search on most levels till 99. The preprocessing on 99 could surely be improved.

Uff, seems after almost 2 months of debugging I got next working version ... with region path search, but without combining neighbouring regions. I have to let it run for a while before I start introducing next bugs ... advanced data structures not implemented, representation of sets is far from optimal ...