coolcomputery
Regular
5x5 GN is at most 41 = 17 (0x0->ACKM->3x3) + 24 (3x3->3x5->5x5, syllable conjugations)
code + output: https://gist.github.com/coolcomputery/5b659addaf32c4e7f33e246d89a6f70b
Total time: ~ 7.9 days (summed across multiple threads)
This result surpasses the lower bound I noted here for 3x3->5x5, since we are allowing ourselves to temporarily break the 3x3 region.
Rewrote everything in C++ and combined syllable conjugation Dijkstra's with the older 2-phase improvement technique I did a few years ago. This time I have no move-count restrictions on the conjugations.
I also applied symmetry reduction using the order-4 group that preserves the region 3x5 \ 3x3 (represented with '*'s below):
I could have used the larger order-8 group that preserves 5x5 \ 3x3, but that would involve a tricky set cover problem similar to what was done to prove the Rubik's cube has GN 20. I might do that for larger search instances in the future.
Minor notes/optimizations:
P. S. I was not able to improve the 4x4->4x6 bound for 6x6 Loopover, as I mentioned in my previous post. I'll probably have to run 2-phase improvement on 4x4->4x6->6x6.
code + output: https://gist.github.com/coolcomputery/5b659addaf32c4e7f33e246d89a6f70b
Total time: ~ 7.9 days (summed across multiple threads)
This result surpasses the lower bound I noted here for 3x3->5x5, since we are allowing ourselves to temporarily break the 3x3 region.
Rewrote everything in C++ and combined syllable conjugation Dijkstra's with the older 2-phase improvement technique I did a few years ago. This time I have no move-count restrictions on the conjugations.
I also applied symmetry reduction using the order-4 group that preserves the region 3x5 \ 3x3 (represented with '*'s below):
Code:
XXX**
XXX**
XXX**
.....
.....I could have used the larger order-8 group that preserves 5x5 \ 3x3, but that would involve a tricky set cover problem similar to what was done to prove the Rubik's cube has GN 20. I might do that for larger search instances in the future.
Minor notes/optimizations:
- the SSSP algorithm I am using is basically Dial's algorithm but edges are relaxed in a different order
- technically we want to do SDSP (single-*destination* shortest paths), since we want to create a path *from* every state *to* the solved state, so I have rewrote this algorithm to reflect that
- WLOG we can further restrict syllable conjugations \( A^{-1}BA \) such that:
- \( A \) *only* shifts rows/columns that disrupt the starting region
- e.g. for the 3x3->3x5 phase, \( A \) can only shift the first 3 rows (or first 3 columns). If not, we could write \( A=A' S \) where \( S \) does not disrupt the 3x3, and then \( A^{-1}BA=S^{-1} (A'^{-1} B A') S \) (because \( A'S=SA' \)), so \( A^{-1}BA \) would be obtainable by composing a cheaper syllable conjugation with several single-cost moves that do not disrupt the 3x3, without increasing the total move-cost.
- \( A \) has minimal move-cost out of all \( A*G \), where \( G \) shifts all rows by an equal amount
- \( A \) *only* shifts rows/columns that disrupt the starting region
- I realized that I forgot to add some input validation checks in my code, but the input I used satisfies those checks anyway so the results should be correct. This is the only reason I am still releasing my code in a gist instead of a repository.
P. S. I was not able to improve the 4x4->4x6 bound for 6x6 Loopover, as I mentioned in my previous post. I'll probably have to run 2-phase improvement on 4x4->4x6->6x6.
Last edited:
