Loopover NRG god's number upper and lower bounds

[coolcomputery]

5x5 NRG is at most 20 (empty -> AEUY) + 43 ( + BCD VWX M) + 65 ( + FG KL PQ) + 91 ( + rest of board) = 219

code + results: https://gist.github.com/coolcomputery/0a439b46ee0758310530b9b6a4cf60c8
(builds off of the code I used in my recent post on regular Loopover)

I changed the solving phases so that the last phase does the row-center column-right 3x3 instead of the central 3x3.
I also included more NRG sequences: specifically, conjugations Z*S*Z^{-1}, where cost(Z)<=14 and S is one of the following:

• a subset of some small-cycle algorithms I found a few years ago
• a commutator A*B*A^{-1}*B^{-1} of cost <=16, where both A and B are "loops" (the gripped piece starts and ends at the same place)

I only used commutators for the FG KL PQ phase; based on some preliminary testing, they don't seem to help in the last phase.

Ideally I would generate conjugations in a smarter way (a Dijkstra-like approach) instead of brute-forcing all Z, like I have in my previous post, but I haven't had the time yet to implement it in C++. There are probably many other significant improvements that can be made...

 

[coolcomputery]

5x5 NRG <= 196 = 20 (empty -> AEUY) + 43 ( + BCD VWX M) + 52 ( + FGH KL PQ) + 81 ( + rest of board)

code + results: https://gist.github.com/coolcomputery/561082974f09bbed3b1975c87724248b

• changed the solving phases again, this time by moving one piece (the "H" piece) from the last phase into the previous phase.
• replaced commutators with general loops, which massively reduces diameter in the 2nd-to-last phase
• generate conjugations in a smarter way (somewhat like Bellman-Ford)
• used all small-cycle move sequences I found a few years ago, not just some

Specifics:

• + FGH KL PQ
  • generate a list all loops of cost <=36 (a pruning table helped make this step more efficient)
  • add the small-cycle algorithms to this list
  • for all move sequences in this list that shuffle <=5 pieces, add all conjugations of them
• + rest of board: same as + FGH KL PQ, but don't generate any loops