# Loopover NRG god's number upper and lower bounds



## coolcomputery (Jun 11, 2021)

Loopover NRG is like Loopover, but you can only "grip" a certain fixed piece at all times, i.e. you can only slide the row or the column that that piece is in. Here is an example solve (not by me).

Although there's been research on God's number for regular Loopover, I haven't found any for Loopover NRG, besides this page showing that God's number for 3x3 NRG is 12, so I've decided to do some. Code is at https://github.com/coolcomputery/Loopover-NRG-Upper-Bounds.

The current method of solving a Loopover NRG board is by solving a few pieces at a time, using setup moves, 3-cycles, and "double-swappers", which permutes a set of 4 pieces ABCD into BADC.
Letting X_(n) represent XX...X repeated n times, where X represents the moves down, right, up, or left, and comm(a, b) represent the commutator a b inverse(a) inverse(b), I used the following commutators (with the exception that the first 3-cycle is technically not a commutator):
3-cycles:

for even N: (comm(R_(N/2), D_(N/2)))_2
for N=5: comm(RURULDRDLL, DDLDRULURU)
for N>=5: comm(LURDLULDRR, RRDRULDLUL)
double-swappers (for N>=5):

comm(a8, b8)
comm(a8, inv(b8))
comm(inv(a8), inv(b8))
where a8=URULDRDL and b8=DLDRULUR

To actually use these commutators to solve a board, we also need to use setup moves. Let S3(N) (S4(N)) equal the maximum possible number of moves needed to permute an arbitrary 3- (4-) tuple of tiles along a cycle (double-swap) permutation, including both the commutators and setup moves. Using a BFS-like search (really an optimized Dijkstra's shortest path tree) for various values of N yields:

```
N  S3  S4
  4  36  72 (the double-swapper algorithms presented above do not work on 4x4 boards, but we can artificially make a double-swapper algorithm by applying two 3-cycles)
  5  64  56
  6  56  62
  7  68  66
  8  72  72
  9  76  76
 10  80  80
(This was the farthest my code got. Trying N=11 resulted in a "java.lang.OutOfMemoryError: Java heap space" exception.)
```

To actually solve a Loopover NRG scramble, we have to do the following:

move the gripped piece to where it is supposed to be
repeatedly solve a few pieces at a time using 3-cycles and double-swappers
The first step takes at most 2*floor(N/2) moves. For the second step, note that any solvable scramble must have the unsolved pieces be put in a even permutation after the gripped piece is where it is supposed to be. Suppose there are K unsolved pieces. Let P be the composite permutation that must be applied on all the unsolved pieces. P can be decomposed into a set of cycles. Consider the following cases:

if there is a cycle of size 3, we can apply a 3-cycle to solve all 3 of those pieces at once
if there is a cycle of size >=4, we can always apply either a 3-cycle or a double-swapper to solve exactly 2 pieces in this cycle and thus decrease its size by 2
otherwise, P is a purely set of 2-cycles (swaps); in this case, there must be an even number of 2-cycles, so K must be a multiple of 4: then we can apply K/4 double-swappers to completely solve P. For worst-case analysis, we can completely ignore this case.
For W(N,K)=the worst-case number of moves to solve an arbitrary K-tuple of pieces in an NxN board, we have W(N,K)=W(N,K-2)+min(S3(N),S4(N)), with base cases W(N,3)=S3(N) and W(N,4)=S4(N). Thus, God's number for NxN Loopover NRG is 2*floor(N/2)+max_{3<=K<=N*N-1} (W(N,K)).

For a lower bound, there are at most 4*3^(m-1) scrambles that require m moves to solve, since there are 4 possibilities for the first move and 3 possibilities for each next move that does not undo the previous move. A lower bound is thus the smallest m s.t. 1+4+4*3+...+4*3^(m-1)=2*3^m-1 >= (N^2)!/2. Our final results are:

```
N      God's number lower bound      God's number upper bound
  4                            27                           256
  5                            52                           628
  6                            86                           958
  7                           131                          1526
  8                           186                          2240
  9                           252                          2972
 10                           330                          3930
```
As can be seen, there is a huge gap between the lower and upper bounds. It is probably possible to have a tighter bound on W(N,K) by considering sets of cycle lengths and doing more brute-force calculations.


----------



## coolcomputery (Jun 14, 2021)

New lower bounds:
Using a similar technique by xyzzy for regular Loopover, we can describe any NRG scramble as a list of "syllables", where a syllable is a run of Ds, Rs, Ls, or Us, and syllables alternate between horizontal (Rs and Ls) and vertical (Ds and Us). Then, for a NxN board, let S be the array where S(m)=# of possible syllables that requires m moves to be described. Note that for all m>floor(N/2), S(m)=0, so by ignoring those m, S has bounded length, ex. for N=4, S=[0,2,1]; we disallow 0-length syllables.
This improves on the previous lower bound, because we avoid sequences that contain runs of the same move that are longer than floor(N/2), which render such sequences redundant.

Now let \(dp(m,k)=\)# of move sequences consisting of m moves and k syllables, where the first syllable is horizontal. Then \(dp(0,0)=1, dp(m,k)=0\) if m<k or (m>0 and k==0) or m<0, and \( dp(m,k)=\sum_{1\le n < len(S)} S[n] dp(m-n,k-1) \) otherwise. (It can also be shown that dp(m,k) equals the coefficient of the \( x^m \) term in the expansion of \( (\sum_{1\le n < len(S)} S[n] x^n)^k \).)
Letting T(m)=# of move sequences of length <=m, we have \( T(m)=1+2\sum_{1\le k\le n\le m} dp(n,k) \). The resulting lower bound of God's number of NxN NRG is the smallest m s.t. T(m)>=(N^2)!/2, yielding:

```
4   33
  5   57
  6   91
  7  134
  8  189
  9  254
10  332
11  421
12  524
13  638
14  766
15  907
16 1062
17 1230
18 1413
19 1609
20 1820
```



Spoiler: Source code:





```
//https://github.com/coolcomputery/Loopover-NRG-Upper-Bounds/blob/main/LoopoverNRGLowerBound.java
import java.util.*;
import java.math.BigInteger;
public class LoopoverNRGLowerBound {
    private static int lower_bound(int N) {
        int[] S=new int[N/2+1];
        for (int i=1; i<=N/2; i++)
            S[i]=2*i==N?1:2;
        List<BigInteger[]> dp=new ArrayList<>();
        //dp(m,k)=# canonical move sequences w/ m moves, k syllables, first syllable is horizontal
        //dp(0,0)=1
        //dp(m,k)=SUM_{n=1 to len(S)-1} dp(m-n,k-1)*S[n]
        //let T(m)=# canonical move seq.s w/ <=m moves
        //then T(m)=1+2*(SUM_{1<=k<=n<=m} dp(n,k))
        BigInteger tot=BigInteger.ONE, target=BigInteger.ONE;
        for (int i=2; i<=N*N; i++)
            target=target.multiply(new BigInteger(""+i));
        target=target.divide(new BigInteger("2"));
        for (int m=0;; m++) {
            BigInteger[] row=new BigInteger[m+1];
            dp.add(row);
            for (int k=0; k<=m; k++) {
                if (k==0)
                    row[0]=m==0?BigInteger.ONE:BigInteger.ZERO;
                else {
                    row[k]=BigInteger.ZERO;
                    for (int n=1; n<=m && n<S.length; n++)
                        if (m-n>=k-1)
                            row[k]=row[k].add(dp.get(m-n)[k-1].multiply(new BigInteger(""+S[n])));
                }
                if (m>0)
                    tot=tot.add(row[k].multiply(new BigInteger("2")));
            }
            if (tot.compareTo(target)>=0) {
                return m;
            }
        }
    }
    public static void main(String[] args) {
        for (int N=4; N<=20; N++)
            System.out.printf("%3d%5d%n",N,lower_bound(N));
    }
}
```




*Note:* It is possible to refine the DP by further separating each canonical move sequence by the net row and column displacement they do on the gripped piece. *However, this does not improve any lower bounds.* Let \(dp(m,k,t,d_r,d_c)=\)# of canonical move sequences consisting of m moves and k syllables, with the last syllable of type \(t\) (0 being horizontal, 1 being vertical), net row displacement of \(d_r\) and net column displacement of \(d_c\) on the gripped piece. Then \(dp(m,k,t,d_r,d_c)=\sum_{s\in S(t)} dp(m-L(s),k-1,1-t,d_r-R(s),d_c-C(s))\), where \(S(t)\) is the set of all type \(t\) syllables, \(L(s)\) is the length of a syllable \(s\), \(R(s)\) is the net row displacement of \(s\), and \(C(s)\) is the net column displacement of \(s\), Base cases apply.


Spoiler: Code + stdout





```
import java.util.*;
import java.math.BigInteger;
public class LoopoverNRGLower {
    private static int mod(int n, int k) {
        return (n%k+k)%k;
    }
    private static int lowerBound2(int N) {
        //dp(m,k,t,dr,dc)=# canonical move sequences w/ m moves, k syllables,
        //  last syllable is type t (t=0: horizontal, t=1: vertical)
        //  net displacement of gripped piece is <dr,dc>
        //  i.e. dr rows down (mod N), dc columns right (mod N)
        //let S(t) be the set of all syllables of type t
        //for a syllable s:
        //  L(s)=length of s
        //  R(s)=net row displacement of gripped piece under s
        //  C(s)=same but column displacement
        //dp(m,k,t,dr,dc)=SUM_{s in S(t)} dp(m-L(s),k-1,1-t,dr-R(s),dc-C(s))
        //# move sequences w/ <=M moves, net displacement <dr,dc>=1 + SUM_{t; 1<=k<=m<=M} dp(m,k,t,dr,dc)
        List<BigInteger[][][][]> dp=new ArrayList<>();
        BigInteger target=BigInteger.ONE;
        for (int i=2; i<=N*N; i++)
            target=target.multiply(new BigInteger(""+i));
        target=target.divide(new BigInteger("2")).divide(new BigInteger(""+(N*N)));
        //System.out.println("target="+target);
        BigInteger[][] tot=new BigInteger[N][N];
        for (int dr=0; dr<N; dr++)
            for (int dc=0; dc<N; dc++)
                tot[dr][dc]=dr==0&&dc==0?BigInteger.ONE:BigInteger.ZERO;
        for (int m=0;; m++) {
            BigInteger[][][][] ndp=new BigInteger[m+1][2][N][N];
            dp.add(ndp);
            for (int k=0; k<=m; k++)
            for (int t=0; t<2; t++)
            for (int dr=0; dr<N; dr++)
            for (int dc=0; dc<N; dc++) {
                if (k==0)
                ndp[k][t][dr][dc]=m==0&&dr==0&&dc==0?BigInteger.ONE:BigInteger.ZERO;
                else {
                    BigInteger sum=BigInteger.ZERO;
                    if (t==0) {
                        for (int fdc=1; fdc<N; fdc++) {
                            //fdc=C(s), i.e. the column displacement under s
                            int len=Math.min(fdc,N-fdc);
                            if (m-len>=k-1)
                                sum=sum.add(dp.get(m-len)[k-1][1-t][dr][mod(dc-fdc,N)]);
                        }
                    }
                    else {
                        for (int fdr=1; fdr<N; fdr++) {
                            //fdr=R(s)
                            int len=Math.min(fdr,N-fdr);
                            if (m-len>=k-1)
                                sum=sum.add(dp.get(m-len)[k-1][1-t][mod(dr-fdr,N)][dc]);
                        }
                    }
                    ndp[k][t][dr][dc]=sum;
                }
                if (m>0) tot[dr][dc]=tot[dr][dc].add(ndp[k][t][dr][dc]);
            }
            BigInteger min=tot[0][0];
            for (int dr=0; dr<N; dr++)
            for (int dc=0; dc<N; dc++) {
                BigInteger n=tot[dr][dc];
                if (min.compareTo(n)<0) min=n;
            }
            //System.out.printf("M=%d,min=%d%n",m,min);
            if (min.compareTo(target)>=0) return m;
        }
    }
    /*private static int lowerBound(int N) {
        int[] S=new int[N/2+1];
        for (int i=1; i<=N/2; i++)
            S[i]=2*i==N?1:2;
        List<BigInteger[]> dp=new ArrayList<>();
        //dp(m,k)=# canonical move sequences w/ m moves, k syllables, first syllable is horizontal
        //dp(0,0)=1
        //dp(m,k)=SUM_{n=1 to len(S)-1} dp(m-n,k-1)*S[n]
        //let T(m)=# canonical move seq.s w/ <=m moves
        //then T(m)=1+2*(SUM_{1<=k<=n<=m} dp(n,k))
        BigInteger tot=BigInteger.ONE, target=BigInteger.ONE;
        for (int i=2; i<=N*N; i++)
            target=target.multiply(new BigInteger(""+i));
        target=target.divide(new BigInteger("2"));
        System.out.println("target="+target);
        for (int m=0;; m++) {
            BigInteger[] row=new BigInteger[m+1];
            dp.add(row);
            for (int k=0; k<=m; k++) {
                if (k==0)
                    row[0]=m==0?BigInteger.ONE:BigInteger.ZERO;
                else {
                    row[k]=BigInteger.ZERO;
                    for (int n=1; n<=m && n<S.length; n++)
                        if (m-n>=k-1)
                            row[k]=row[k].add(dp.get(m-n)[k-1].multiply(new BigInteger(""+S[n])));
                }
                if (m>0)
                    tot=tot.add(row[k].multiply(new BigInteger("2")));
            }
            System.out.printf("M=%d,tot=%d%n",m,tot);
            if (tot.compareTo(target)>=0) return m;
        }
    }*/
    public static void main(String[] args) {
        for (int N=4; N<=10; N++)
            System.out.printf("%3d%5d%n",N, lowerBound2(N));
    }
}
```


```
stdout:

  4   33
  5   57
  6   91
  7  134
  8  189
  9  254
 10  332

Process finished with exit code 0
```


----------



## rokicki (Jun 14, 2021)

This sequence is optimal on a 4x4 Loopover NRG, which shows for that size that 37 is a lower bound:

H H V H' V H H V H V H' V' H H V H V V H H V' H H V H' V H H V H' V H' V' H' V H' V


----------



## coolcomputery (Jun 14, 2021)

rokicki said:


> This sequence is optimal on a 4x4 Loopover NRG, which shows for that size that 37 is a lower bound:
> 
> H H V H' V H H V H V H' V' H H V H V V H H V' H H V H' V H H V H' V H' V' H' V H' V


How did you find this sequence?
Also, does it create a scramble like this (I did H=right, V=down)?

```
ABCD     DPIE
EFGH --> OKGH
IJKL     MJAL
MNOP     FCBN
```


----------



## rokicki (Jun 14, 2021)

I'm using twsearch and a loopover NRG "ksolve" file. This puzzle is a group; instead of moving the "A" row or column, just move all the *other* rows/columns keeping the key piece fixed, and add an orbit that just gives the horizontal and vertical position of the A.

Anyway, I just ran for a few hours with the -S option (solve "random" positions; I solved about 20,000) and picked off the highest I saw. I'd
be surprised if there's not a distance-38 position.

I'll work on verifying the actual position that results . . .

[added]

I can't verify your resulting position. Which piece do you visualize as gripped? If it's A, then the total movement of that piece between the two boards is +2 horizontally and +2 vertically, which is even, which can't happen for an odd-length scramble.


----------



## coolcomputery (Jun 14, 2021)

rokicki said:


> I'm using twsearch and a loopover NRG "ksolve" file. This puzzle is a group; instead of moving the "A" row or column, just move all the *other* rows/columns keeping the key piece fixed, and add an orbit that just gives the horizontal and vertical position of the A.
> 
> Anyway, I just ran for a few hours with the -S option (solve "random" positions; I solved about 20,000) and picked off the highest I saw. I'd
> be surprised if there's not a distance-38 position.
> ...


Oops, I had F gripped instead of A (it's the default gripped piece on https://loopover.xyz/). Here's the scramble again, this time with A gripped:

```
ABCD     FBCJ
EFGH --> EPGL
IJKL     NMIA
MNOP     KHDO
```


----------



## rokicki (Jun 14, 2021)

coolcomputery said:


> Oops, I had F gripped instead of A (it's the default gripped piece on https://loopover.xyz/). Here's the scramble again, this time with A gripped:
> 
> ```
> ABCD     FBCJ
> ...


That looks right.


----------



## rokicki (Jun 14, 2021)

Found a distance-38 position. Just ran the optimal solver a little longer.

H H V H V' H V H' V' H' V' H V H' V H' V' H' V' H' V' H V H' V H' V' H V' H V' H' V' H V V H' V'


----------



## coolcomputery (Jul 2, 2021)

*New upper bounds:*
I added permutation "symmetries" to the 3-cycle and double-swap algorithms. Code is at https://github.com/coolcomputery/Loopover-NRG-Upper-Bounds.
Basically, every algorithm *A* describes an action (L,P) for some array L of locations on the NxN board and a permutation P, where for each i *A* moves the piece at location L(i) to location L(P(i)). What I mean by "adding permutation symmetries" is that for a fixed P, it is possible to permute the array L to (possibly several) different arrays L' such that (L',P) and (L,P) represent equivalent actions. For example, if L=[17,18,19] and P=[1,2,0], then a possible L' is [18,19,17] or [19,17,18].
We can take advantage of these "symmetries" to use fewer setup moves when cycling a set of pieces. For example, if we want to cycle A-->B-->C-->A and we have an algorithm describing the action ([17,18,19],[1,2,0]), we don't have to move A to location 17, B to 18, and C to 19, we could also send A to 18, B to 19, and C to 17, or A to 19, B to 17, and C to 18. This leads to the following new upper bounds on the number of moves needed to 3-cycle an arbitrary 3-tuple of pieces and double-swap an arbitrary 4-tuple of pieces:

```
N  S3  S4
  4  36  72
  5  60  52
  6  54  60
  7  66  64
  8  68  70
  9  70  72
10  72  78
```
... which lead to new upper bounds on NxN NRG GNs:

```
N      God's number upper bound
  4                           256
  5                           584
  6                           924
  7                          1480
  8                          2116
  9                          2740
10                          3538
```
*UPDATE (2021-07-02): Added new commutators found with a brute-force search.* I also reduced some redundant moves within the commutators, i.e. adjacent inverse moves, and the same move being repeated more than floor(N/2) times consecutively. New upper bounds below (also see on https://github.com/coolcomputery/Lo...mmit/da00e9be9d8aa356680a4bed721416d37c47fb74):

```
N  S3  S4      God's number upper bound
  4  36  72                           256
  5  58  52                           582
  6  54  54                           924
  7  57  60                          1320
  8  60  70                          1868
  9  64  72                          2512
 10  70  76                          3440
```


----------



## coolcomputery (Jul 3, 2021)

*New upper bound technique:*
Let C3(a,b,c) be the minimum number of moves needed to cycle locations a-->b-->c-->a and C4(a,b,c,d) be the minimum number of moves needed to swap locations a<-->b and c<-->d.

Consider for simplicity only using the 3-cycle. Suppose the piece at the location (0,0) is gripped and the piece is where it should be in a solved board, and we solve all other locations on the board one a a time. As we proceed with solving the board, let *U* be the set of all locations that are not yet guaranteed to be solved.
Suppose we want to solve the location t=*U*[0] in *U.* For every possible location x!=t that the piece that needs to be at location t could actually be in, we want to find the best way to move location x to location t using a 3-cycle. For this, we find a piece y s.t. C3(x,t,y) is minimized. Then we take the worst case of this quantity over all x, i.e. we evaluate \( max_{x} (min_{y} C3(x,t,y)) \) (it is assumed that in this expression, we only consider C3(x,t,y) s.t. x, t, and y are all mutually distinct). Then we remove t from *U* and repeat, until *U* has only two elements left. Because we assumed that the initial scramble had to be solvable on an NRG board, these last two pieces must be solved (or else they would be swapped, meaning the scramble describes an odd permutation, which is impossible).

Now, for N>=5, consider adding in the double-swapper. As before, let *U* be the list of all locations that are not yet guaranteed to be solved. If |*U*|<=3, we default to the strategy above. Otherwise, we solve two locations at once: ta=*U*[0] and tb=*U*[1]. Let a and b be the locations of the pieces that need to be at location ta and tb respectively. There are 6 cases to consider, each of which leads to the following quantities:
- a!=ta or tb, and b!=ta or tb --> \( C4(a,ta,b,tb) \)
- a==tb and b==ta --> \(min_{x,y} C4(ta,tb,x,y) \)
- a==ta and b!=ta or tb --> \( min_{x,y} C4(b,tb,x,y)\), or \( min_x C3(b,tb,x) \) if |*U*|<5
- b==tb and a!=ta or tb --> \( min_{x,y} C4(a,ta,x,y)\), or \( min_x C3(a,ta,x) \) if |*U*|<5
- a==tb and b!=ta or tb --> \( C3(b,tb,ta) \)
- b==ta and a!=ta or tb --> \( C3(a,ta,tb) \)
We then take the max of all these quantities over all possible a and b, remove ta and tb from *U*, and repeat. Doing so yields an upper bound on solving any NxN board by solving its pieces in the order determined by *U*. It remains to find the list *U *that minimizes this upper bound. For this, I used simulated annealing, albeit with very few iterations, since the time complexity of a single iteration (i.e. calculating the upper bound for fixed N and *U*) is about \( O(N^8) \). We get the following new NxN NRG God's number upper bounds for N>=5 (along with a worse upper bound for N=4):

```
N    GN  best sequence of locations to solve (assuming location 0 is gripped)
4   356  [2, 8, 4, 10, 14, 12, 6, 11, 3, 5, 13, 1, 7, 9, 15]
5   560  [14, 9, 2, 8, 13, 7, 18, 12, 3, 5, 6, 11, 1, 20, 21, 22, 10, 19, 17, 16, 23, 4, 24, 15]
6   830  [5, 10, 2, 25, 24, 26, 17, 16, 13, 19, 29, 30, 32, 14, 1, 15, 3, 31, 6, 20, 7, 21, 8, 22, 28, 11, 12, 33, 23, 4, 34, 35, 18, 9, 27]
7  1247  [33, 3, 34, 45, 27, 36, 22, 39, 40, 41, 37, 11, 38, 47, 32, 25, 30, 31, 18, 46, 28, 4, 10, 17, 26, 35, 16, 23, 12, 24, 48, 42, 9, 8, 7, 19, 2, 1, 5, 6, 43, 14, 21, 29, 13, 20, 44, 15]
8  1812  [5, 42, 40, 38, 29, 10, 32, 26, 12, 58, 6, 9, 46, 36, 13, 15, 17, 39, 33, 23, 21, 22, 28, 14, 4, 20, 37, 27, 16, 30, 31, 56, 19, 18, 59, 24, 3, 41, 43, 35, 52, 25, 2, 62, 50, 48, 1, 53, 49, 61, 34, 44, 45, 51, 11, 47, 57, 54, 55, 8, 7, 60, 63]
9  2428  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 14, 15, 16, 17, 18, 19, 20, 13, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 58, 47, 48, 49, 50, 51, 52, 53, 54, 55, 63, 57, 46, 59, 60, 61, 62, 56, 64, 65, 66, 67, 68, 69, 70, 71, 73, 72, 74, 75, 76, 77, 78, 79, 80]
10  3216  [38, 26, 3, 4, 5, 6, 7, 74, 9, 10, 11, 12, 13, 14, 15, 34, 17, 18, 33, 20, 21, 22, 23, 24, 25, 2, 27, 28, 42, 30, 31, 32, 19, 39, 35, 54, 37, 16, 1, 40, 41, 29, 43, 44, 45, 46, 47, 48, 49, 60, 51, 52, 53, 36, 55, 68, 57, 58, 59, 50, 56, 62, 63, 64, 65, 66, 83, 61, 69, 70, 71, 72, 96, 8, 75, 76, 77, 78, 73, 87, 81, 82, 67, 84, 85, 86, 97, 88, 89, 90, 91, 92, 93, 94, 95, 79, 80, 98, 99]
```
Note: In a NxN board, the location at row r, column c (with 0-indexed rows and columns) is assigned the number r*N+c.
Code for this upper bound algorithm and simulated annealing is at https://github.com/coolcomputery/Lo...mmit/1dbcb4e4c555ed6dca46b8c997e91c5083ae47e1.


----------



## coolcomputery (Jul 8, 2021)

*A much better upper bound technique:*
This one comes partially from xyzzy via a Discord post. As in regular Loopover, we can solve a NRG board by extending a block of solved pieces. Unlike in regular Loopover, when extending an existing block to a bigger block, the initial block must leave at least 3 rows and 2 columns, or at least 2 rows and 3 columns, free, In order for BFS trees to not take an unreasonable amount of running time and memory, this restriction forces us
to switch back to "permuters" (3-cycles and double-swappers) to solve the last several pieces of the board.
In each line of the BFS distributions below, there are two numbers at each depth of each BFS instead of one. The first is the total number of states at that depth. The second is the total number of states that have the gripped piece in the same place it would be in a solved position. For example, in 4x4 NRG with the A piece gripped and the BFS tree set to solving the pieces KLOP, the line "4:48,6" means that at depth 4, there are 48 total states of the pieces AKLOP, and 6 states of AKLOP where A is at the same place it would be in the solved board.
Combining repeated block-building and the simulated annealing from the previous post yields the new GN upper bounds for 4x4-6x6 NRG:
*4x4 NRG: 199
5x5 NRG: 398
6x6 NRG: 596*
Solving phases used (A is the gripped piece):
4x4: KLOP --> permuters
5x5: MNRS --> OTWXY --> permuters
6x6 (where the solved board starts as "1,2,3,4,5//6,7,8,..."): 15,16,21,22 --> 17,18,23,24 --> 27,28,29,30 --> 33,34,35,36 --> permuters
Code is at https://github.com/coolcomputery/Lo...cc5953f223d07197d74e899/LoopoverNRGUpper.java.


Spoiler: stdout





```
K=3,diameter=36,BFS time=23
4x4: (1111,1111)-->(1100,1100)
  *0   1   2   3
   4   5   6   7
   8   9 '10 '11
  12  13 '14 '15
[0, 10, 11, 14, 15]
ncombos=524160, nreturningcombos=32760
0:1,1
1:4,0
2:9,0
3:20,0
4:48,6
5:114,0
6:266,28
7:622,0
8:1447,221
9:3336,0
10:7525,792
11:16578,0
12:35147,4859
13:68230,0
14:112077,13304
15:137592,0
16:101783,13209
17:35554,0
18:3777,340
19:30,0
#reached=524160, #returningreached=32760
D=20, Dreturning=19
total time=660
N=4
T=11
NREPS=1000000
    REPS    ACCN    GN temp
       0       0   280 1.0
  100000   19174   256 0.9
  200000   36625   256 0.8
  300000   53320   254 0.7
  400000   68564   256 0.6
  500000   82177   254 0.5
  600000   94752   254 0.4
  700000  106257   254 0.30000000000000004
  800000  117279   254 0.19999999999999996
  900000  128098   254 0.09999999999999998
1000000  138807   254 0.0
bestScr=254, best list of pieces to solve=[9, 2, 1, 7, 3, 5, 8, 12, 13, 4, 6]
SA time=37302
simplescr=180
GN<=19+180=199
K=3,diameter=58,BFS time=28
K=4,diameter=52,BFS time=244
5x5: (11111,11111)-->(11001,11001)
  *0   1   2   3   4
   5   6   7   8   9
  10  11 '12 '13  14
  15  16 '17 '18  19
  20  21  22  23  24
[0, 12, 13, 17, 18]
ncombos=6375600, nreturningcombos=255024
0:1,1
1:4,0
2:8,0
3:16,0
4:40,0
5:104,0
6:240,8
7:592,4
8:1528,64
9:3920,212
10:9800,340
11:23984,996
12:57912,2240
13:136892,5472
14:309456,12496
15:646682,25882
16:1173142,48242
17:1654246,67854
18:1516972,62272
19:712727,25443
20:123107,3387
21:4190,110
22:37,1
#reached=6375600, #returningreached=255024
D=23, Dreturning=23
total time=4472
5x5: (11001,11001)-->(11000,11000)
  *0   1   2   3   4
   5   6   7   8   9
  10  11   X   X '12
  13  14   X   X '15
  16  17 '18 '19 '20
[0, 12, 15, 18, 19, 20]
ncombos=39070080, nreturningcombos=1860480
0:1,1
1:4,0
2:11,0
3:20,0
4:24,6
5:36,0
6:70,6
7:136,0
8:200,38
9:336,0
10:594,74
11:1096,0
12:1709,272
13:2936,0
14:4902,682
15:8752,0
16:13957,2078
17:24120,0
18:39098,5589
19:67838,0
20:107156,15405
21:182448,0
22:285482,40220
23:477846,0
24:728004,100468
25:1183144,0
26:1727982,229985
27:2657712,0
28:3563167,435298
29:4920994,0
30:5552351,577547
31:6218922,0
32:5004940,375910
33:3822500,0
34:1657029,74259
35:681336,0
36:112031,2623
37:20174,0
38:946,19
39:76,0
#reached=39070080, #returningreached=1860480
D=40, Dreturning=39
total time=30891
N=5
T=15
NREPS=1000000
    REPS    ACCN    GN temp
       0       0   366 1.0
  100000   16737   338 0.9
  200000   31950   338 0.8
  300000   45145   344 0.7
  400000   57519   342 0.6
  500000   69496   338 0.5
  600000   80087   338 0.4
  700000   90592   338 0.30000000000000004
  800000   99300   338 0.19999999999999996
  900000  107795   338 0.09999999999999998
1000000  116370   338 0.0
bestScr=338, best list of pieces to solve=[8, 9, 20, 1, 16, 21, 10, 5, 4, 3, 6, 2, 11, 7, 15]
SA time=978508
simplescr=370
GN<=22+38+338=398
K=3,diameter=54,BFS time=24
K=4,diameter=54,BFS time=1081
6x6: (111111,111111)-->(110011,110011)
  *0   1   2   3   4   5
   6   7   8   9  10  11
  12  13 '14 '15  16  17
  18  19 '20 '21  22  23
  24  25  26  27  28  29
  30  31  32  33  34  35
[0, 14, 15, 20, 21]
ncombos=45239040, nreturningcombos=1256640
0:1,1
1:4,0
2:8,0
3:14,0
4:31,0
5:78,0
6:184,4
7:420,0
8:1012,24
9:2582,0
10:6639,244
11:16716,0
12:40921,2382
13:98136,0
14:230670,11803
15:528798,0
16:1164733,64349
17:2406704,0
18:4487356,249145
19:7178372,0
20:9322076,549493
21:9252170,0
22:6554783,351064
23:3036946,0
24:807570,28088
25:98562,0
26:3535,43
27:18,0
28:1,0
#reached=45239040, #returningreached=1256640
D=29, Dreturning=27
total time=37590
6x6: (110011,110011)-->(110011,110000)
  *0   1   2   3   4   5
   6   7   8   9  10  11
  12  13   X   X '14 '15
  16  17   X   X '18 '19
  20  21  22  23  24  25
  26  27  28  29  30  31
[0, 14, 15, 18, 19]
ncombos=24165120, nreturningcombos=755160
0:1,1
1:4,0
2:10,0
3:21,0
4:39,2
5:64,0
6:91,6
7:126,0
8:196,23
9:362,0
10:742,84
11:1531,0
12:3070,287
13:5965,0
14:11380,1151
15:21547,0
16:40527,3840
17:75467,0
18:138762,13258
19:252224,0
20:451536,41878
21:785155,0
22:1300002,113065
23:2005849,0
24:2814359,212787
25:3493575,0
26:3745575,226183
27:3405079,0
28:2594011,115332
29:1648415,0
30:865890,25723
31:363000,0
32:113288,1528
33:23987,0
34:3080,12
35:189,0
36:1,0
#reached=24165120, #returningreached=755160
D=37, Dreturning=35
total time=14525
6x6: (110011,110000)-->(110001,110000)
  *0   1   2   3   4   5
   6   7   8   9  10  11
  12  13   X   X   X   X
  14  15   X   X   X   X
  16  17 '18 '19 '20 '21
  22  23  24  25  26  27
[0, 18, 19, 20, 21]
ncombos=11793600, nreturningcombos=421200
0:1,1
1:4,0
2:8,0
3:10,0
4:9,0
5:9,0
6:12,3
7:20,0
8:34,2
9:48,0
10:61,7
11:84,0
12:125,11
13:178,0
14:238,26
15:319,0
16:433,37
17:580,0
18:785,87
19:1103,0
20:1573,155
21:2222,0
22:3109,314
23:4327,0
24:5959,592
25:8144,0
26:11131,1083
27:15180,0
28:20603,2065
29:27961,0
30:37958,3749
31:51156,0
32:68182,6588
33:90056,0
34:117822,11089
35:152211,0
36:193883,17966
37:243377,0
38:301019,26634
39:366881,0
40:440971,38469
41:522668,0
42:609763,50989
43:698355,0
44:782619,62349
45:854527,0
46:905091,66875
47:925602,0
48:907187,60402
49:846149,0
50:746215,42719
51:616944,0
52:473073,21599
53:332022,0
54:209535,6571
55:115351,0
56:53324,786
57:20002,0
58:5878,32
59:1288,0
60:199,0
61:22,0
#reached=11793600, #returningreached=421200
D=62, Dreturning=59
total time=5701
6x6: (110001,110000)-->(110000,110000)
  *0   1   2   3   4   5
   6   7   8   9  10  11
  12  13   X   X   X   X
  14  15   X   X   X   X
  16  17   X   X   X   X
  18  19 '20 '21 '22 '23
[0, 20, 21, 22, 23]
ncombos=5100480, nreturningcombos=212520
0:1,1
1:4,0
2:9,0
3:12,0
4:11,2
5:12,0
6:18,1
7:25,0
8:31,5
9:42,0
10:61,6
11:81,0
12:104,13
13:145,0
14:201,23
15:255,0
16:324,36
17:442,0
18:598,72
19:770,0
20:996,108
21:1319,0
22:1732,207
23:2250,0
24:2948,326
25:3880,0
26:5051,580
27:6514,0
28:8381,929
29:10761,0
30:13766,1535
31:17539,0
32:22290,2429
33:28303,0
34:35793,3972
35:45059,0
36:56661,6096
37:70935,0
38:87843,9402
39:107514,0
40:130237,13384
41:155956,0
42:184478,18696
43:215912,0
44:249666,24239
45:284038,0
46:317081,29676
47:346940,0
48:370319,32230
49:382865,0
50:381623,30336
51:364751,0
52:330906,22468
53:281100,0
54:220684,11755
55:157296,0
56:99730,3513
57:55134,0
58:25695,454
59:9692,0
60:2889,26
61:683,0
62:112,0
63:11,0
64:1,0
#reached=5100480, #returningreached=212520
D=65, Dreturning=61
total time=2227
N=6
T=19
NREPS=1000000
    REPS    ACCN    GN temp
       0       0   442 1.0
  100000   22419   424 0.9
  200000   42405   426 0.8
  300000   59163   428 0.7
  400000   72374   424 0.6
  500000   82732   418 0.5
  600000   90516   416 0.4
  700000   97203   416 0.30000000000000004
  800000  103617   416 0.19999999999999996
  900000  110153   416 0.09999999999999998
1000000  116523   416 0.0
bestScr=416, best list of pieces to solve=[24, 13, 25, 3, 19, 12, 31, 18, 4, 1, 5, 2, 6, 9, 7, 10, 30, 8, 11]
SA time=2714940
simplescr=486
GN<=28+34+58+60+416=596

Process finished with exit code 0
```




*UPDATE (2021-07-08): *Changed the block solving so that the gripped piece is not unnecessarily brought back to where it would be in the solved board until after the last stage of block solving is complete. Also, used better phases for block solving:
4x4 NRG: GN<=*168*, phases: JKLNOP --> permuters
5x5 NRG: GN<=*359*, phases: LMQR --> NS --> OTVWXY --> permuters
New code + stdout at https://github.com/coolcomputery/Lo...32959127bff928cc308194f/LoopoverNRGUpper.java

*UPDATE (2021-07-10):* Added a few more 3-cycles for even N, as well as "rotated" versions of X-cycle algorithms. Given any X-cycle M=[M[0]...M[L-1]], any rotated version of the algorithm [M[a]...M[L-1] M[0]...M[a-1]] can be written as S M inv(S), where S=inv([M[0]...M[a-1]). Thus, any rotated version of an X-cycle is itself an X-cycle of the same length, but for which the locations of the cycled pieces are different. This yields the following new upper bounds (code at https://github.com/coolcomputery/Lo...0c5763062e301cdb3e40a83e79e0404ea84257c5742e6):
4x4 NRG: 24+136=*160*
5x5 NRG: 21+24+66+232=343 (worse than xyzzy's upper bound of 282)
6x6 NRG: 28+34+58+60+400=*580

UPDATE (2021-07-11): *Found a new 30-move 2,2 cycle RUULURDLDRDLDRULUURULDRDLDRDLU (works for N>=5) and a new 32-move 3-cycle RDLUURDLDLURDRULLDRUULDRDRULDLUR (works for N>=4). The code I used to find these algorithms is at https://github.com/coolcomputery/Lo...7ad16930c4aed/LoopoverNRGAlgorithmFinder.java.
However, this only decreases the 5x5 NRG GN upper bound to 21+24+66+216=327 (code+stdout), still worse than xyzzy's bound of 282.


----------



## xyzzy (Jul 9, 2021)

New 5×5 NRG upper bound: 330 moves 282 moves.

Unlike coolcomputery, I'll be using the central piece, M, as the gripped piece, for no particular reason other than convenience.

*Phase 1*: Solve AEUY (the corners) and bring M to the home position.

This has \( 25!/20!=6375600 \) positions, which is very manageable.


Spoiler: Phase 1 distribution



Note: This matches coolcomputery's output, as it should.

```
distance 0: 1 nodes
distance 1: 4 nodes
distance 2: 8 nodes
distance 3: 16 nodes
distance 4: 40 nodes
distance 5: 104 nodes
distance 6: 240 nodes
distance 7: 592 nodes
distance 8: 1528 nodes
distance 9: 3920 nodes
distance 10: 9800 nodes
distance 11: 23984 nodes
distance 12: 57912 nodes
distance 13: 136892 nodes
distance 14: 309456 nodes
distance 15: 646682 nodes
distance 16: 1173142 nodes
distance 17: 1654246 nodes
distance 18: 1516972 nodes
distance 19: 712727 nodes
distance 20: 123107 nodes
distance 21: 4190 nodes
distance 22: 37 nodes
```



Upper bound: 22 moves.

*Phase 2*: Solve the rest.

In this phase, we restrict movement of the gripped piece to the central 3×3 square, so the corner tiles are never moved. Any movement that starts and ends on the home tile can be (essentially uniquely) decomposed into little square loops (LURD, ULDR, URDL, RULD, RDLU, DRUL, DLUR, LDRU), which will be the primitive movement unit for this phase. All of the squares have order 15, by cycling 15 pieces. Note that it's possible for partial cancellations between squares to occur (e.g. LURD URDL = LURRDL), but we do not account for that here.

Obviously, we're not doing this all at once. 20 pieces, with 20!/2 possible permutations, is a lot. So:

*Phase 2a*: Solve BCD VWX (the top and bottom rows).



Spoiler: distribution





```
distance 0: 1 nodes
distance 1: 4 nodes
distance 2: 22 nodes
distance 3: 148 nodes
distance 4: 1006 nodes
distance 5: 6596 nodes
distance 6: 43054 nodes
distance 7: 275187 nodes
distance 8: 1628977 nodes
distance 9: 7464610 nodes
distance 10: 14854222 nodes
distance 11: 3618744 nodes
distance 12: 14629 nodes
average: 9.7093
```



Upper bound: 12 squares = 48 moves.

*Phase 2b*: Solve FKP JOT (the left and right columns).

This is done by solving the \( 14!/8!=2162160 \) possible configurations with an optimal solver. This computation used partial symmetry reduction (reducing the number of cases from \( \binom{14}6\times6!=2162160 \) to \( 787\times6!=566640 \)) and took about 13 CPU hours. (A coset solver might have made this less painful.)



Spoiler: distribution





```
0	1
2	8
4	68
6	586
8	5250
9	64
10	49309
11	1690
12	424403
13	34298
14	1405878
15	78338
16	162263
17	4
```



Upper bound: 17 squares = 68 moves.

*Phase 2c*: Solve the last eight pieces (central 3×3 square).

Unfortunately, my optimal solver can't handle this in any reasonable amount of time. (It managed to solve a 5-cycle (L N S R Q) in 20 squares = 80 moves, but that took 30 minutes and I'm not going to run a thousand scrambles that each take half an hour.) Instead, we just use 3-cycles and (2,2)-cycles. The 3-cycles are solved very quickly, and the (2,2)-cycles not so quickly. Full symmetry+antisymmetry reduction is used. (Note that the (2,2)-cycles are all automatically antisymmetric since they're self-inverse.)



Spoiler: distribution for 3-cycles





```
3-cycles (5 fixed points):
index: 1 / # symmetries: 2 / distance: 12
index: 4 / # symmetries: 2 / distance: 12
index: 7 / # symmetries: 1 / distance: 12
index: 22 / # symmetries: 1 / distance: 14
index: 5 / # symmetries: 1 / distance: 14
index: 100 / # symmetries: 1 / distance: 14
index: 139 / # symmetries: 2 / distance: 14
index: 197 / # symmetries: 2 / distance: 14
index: 142 / # symmetries: 2 / distance: 14
index: 29 / # symmetries: 2 / distance: 14
12	32
14	80
elapsed time: 0.867111
```






Spoiler: distribution for (2,2)-cycles





```
(2,2)-cycles (4 fixed points):
index: 11 / # symmetries: 2 / distance: 16
index: 3 / # symmetries: 2 / distance: 16
index: 14 / # symmetries: 2 / distance: 16
index: 33 / # symmetries: 2 / distance: 16
index: 8 / # symmetries: 2 / distance: 18
index: 53 / # symmetries: 2 / distance: 16
index: 12 / # symmetries: 4 / distance: 18
index: 60 / # symmetries: 4 / distance: 16
index: 47 / # symmetries: 4 / distance: 18
index: 62 / # symmetries: 2 / distance: 16
index: 61 / # symmetries: 4 / distance: 18
index: 59 / # symmetries: 4 / distance: 20
index: 132 / # symmetries: 2 / distance: 16
index: 134 / # symmetries: 2 / distance: 18
index: 70 / # symmetries: 2 / distance: 20
index: 157 / # symmetries: 2 / distance: 18
index: 67 / # symmetries: 2 / distance: 20
index: 195 / # symmetries: 2 / distance: 18
index: 222 / # symmetries: 4 / distance: 16
index: 201 / # symmetries: 2 / distance: 18
index: 257 / # symmetries: 4 / distance: 16
index: 259 / # symmetries: 2 / distance: 18
index: 234 / # symmetries: 2 / distance: 18
index: 263 / # symmetries: 2 / distance: 18
index: 296 / # symmetries: 4 / distance: 18
index: 319 / # symmetries: 2 / distance: 18
index: 323 / # symmetries: 2 / distance: 18
index: 343 / # symmetries: 2 / distance: 18
index: 283 / # symmetries: 4 / distance: 20
index: 782 / # symmetries: 8 / distance: 18
index: 169 / # symmetries: 4 / distance: 20
index: 5407 / # symmetries: 8 / distance: 16
index: 356 / # symmetries: 4 / distance: 20
index: 10705 / # symmetries: 16 / distance: 20
index: 1554 / # symmetries: 16 / distance: 20
16	70
18	106
20	34
elapsed time: 7524.961412
```




The even permutations on the eight pieces fall in eleven twelve cycle types (given as partitions of 8 into an even number of parts):
7+1 (solved with three 3-cycles, ≤42 squares)
6+2 (solved with (2,2)-cycle and two 3-cycles, ≤48 squares)
5+3 (solved with three 3-cycles, ≤42 squares)
4+4 (solved with (2,2)-cycle and two 3-cycles, ≤48 squares)
5+1+1+1 (solved with two 3-cycles, ≤28 squares)
4+2+1+1 (solved with (2,2)-cycle and 3-cycle, ≤34 squares)
3+3+1+1 (solved with two 3-cycles, ≤28 squares)
3+2+2+1 (solved with (2,2)-cycle and 3-cycle, ≤34 squares)
2+2+2+2 (solved with two (2,2)-cycles, ≤40 squares)
3+1+1+1+1+1 (solved with 3-cycle, ≤14 squares)
2+2+1+1+1+1 (solved with (2,2)-cycle, ≤20 squares)
1+1+1+1+1+1+1+1 (already solved, 0 squares)

Upper bound: 48 squares = 192 moves.
Overall upper bound: 22 + 48 + 68 + 192 = *330 moves*.

(I'm running a suboptimal solver on the zero-fixed-point cases in phase 2c and so far everything can be solved in 34 squares or less; if that remains true for the other cases as well, then this would reduce the upper bound to 22 + 48 + 68 + 136 = 274 moves.)

Update: Output of the suboptimal solver on the zero-fixed-point and one-fixed-point cases in phase 2c. At most 36 squares are needed for those cases, with only a few needing 35 or 36 squares. I'll try running a better solver on those. In the meantime, this reduces the upper bound for phase 2c to 36 squares = 144 moves, and the overall GN bound to *282 moves*.


----------



## coolcomputery (Jul 12, 2021)

*3-cycles and 2,2-cycles + Dijkstra's algorithm*
This is similar to doing a standard Loopover BFS, except the transitions are 3-cycles and 2,2-cycles instead of single moves, and we have to use Dijkstra's algorithm instead of BFS (since we are now evaluating shortest paths in a weighted graph).
For 4x4 NRG, if JKL NOP are already solved, then we can solve the rest of the board with at most 126 moves, yielding a new upper bound of *24+126=150*. Code and stdout is at https://github.com/coolcomputery/Lo...mmit/b65edc91b031751e002ea85b1171e26873980197.
(For 5x5 NRG, if LMNO QRST VWXY are already solved, then we can first solve F K P U in at most 87 moves, then solve the rest of the board in at most 118 moves, yielding an upper bound of 21+24+66+87+118=316.)
*UPDATE (2021-07-12):*
A better way to split 4x4 NRG solving into two phases is to first brute-force solve BD JL NP and move A to its home position in at most 25 moves, then solve the rest using 3-cycles and 2,2-cycles in at most 112 moves. *25+112=137*.


Spoiler: Phase distributions



Phase 1 (16!/9!=57657600 scrambles):
0:1
1:4
2:10
3:24
4:58
5:140
6:336
7:806
8:1937
9:4660
10:11150
11:26620
12:63338
13:150146
14:353076
15:821860
16:1870915
17:4075029
18:8095450
19:13369075
20:15528839
21:10197123
22:2902900
23:183303
24:790
25:10

Phase 2 (9!/2=181440 scrambles):
0:1
16:4
18:2
20:6
22:6
24:28
26:20
28:36
30:34
32:36
34:16
36:36
38:35
40:174
42:185
44:424
46:346
48:613
50:738
52:991
54:1031
56:1285
58:1455
60:2294
62:1829
64:3474
66:3814
68:5854
70:5368
72:7054
74:7750
76:8840
78:8986
80:11764
82:10462
84:14191
86:9867
88:12327
90:10160
92:10931
94:9372
96:9237
98:6680
100:5869
102:3695
104:2536
106:1038
108:402
110:136
112:8


Additionally, a slightly better way of solving 5x5 NRG after LMNO QRST VWXY are already solved is to first solve C HIJ with at most 86 moves, then solve the rest of the board with at most 113 moves, yielding an upper bound of 21+24+66+86+113=310.
*UPDATE (2021-07-18): *Added a new 36-move 3-cycle and 4-new 36-move 2,2-cycles for 5x5NRG, as well as improved Dijkstra's algorithm for optimally applying setup moves to cycle algorithms. Also, I realized that when computing the first three solving phases of 5x5NRG, I was accidentally too restrictive with where the gripped piece could end up after each phase, so the real GNs of those phases are actually slightly lower than what I wrote earlier. 20+23+65 (https://github.com/coolcomputery/Lo...53e6c20e33e05a6fbd087cb3e/LoopoverNRGBFS.java) + 82+106 (https://github.com/coolcomputery/Lo...4ce9fec3ae221fdfdfc6/LoopoverNRGDijkstra.java) = 296.


----------



## xyzzy (Jul 13, 2021)

New 4×4 NRG upper bound: 63 59 moves.

Phase 1: Move every piece (including the grip piece) to the correct row.


Spoiler: distribution





```
0	1
1	2
2	5
3	12
4	29
5	70
6	169
7	408
8	981
9	2354
10	5573
11	13256
12	31435
13	74284
14	174955
15	409564
16	949463
17	2162078
18	4736835
19	9550151
20	16052010
21	18309973
22	9472865
23	1108229
24	8292
25	6
```




Phase 2: Solve the rest.


Spoiler: distribution





```
0       1
1       2
2       1
3       0
4       0
5       0
6       0
7       0
8       0
9       0
10      0
11      0
12      0
13      0
14      0
15      0
16      1
17      2
18      1
19      16
20      68
21      114
22      112
23      126
24      204
25      340
26      684
27      1386
28      2555
29      4850
30      9250
31      17252
32      28989
33      40096
34      36974
35      18416
36      4098
37      344
38      6
```




Phase 2's distribution was found using a coset solver, running up to depth 37, which took about 8 minutes of CPU time and over an hour of human hair-tearing-out time. This covers all odd-parity states as well as all-but-six even-parity states, which forces the remaining even-parity states to be at depth 38. (There can't be any at depth 40 or higher, because that would mean there are depth-39 odd-parity states, which don't exist.) 

Edit: The struck-out argument above is incorrect, because gaps in the distribution can't be excluded a priori. Running the coset solver to completion at depth 38 (roughly 12 minutes total CPU time) verifies the result. (Edit edit: the argument can still be repaired; if there is some depth n≥40 even-parity state, then applying a left or right move _on the inverse_ will bring it to either n+1 or n−1 moves while staying in the same coset, but there are no states at those depths.)

This gives an upper bound of 25 + 38 = *63 moves*.

---

There are five phase 1 cosets at depth 2, but up to symmetry there are only two distinct cosets, given by the scrambles DD and DR/DL/UR/UL. We solve both of those. (Roughly 6 minutes of CPU time each.) We also solve the 25-move cosets. (Roughly 11.5 minutes of CPU time total.)


Spoiler: distributions



(The formatting is dumb because of four-space tabs and this is why elastic tabs is the one true tab style. Copy-paste it into a text editor or spreadsheet program to see it properly.)

The 2-move cosets:

```
dist	DD	DR
2	1	1
3	2	2
4	1	1
5	0	0
6	0	0
7	0	0
8	0	0
9	0	0
10	0	0
11	0	0
12	0	0
13	0	0
14	0	1
15	0	2
16	1	1
17	2	4
18	1	12
19	16	17
20	48	20
21	50	29
22	64	94
23	150	176
24	242	208
25	352	327
26	678	668
27	1270	1234
28	2340	2423
29	4534	4744
30	8842	9244
31	16600	17281
32	29116	29632
33	41130	41119
34	38226	37560
35	18720	17947
36	3384	3079
37	118	62
```

The 25-move cosets:

```
J N M O
a L I K
H C B D
P E G F
25	26
26	106
27	290
28	776
29	2110
30	5152
31	11286
32	22968
33	39232
34	46432
35	29661
36	7510
37	339
L F G H
E O M P
N C B D
a J K I
25	26
26	106
27	290
28	776
29	2110
30	5152
31	11286
32	22968
33	39232
34	46432
35	29661
36	7510
37	339
O P N M
J I K L
B D C a
F E G H
25	4
26	54
27	266
28	864
29	2170
30	4904
31	10876
32	22344
33	38482
34	46193
35	30744
36	8575
37	402
38	10
J O I E
H N F P
C a D B
K G L M
25	22
26	114
27	368
28	984
29	2224
30	5028
31	11374
32	23490
33	39996
34	46496
35	28764
36	6832
37	196
J G I M
K O L E
C a D B
P F N H
25	22
26	114
27	368
28	984
29	2224
30	5028
31	11374
32	23490
33	39996
34	46496
35	28764
36	6832
37	196
E F H G
M N P O
C B D a
K L J I
25	4
26	54
27	266
28	864
29	2170
30	4904
31	10876
32	22344
33	38482
34	46193
35	30744
36	8575
37	402
38	10
elapsed time: 694.646332
```
(The states printed are representatives at the minimal depth.)



Then we can split into three cases:

If phase 1 can be solved in at most 1 move, then the whole solve can be done in at most 1 + 38 = 39 moves.
If phase 1 can be solved in 2≤n≤24 moves, then the whole solve can be done in at most (n−2) + 37 ≤ 59 moves (by skipping the last two moves of the phase 1 solution).
If phase 1 can be solved in 25 moves, then the whole solve can be done in at most 38 moves.

Thus GN is at most *59 moves*.

---

Bonus: approximate (very approximate!) distribution of the optimal 4NRG solution lengths, obtained by solving a random coset at each phase 1 depth (between depths 3 and 24 incl., since I already have exact distributions for 0, 1, 2 and 25) and then taking a weighted average:


Spoiler: 4NRG distribution (approximate)





```
0	1
1	4
2	10
3	24
4	58
5	140
6	338
7	816
8	1966
9	4724
10	11262
11	26756
12	63549
13	150480
14	355085
15	847461
16	2145769
17	4884611
18	10444362
19	22405735
20	45792003
21	94703173
22	235732503
23	778138649
24	1908227165
25	4475497978
26	11053410729
27	26639379181
28	62389724129
29	146658105673
30	337950960661
31	750719849972
32	1527225242626
33	2551667564616
34	2893641867711
35	1738211559105
36	396232133020
37	11424352902
38	1359053
```




This happens to be exact up to depth 7; between depths 8 and 37, you should expect this to be accurate to one and a half sig figs or so. The depth-38 value is probably not very accurate because only two depth-38 scrambles were found at all during the random coset solves, plus the handful at phase 1 depths 0 and 25.


----------



## kubesolver (Jul 13, 2021)

Can you try to brute force better solution for 6*6 worst cases to reduce it further?


----------



## xyzzy (Jul 13, 2021)

kubesolver said:


> Can you try to brute force better solution for 6*6 worst cases to reduce it further?


Well, someone would have to write the code because it's not going to write itself. I think I've spent just about enough time on Loopover-ing for a while. (I assume coolcomputery is going to take a crack at it, eventually?)


----------



## rokicki (Jul 14, 2021)

xyzzy said:


> This happens to be exact up to depth 7; between depths 8 and 37, you should expect this to be accurate to one and a half sig figs or so. The depth-38 value is probably not very accurate because only two depth-38 scrambles were found at all during the random coset solves, plus the handful at phase 1 depths 0 and 25.



It is not super accurate as you guessed for intermediate values; here are the actual counts through distance 28 (QTM):



Spoiler





```
0 1
1 4
2 10
3 24
4 58
5 140
6 338
7 816
8 1970
9 4756
10 11442
11 27456
12 65794
13 157460
14 376386
15 898656
16 2143082
17 5105212
18 12148726
19 28879492
20 68575793
21 162684696
22 385572016
23 912994164
24 2159806867
25 5103944964
26 12045110914
27 28366603900
28 66546847650
```




And for completeness, HTM:



Spoiler





```
0 1
1 6
2 18
3 54
4 162
5 486
6 1458
7 4374
8 13122
9 39366
10 118018
11 353142
12 1056145
13 3155576
14 9422136
15 28100160
16 83755414
17 249414010
18 742173760
19 2206310764
20 6551834832
21 19421204622
22 57369445913
```




The higher values look to be reasonably accurate, however; here's a distribution of 100,000,000 somewhat-random QTM solves (not really random because I only did one random move between each solve):



Spoiler





```
14 2
15 7
16 22
17 54
18 111
19 306
20 670
21 1593
22 3690
23 8632
24 20404
25 48274
26 115248
27 270639
28 636310
29 1481759
30 3384603
31 7429746
32 14923305
33 24582381
34 27374162
35 16069116
36 3545751
37 103186
38 29
```


----------



## coolcomputery (Jul 19, 2021)

*5x5 NRG GN is at most 278.*

I used the solving phases null --> LMN QRS --> LMNO QRST VWXY --> C HIJ LMNO QRST VWXY --> entire board. 25+65+82+106=278.


Spoiler: Phase distributions



null --> LMN QRS (move all rows and columns):
0:19
1:26
2:78
3:200
4:508
5:1338
6:3576
7:9492
8:25154
9:66824
10:176956
11:467172
12:1227542
13:3201312
14:8261077
15:20960104
16:51747614
17:121886784
18:264145457
19:491062661
20:685585493
21:567695147
22:191393456
23:14720577
24:89432
25:1

LMN QRS --> LMNO QRST VWXY (only move rows and columns that do not affect the block LMN QRS):
0:13
1:6
2:14
3:18
4:24
5:34
6:46
7:60
8:82
9:114
10:152
11:202
12:278
13:380
14:506
15:682
16:934
17:1259
18:1686
19:2287
20:3112
21:4194
22:5642
23:7662
24:10370
25:13949
26:18838
27:25551
28:34472
29:46356
30:62608
31:84670
32:113994
33:153305
34:206834
35:278691
36:374327
37:502695
38:675675
39:905712
40:1210780
41:1617135
42:2154888
43:2856933
44:3771365
45:4954949
46:6461480
47:8340221
48:10635200
49:13352714
50:16418176
51:19645646
52:22710265
53:25094207
54:26134754
55:25219838
56:22079706
57:17056323
58:11222159
59:6029119
60:2512983
61:763195
62:155199
63:19468
64:1341
65:42

LMNO QRST VWXY --> C HIJ LMNO QRST VWXY (two programs used) (only use single moves or entire cycle algorithms that by themselves do not affect any already-solved pieces):
0:5
1:4
2:4
30:2
31:17
32:180
33:347
34:368
35:364
36:591
37:892
38:1060
39:1144
40:1019
41:716
42:519
43:234
44:45
45:2
46:1
61:3
62:15
63:344
64:1939
65:5945
66:9025
67:11222
68:13567
69:14311
70:14288
71:15708
72:15882
73:14142
74:11564
75:8533
76:5417
77:2972
78:1379
79:513
80:127
81:23
82:7

C HIJ LMNO QRST VWXY --> entire board (same two programs used as before) (only use single moves or entire cycle algorithms that by themselves do not affect any already-solved pieces):
0:1
1:2
2:2
31:2
32:25
33:63
34:100
35:112
36:162
37:207
38:210
39:170
40:145
41:136
42:132
43:87
44:40
45:17
46:2
63:76
64:486
65:1395
66:2576
67:3643
68:4854
69:5381
70:4685
71:3822
72:2772
73:1836
74:1197
75:621
76:286
77:131
78:59
79:13
80:2
81:2
82:8
95:895
96:4213
97:10937
98:15637
99:13868
100:10314
101:5642
102:2538
103:985
104:262
105:43
106:6



(Sidenote: for 4x4NRG, using the solving phases null --> IJKL MNOP --> entire board yields a bound of 28+94=122, which is worse than xyzzy's bound of 59.)


----------



## coolcomputery (Aug 25, 2021)

*5x5 NRG GN is at most 244. *(20+43+68+113) The solving phases used are the same as the ones xyzzy used in post #12.

Phase 1: Solve AEUY and put M anywhere on the board. (20 moves)


```
0:21
1:24
2:72
3:176
4:416
5:1044
6:2712
7:6820
8:16888
9:40968
10:97612
11:225072
12:485990
13:938792
14:1486888
15:1662330
16:1076585
17:307899
18:25040
19:250
20:1
```

Phase 2a: Solve BCD VWX and put M in the home position. (43 moves)


```
0:1
1:4
2:12
3:24
4:28
5:32
6:46
7:84
8:140
9:240
10:416
11:768
12:1244
13:2188
14:3674
15:6640
16:10928
17:19340
18:32142
19:57446
20:94100
21:166724
22:275016
23:489142
24:801794
25:1416352
26:2312306
27:4059898
28:6534811
29:11257044
30:17599885
31:29138604
32:42614200
33:64486242
34:81122657
35:100996374
36:91429683
37:77175216
38:36210243
39:15295492
40:2133618
41:301708
42:4550
43:144
```

Phase 2b: Use xyzzy's bound of solving FKP JOT in at most 68 moves. (my method gives a much worse bound of 124 moves).

Phase 2c: Solve the last 8 pieces, in the central 3x3 square. (113 moves)


```
0:1 32:16 33:20 34:44 35:34 36:32 37:20 38:8 39:8 40:32 41:4 42:72 43:16 44:14 45:1 46:1 64:176 65:336 66:690 67:1036 68:978 69:652 70:632 71:328 72:416 73:276 74:316 75:240 76:228 77:196 78:100 79:76 80:24 81:2 82:28 84:16 85:12 86:10 88:1 96:448 97:1216 98:3632 99:2728 100:1984 101:1208 102:408 103:672 104:268 105:148 106:140 107:144 108:36 112:24 113:12
```


----------

