coolcomputery
Member
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:
To actually solve a Loopover NRG scramble, we have to do the following:
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:
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.
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)
- comm(a8, b8)
- comm(a8, inv(b8))
- comm(inv(a8), inv(b8))
- where a8=URULDRDL and b8=DLDRULUR
Code:
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
- 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 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:
Code:
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
Last edited: