I'm taking a break from my optimization work for now, and have concentrated on something else that I already started writing a blog post about. I haven't finished that yet, though, and instead had a sudden revelation about the puzzle that I thought I'd write down.

The revelation

I woke up one night and had trouble getting back to sleep – which is something that happens far more often than I'd like – and for some reason started thinking about these puzzle solving optimizations also. And then it hit me: every solution found to the algorithm can't only be multiplied by rotating and mirroring it to other starting points, but also by reversing it.

My mind was blown. I've initially started working on the algorithm years ago, and only now realized something this obvious and simple.

The consequences

The good news is that this means every single solution doesn't reveal 8 unique solutions, but actually 16. (Mirroring doubles a solution, rotating quadruples them, and reversing doubles the amount again.)

The bad news is that I can't immediately think how this helps in narrowing down the search space efficiently. If the search starts from e.g. the grid cell (1,1), the found solutions may end in pretty much any cells except the starting point. If I reverse them, I do get 16 solutions per each found one, but I haven't at least yet come up with a good way to use these to limit the search space later.

If I e.g. find a solution starting from (1,1) and ending in (3,2), it means there is a reversed solution starting from (3,2) ending in (1,1). However, I'm not sure if it's possible to use that reversed solution to speed up the search when finding solutions from (3,2); as I want to find all solutions starting from (3,2), I'll anyway have to start the search there separately, and only realize if a particular solution has already been found (by reversing another one) when I find it again. Which means it wouldn't save time whatsoever.

Besides, if the original solution's ending point is not one of the unique starting points which the search is started from but somewhere else, the reversed solution will anyway be generated already when mirroring and rotating the minimum set of needed solutions.

What does this all mean?

So, will I make any changes to my algorithm based on this new realization? Probably not, at least yet. As stated, I don't know how to use this new knowledge.

If the idea of the algorithm was to find a single solution, I could return 16 solutions instead of 8 with very little effort. But with my current goal of finding all existing solutions, it doesn't really help — unless I also discover some new logic about what kind of solutions are possible in general.