# Loopover god's number upper bounds: 4×4, asymptotics, etc.



## xyzzy (Sep 9, 2019)

*Summary of current knowledge (2022-04-17):*

STM:
4×4: 18 (by rokicki)
5×5: ≤44 (by coolcomputery)
6×6: ≤88 (by coolcomputery)
(plus some small rectangular sizes by rokicki)
m×n: \( O(N\log^2N) \) where \( N=mn \); ≥\( \lfloor m/2\rfloor n+m\lfloor n/2\rfloor \) (from considering Manhattan distance)
2×n: \( \le n(\log_2n+20) \)

MTM:
4×4: 14 (by rokicki)
(plus some small rectangular sizes by rokicki)
m×n: Θ(mn) (from counting arguments)

---

Loopover = this game; STM = single-tile metric (the one Loopover implementations use to count moves); MTM = multi-tile metric (a seemingly more sensible choice of metric).

STM bound of 26 moves is one move less than the best I could find (27 according to this spreadsheet); MTM bound has not been previously calculated before, as far as I can tell, although chances are that I'm just not aware of it. This puzzle has "only" 21 trillion states and we can get 128-fold symmetry+antisymmetry reduction, so in theory it shouldn't be too hard to BFS the whole thing. (I did also recently get a new 4 TB hard drive…) The solving procedure is essentially: solve a bunch of pieces optimally, then solve the remaining pieces _also optimally_. The second part is something that earlier work did not do, which is why we can get an immediate one-move improvement.

(I might bother to do a more sophisticated analysis later on; there's still a lot of low-hanging fruit left to pick.)

Solving the top two rows optimally takes at most 10 MTM, 13 STM.


Spoiler: MTM distribution



(0, 1)
(1, 18)
(2, 255)
(3, 3648)
(4, 48787)
(5, 605886)
(6, 6632955)
(7, 56497090)
(8, 253413670)
(9, 199503998)
(10, 2212092)

(nice formatting wew)





Spoiler: STM distribution



total states: 518918400
distance 0: 1 nodes
distance 1: 12 nodes
distance 2: 114 nodes
distance 3: 1084 nodes
distance 4: 9931 nodes
distance 5: 86036 nodes
distance 6: 703024 nodes
distance 7: 5240586 nodes
distance 8: 32884017 nodes
distance 9: 142199734 nodes
distance 10: 258379100 nodes
distance 11: 78645932 nodes
distance 12: 768545 nodes
distance 13: 284 nodes
average distance: 9.717073



Solving the bottom two rows optimally once the top two rows are solved takes at most 11 MTM, 13 STM. Note that almost all of the optimal solutions here temporarily destroy the initially solved rows before finally restoring them (because there are no free columns at all), with the only exceptions being the solutions for the sixteen states that can be solved by moving just the two free rows.


Spoiler: MTM distribution





```
move count stats:
 0:         1
 1:         6
 2:         9
 3:        24
 4:       288
 5:      1132
 6:      1340
 7:      8936
 8:     16721
 9:      8992
10:      2703
11:       168
```






Spoiler: STM distribution





```
0:         1
 1:         4
 2:         6
 3:        20
 4:       137
 5:       428
 6:       934
 7:      3172
 8:      8410
 9:     11024
10:      9792
11:      5276
12:       880
13:       236
```




From these, we conclude an upper bound of 21 MTM and 26 STM.

Alternatively (for STM), following earlier work, it is known that solving a 3×3 block takes at most 13 STM; running the optimal solver on the 7! = 5040 possible permutations of the last side last layer leads to a maximum of 13 STM as well, so we have a total of 26 STM.


Spoiler: STM distribution





```
move count stats:
 0:         1
 1:         4
 2:        10
 3:        24
 4:        58
 5:       140
 6:       334
 7:       726
 8:      1258
 9:      1442
10:       829
11:       176
12:        30
13:         8
```




Similarly, solving a 3×2 block takes at most 11 STM; running the optimal solver on the 10! = 3628800 permutations of the last ten pieces leads to a maximum of 15 STM, again a total of 26 STM.


Spoiler: STM distribution





```
move count stats:
 0:         1
 1:         6
 2:        23
 3:        96
 4:       451
 5:      1996
 6:      8370
 7:     33748
 8:    125081
 9:    397755
10:    927554
11:   1230082
12:    748542
13:    150702
14:      4378
15:        15
```






Spoiler: Implementation details



The solver I coded for this doesn't "truly" exploit much of the inherent symmetry of the puzzle. The puzzle state is stored as a 64-bit integer with four bits for each cell, rather than as a permutation coordinate; this allows for switching the top and bottom halves of the puzzle just by doing a bit rotation and xor-ing by a constant. Only one pruning table is used (solving the top eight pieces); this pruning table is stored very inefficiently by using a 32-bit index, but that's fine, because I have 2 GB RAM to spare and it's only one pruning table. This pruning table is applied to the puzzle state itself, a shifted version of the puzzle state (solving the bottom two rows instead of the top two rows, effectively), as well as doing those two things to the _inverse_ state as well to increase average pruning depth.

When solving the last two rows in MTM, this managed to do about 3500 solves per second, with all 8! = 40320 cases being solved in 11.65 seconds.

The solver has not been thoroughly tested for correctness (I literally just wrote it yesterday and haven't reviewed it), but there _is_ a failsafe check to ensure that the generated solutions really do solve the input puzzle state. In other words, if there's a bug, at worst it just means that the solutions are not optimal, as opposed to being completely wrong. Thus this will not affect the correctness of the upper bounds in the rest of this post. (Unless there's a bug in the checking code…)

I tried doing the thing where the solver switches to the inverse scramble opportunistically (like this) but it ended up being 40% slower than just doing regular IDA* (because of branch mispredicts?). Maybe I just didn't implement it right, idk.



========

Update (2019-09-10): STM bound has been reduced to *25 STM*.

Each of the 284 eight-piece cosets that are 13 moves away from solved have the eight pieces ABCDEFGH in the opposite half of the board, e.g.


```
P O M N
K L J I
G H E F
C D B A
```

(For this specific board, it takes 13 moves to solve either ABCDEFGH or IJKLMNOP, and 17 moves to solve the whole thing.) Note that there are four different partitions into 2×4 blocks we can consider:


```
X X X X
X X X X
O O O O
O O O O

X X X X
O O O O
O O O O
X X X X

X X O O
X X O O
X X O O
X X O O

X O O X
X O O X
X O O X
X O O X
```

The only way a piece can be in the opposite block of its home position under all four of these partitions simultaneously is if it's at the antipodal position, i.e.


```
K L I J
O P M N
C D A B
G H E F
```

But it takes only 12 moves to solve ABCDEFGH on this board (shift the bottom two rows by two cells (4 moves), then shift every column by two cells (8 moves)). Thus there is no state that is in a 13-move eight-piece coset under all four partitions simultaneously, and it always takes at most 12 moves to solve some 2×4 block (although solving a _specific_ block may sometimes take 13 moves). This leads to a total upper bound of 12 + 13 = 25 STM.

========



Spoiler: Additional notes / future work



TL note: "future" probably means like in the rest of the week, depending.

Consider the asymptotic behaviour of GN in the single-tile and multi-tile metrics. In the latter, a counting argument shows that it is bounded below by Ω(n^2) and a 3-cycle method shows that it is bounded above by O(n^2), so god's number in MTM is necessarily Θ(n^2). The former seems to be a lot more complicated. Again, a counting argument gives a lower bound of Ω(n^2), but the 3-cycle method gives an upper bound of O(n^3). I think I have a way of bringing the upper bound down to something like O(n^2 (log n)^4) but I haven't worked out the details (so the exponent of the log factor is probably wrong); I'm _pretty sure_ the actual asymptotic behaviour is Θ(n^2), but I can't figure out how to prove that.

As for a lower bound, there are two basic approaches to consider. As mentioned above, we have a counting argument leading to a lower bound of cn^2 + o(n^2) for some constant c ≥ 2, but for small sizes we can also consider a bound given by Manhattan distance. As the sides wrap around (or should I say, they _loop over_), the maximum possible distance in either axis is ⌊n/2⌋, so the maximum possible Manhattan distance for each piece is 2⌊n/2⌋. Each move affects n pieces, the Manhattan distances of which change by at most ±1; hence the maximum possible change in the sum of Manhattan distances is ±n. The sum of Manhattan distances for a whole board is bounded by 2⌊n/2⌋ × n^2, so this gives a GN lower bound of 2⌊n/2⌋ × n. One example of a board hitting this bound is by shifting all of the rows by half of the board size, then shifting all of the columns by half of the board size. (If n is odd, it doesn't matter whether we round down or round up.)

In particular, this gives a lower bound of 36 for 6×6, which is better than the counting bound of 31, at least according to the formula in the Loopover Research spreadsheet. (I haven't verified it, but it seems roughly correct.)


----------



## Filipe Teixeira (Sep 11, 2019)

I don't understand

TL;DR please?


----------



## xyzzy (Sep 11, 2019)

Filipe Teixeira said:


> I don't understand
> 
> TL;DR please?


The tl;dr version is the thread title.  Explanations are, by their very nature, the exact opposite of tl;dr, so in case that's what you really wanted:

God's number is the maximum among optimal solution lengths: GN := max {min {length of S | S is a solution to P} | P is a puzzle state}.

But how do you measure the length of a solution? Cary's original Loopover counts moving by one cell as one move, moving by two cells as two moves, et cetera. This is the *single-tile* metric (STM). Besides STM, we can also treat moving by multiple cells as one move instead of multiple moves; this leads to the *multi-tile* metric (MTM). Naturally, god's number for the different metrics can be expected to be different (just as god's number for 3×3×3 is 20 in FTM and 26 in QTM, or god's number for 15 puzzle is 40-something in MTM and 80-something in STM).

Generally, a lower bound for GN is obtained either by counting move sequences (if there are only X move sequences of length at most N, and there are more than X puzzle states in total, then GN must be greater than X), or by explicitly finding some puzzle state that takes so-and-so many moves to solve. On the other hand, an upper bound is obtained by devising a solving algorithm that can solve _any_ puzzle state within a certain number of moves. Here, the algorithm is to solve the top half of the puzzle while ignoring the bottom half (500 million different cases; at most 13 STM) and then the bottom half of the puzzle while preserving the top half (40320 different cases; coincidentally, also at most 13 STM); this gives an upper bound of 26 STM.

Again, like in cubing, we can consider analogues of "colour neutrality". In this case, instead of always solving the top 2×4 rectangle on the board for the first step, what if we choose to start with the bottom half instead? The left half? The right half? Or what if we switch to the inverse like we do for FMC? Et cetera. In this case, the 13 STM cases for the first step can always be avoided, so the first step takes at most 12 STM with "colour neutrality". This reduces the upper bound to 12 + 13 = 25 STM.


----------



## xyzzy (Sep 14, 2019)

So, I said this:
>I think I have a way of bringing the upper bound down to something like O(n^2 (log n)^4)

Turns out my original idea didn't work, but I made it stupider and that gave me a bound of \( O(n^2\log^2n) \). And unlike most of my other theoryposts, this one *comes with code*. It might be possible to drop this further to \( O(n^2\log n) \) by using a parallelism trick similar to what Demaine et al used for showing that GN for n×n×n Rubik's cube is \( \Theta(n^2/\log n) \), and if that works, combining this trick with a hypothetical \( O(n\log n) \) sorting network of exactly the type of structure we need (I believe the existence of such sorting networks is an open problem) would prove a bound of \( \Theta(n^2) \).

More specifically, let the board size be \( R\times C \) (with \( R\ge2 \) rows and \( C\ge2 \) columns), and let \( N:=R\cdot C \). The solving algorithm presented results in a solution of length \( O(N\log^2N) \), regardless of the ratio \( R/C \); in particular, we do not assume \( R\ll C\ll R \).

(The hidden constant for this new solving algorithm is relatively large (\( \approx2.6N\log^2 N \) moves on random roughly-square boards), so it only wins over spamming basic 3-cycles (\( \approx0.85N^{1.5} \) moves on random roughly-square boards) when N exceeds around 250000, with both methods taking over _100 million_ moves. Needless to say, this algorithm is not very relevant for typical board sizes like 4×4 to 20×20.)

*Definition 1*: An _involution_ is a permutation \( \pi \) such that \( \pi^2=\mathrm{id} \). (We consider the identity permutation to be an involution here; other sources may instead define involutions to be permutations of order 2, excluding the identity permutation. This distinction is of little significance here.)

*Definition 2*: Let \( \pi,\pi'\in\mathrm{Sym}(\Omega) \) be permutations on the same set. Say \( \pi'\prec\pi \) if, for all \( x\in\Omega \), we have that \( \pi'(x)\in\{x,\pi(x)\} \). (In other words, the non-trivial cycles of \( \pi' \) are a subset of the non-trivial cycles of \( \pi \).)

*Definition 3*: An involution \( \pi \) on a set of integers is said to be of _uniform distance_ if there exists some \( d>0 \) such that for every transposition \( (a,b)\prec\pi \), we have that \( |a-b|=d \). (Note that \( d \) is uniquely determined except when \( \pi=\mathrm{id} \). I don't know if this has a proper name in literature.)

*Definition 4*: More generally, an involution \( \pi\in\mathrm{Sym}(G) \) on an additive (abelian) group \( G \) is said to be of _uniform displacement_ if there exists some \( d\in G \) such that for every transposition \( (a,b)\prec\pi \), we have that \( a-b\in\{d,-d\} \).

*Proposition 5*: Let \( \pi\in\mathrm{Sym}(\{0,\cdots,n-1\}) \) be an arbitrary permutation on \( n \) elements. Then there exists a decomposition of \( \pi \) as the composition of \( O(\log^2n) \) uniform-distance involutions. Furthermore, if there is some threshold \( t\ge0 \) such that \( \pi(x)=x \) for all \( x<t \), then every term of the decomposition fixes every point in \( \{0,\cdots,t-1\} \).

We do not provide a full proof of this proposition, but the basic idea is to apply an \( O(n\log^2n) \) sorting network that can be divided into \( O(\log^2n) \) stages of comparators, where the comparators of a stage all have the same distance, and the swaps performed by the comparators are all disjoint. Note that this is a weaker condition than the comparators being disjoint; for example, the provided implementation of our algorithm makes use of Shell sort with 3-smooth gaps, with one stage for each gap used. Within a stage, except around the endpoints, every element is involved in _two_ comparators, so the comparators are very much not disjoint, but with 3-smooth Shell sort, an element is never swapped more than once for each gap, i.e. the swaps are disjoint.

*Proposition 6*: Let \( \pi\in\mathrm{Sym}(\{0,\cdots,R-1\}\times\{0,\cdots,C-1\}) \) be an arbitrary permutation on \( N=RC \) elements. Then there exists a decomposition into \( O(\log^2N) \) uniform-displacement involutions (taking \( G=\mathbb Z^2 \) in the above definition of a uniform-displacement involution). (In particular, the displacement is not allowed to "wrap" around the sides.) Furthermore, if there is some threshold \( t\ge0 \) such that \( \pi(0,x)=(0,x) \) for all \( x<t \), then every term of the decomposition fixes every point in \( \{(0,0),\cdots,(0,t-1)\} \).

Proof: Identify the underlying set with \( \{0,\cdots,N-1\} \) with the bijection \( (r,c)\mapsto Cr+c \). Per the previous proposition, this leads to a decomposition into \( O(\log^2N) \) uniform-distance involutions. For each of these uniform-distance involutions \( \pi_i \) with distance \( d \), switching back to the original underlying set \( (\{0,\cdots,R-1\}\times\{0,\cdots,C-1\} \), there are only two possible displacements (up to sign): \( (\lfloor d/C\rfloor,d\% C) \) and \( (\lfloor d/C\rfloor+1,d\% C-C) \); this leads to a decomposition \( \pi_i=\sigma_i\tau_i \) for each \( \pi_i\ \), where \( \sigma_i,\tau_i \) are of those two displacements, respectively. Then \( \pi=\sigma_0\tau_0\sigma_1\tau_1\cdots \), a decomposition with at most twice as many nontrivial terms as the earlier (one-dimensional) decomposition, and hence also \( O(\log^2N) \). The preserved points carry over from the one-dimensional case.

*Lemma 7*: Let \( a,b,c\in\{0,\cdots,R-1\}\times\{0,\cdots,C-1\} \) be three distinct positions on an \( R\times C \) Loopover board. Then there exists a sequence of moves cycling the three pieces at those positions of length \( \le\frac32(\|a-b\|_1+\|b-c\|_1+\|c-a\|_1) \) where \( \|\cdot\|_1 \) denotes the Manhattan distance on the board.

Proof outline: If the three pieces are all in distinct rows and distinct columns, slide any one of the three pieces so that two of them are in the same row and the third is in a different row. If the three pieces are all in the same row/column, slide one of them out of the way. Now, with two pieces in the same row (or column), slide the row (or column) containing those two pieces so that one of the pieces is in the same column (or row) as the third piece, then do a basic commutator to cycle the three pieces and undo all the setup moves. For details, see the code.

*Lemma 8*: Let \( a,b,c,d\in\{0,\cdots,R-1\}\times\{0,\cdots,C-1\} \) be four distinct positions on an \( R\times C \) Loopover board. Then there exists a sequence of moves swapping the piece at \( a \) with the piece at \( b \) and the piece at \( c \) with the piece at \( d \) of length \( \le3\|a-b\|_1+3\|c-d\|_1+6\|a-c\|_1 \).

Proof: Do the 3-cycles \( (a,b,c) \) and \( (a,d,c) \). The total move count is bounded by \( \frac32(\|a-b\|_1+\|c-d\|_1+2\|a-c\|_1+\|b-c\|_1+\|a-d\|_1) \), which simplifies to \( 3\|a-b\|_1+3\|c-d\|_1+6\|a-c\|_1 \) with the triangle inequality.

*Lemma 9*: Let \( \pi\in\mathrm{Sym}(\{0,\cdots,R-1\}\times\{0,\cdots,C-1\}) \) be an even uniform-displacement involution on \( N=RC \) elements. Then there exists a sequence of \( O(N) \) moves with the effect of permuting the pieces on an \( R\times C \) Loopover board by \( \pi \).

Proof: Will anyone even read this far… I'll type this out later. The argument is kind of long and messy. In the meantime, check the code (and the comments).

*Theorem 10*: Any scrambled \( R\times C \) Loopover board can be solved in \( O(N\log^2N) \) moves.

Proof: We first solve the first two pieces of row 0 (either directly or via 3-cycles); this takes \( O(N) \) moves. If the board now has odd parity, apply a move in either the last column (if \( R \) is even) or in the last row (if \( C \) is even) to bring it to an even-parity state, still with the first two pieces solved.

Per the previous propositions, the inverse of the board state (as a permutation) can be decomposed into \( O(\log^2N) \) uniform-displacement involutions. For each of these involutions \( \pi_i \), let \( \pi_i':=\pi_i \) if it is an even permutation and \( \pi_i':=\pi_i\circ(a,a+d) \) for some \( (a,a+d)\prec\pi_i \) if it is an odd permutation. Then \( \pi_i' \) is always an even permutation. In the former case, we directly invoke Lemma 9 to get a move sequence of length \( O(N) \); in the latter case, we first apply the transpositions \( (a,a+d)(0,1) \), which takes \( O(R+C)\subseteq O(N) \) moves and then invoke Lemma 9 on \( \pi_i' \) to get a move sequence of total length \( O(N) \). In either case, the length is bounded by \( O(N) \) for each uniform-displacement involution. Since the board state at the beginning of this step is even and the moves applied for each uniform-distance involution all have zero net effect on the parity, it follows that the first two elements will be swapped an even number of times in total, and hence the board will be fully solved after applying all of the involutions in the decomposition.

This leads to a total move count of \( O(N)+O(\log^2N)\cdot O(N)=O(N\log^2N) \). □

Edit (2019-09-15): Some typos and minor mistakes fixed. The constant factors might still be wrong but good thing those aren't the main point of this post. The code has also been updated to fix an inefficiency on non-square boards (which made it not \( O(N\log^2N) \) for extreme aspect ratios), as well as a silly bug in generating random states where it doesn't check for parity on odd-sized boards.


----------



## zman (Sep 15, 2019)

oh cool, i used to own the loopover discord server and own/helped a lot with the research sheet you linked. im not remotely smart enough to understand what's happening but its cool seeing others working on GN for loopover. ill add this to the research sheet


----------



## xyzzy (Oct 4, 2019)

tl;dr STM GN for 5×5 is at least 22.

Precise counts of "canonical" 5×5 move sequences in STM (where "canonical" means that a consecutive bunch of row moves are done starting from the top row to the bottom, no redundant moves are made, and the shorter path is always taken; likewise for column moves):

We divide move sequences into syllables and count them via generating functions. For a single syllable corresponding to row/horizontal moves, we have \( 1+2x+2x^2 \) for how an individual row can move, and thus \( (1+2x+2x^2)^5 \) for how the five rows can move. One of those corresponds to a trivial move sequence (move all of the rows by 0), so subtract one to exclude that: \( s(x):=(1+2x+2x^2)^5-1 \). By symmetry, we get the same expression for column/vertical moves.

The trivial move sequence consists of no syllables: 1. Any non-trivial canonical move sequence (uniquely) decomposes into a finite sequence of nontrivial syllables of alternating directions, i.e. it must be either H-V-H-V-H-etc. or V-H-V-H-V-etc. This is just a standard geometric progression and we use the standard formula for that: \( \frac{2s(x)}{1-s(x)} \). Add these two cases together and we get the generating function \( 1+\frac{2s(x)}{1-s(x)} \) for the number of canonical move sequences. Expand this to 24 terms or so:

\( 1 + 20 x + 300 x^2 + 4320 x^3 + 62120 x^4 + 893584 x^5 + 12854320 x^6 + 184910080 x^7 + 2659940480 x^8 \\
+ 38263376000 x^9 + 550420568192 x^{10} + 7917827258880 x^{11} + 113898339051520 x^{12} + 1638433274027520 x^{13} \\
+ 23568944163699200 x^{14} + 339040434418122752 x^{15} + 4877113517349276160 x^{16} + 70157520597607214080 x^{17} \\
+ 1009219424336639902720 x^{18} + 14517671630674993315840 x^{19} + 208837428703515031881728 x^{20} \\
+ 3004136802167631885004800 x^{21} + 43214657363697298461511680 x^{22} + 621644996231283351323279360 x^{23} + O(x^{24}) \)

We note that the 5×5 board has \( 25!/2 \approx 7.8\cdot10^{24} \) states, and up to 21 moves, there are less than \( 4\cdot10^{24} \) possible move sequences. Therefore GN for 5×5 in STM must be at least 22 moves. This improves on the Manhattan-distance bound of 20 moves.

Bonus: This also lets us approximate the branching ratio (with e.g. brute force or IDA* search); taking the two largest terms printed above and dividing, we get a value of around 14.38.

Bonus #2: There is a different notion of canonicalisation where we defer "global" shifts to the last two syllables (if there are at least two syllables); "global shift" meaning something like shifting every row by the same amount, which can be cancelled by a later syllable shifting every row by the same amount in the opposite direction. This reduces the effective move count a bit compared to the naïve canonicalisation, and is roughly akin to excluding stuff like L2 R2 U2 D2 L R' on the Rubik's cube. The calculation required is considerably more complicated and (i) I don't feel like doing it; (ii) it probably won't affect the above calculation much.

Bonus #3: It's probably possible to increase the bound to 24-25 by just trying to solve a few random boards; we don't even need to let the solves run to completion. Gonna try this later.
--------
(putting an update in this post because it seems too spammy to have a separate post for each minor result)

STM GN for 4×4 is at most 24.

We divide the board into its top half and its bottom half, and consider the cases where the pieces in the top half require 12 or 13 moves to solve and same for the pieces in the bottom half. Naïvely this might seem like it would have (768545+284)^2 = 591,098,031,241 cases, which is a very large number, but most combinations are impossible, in the sense that there would be duplicate pieces (e.g. there are two "A"s on the board) and missing pieces (e.g. there is no "B" on the board). The number of possible combinations is only 953,528,011, which is still large, but more manageable.

Among those 954 million positions, 951,485,926 (~99.79%) of them have a 2×4 block that can be solved in at most 11 moves, in one of these four positions, on normal or on inverse:

```
A B C D
E F G H
. . . .
. . . .

. . . .
. . . .
I J K L
M N O P

A B . .
E F . .
I J . .
M N . .

. . C D
. . G H
. . K L
. . O P
```
By solving this 2×4 block first, then solving the rest, we obtain an upper bound of 24 moves for these positions. For the remaining positions, an optimal solver was used on all 2042085 such positions and all of them can be solved in at most 18 moves; an example of an 18-mover is:

```
F B N J
E A M I
H D P L
G C O K
```
with optimal solution (in a sorta SiGN-like notation) 1U 2U 1L 1U 1L 4L2 2U 2L 2U 4L 1U' 2L 3U 4L 1U2 1L'. (Interestingly, this has a lot of symmetry; it's equivalent to just transposing the solved board.)

Either there is a 2×4 block (on normal or on inverse) that can be solved in at most 11 moves, in which case the entire board can be solved in at most 11+13=24 moves, or all eight of the 2×4 blocks looked at require at least 12 moves and the entire board can be solved in at most 18 moves; therefore GN is at most 24.



Spoiler: some more notes about the solver



I had to optimise the performance of my solver _a lot_ for this approach to be feasible. As before, the "main" heuristic used is still the 8-piece pattern database for solving ABCDEFGH / IJKLMNOP, but now we also transpose the board (this can be done pretty quickly with SWAR magic) and apply the pattern database to check ABEFIJMN and CDGHKLOP as well. If all four values returned are the same (which is rarely the case on random states, but not-so-rarely the case for the specific states we're looking at), then we can bump up the heuristic by one.

(The SWAR magic: )

```
static long transposeSymmetry(long state) {
	// transpose the cells
	state = (state & 0xff00_ff00_00ff_00ffl) | ((state & 0x00ff_00ff_0000_0000l) >>> 24) | ((state & 0x0000_0000_ff00_ff00l) << 24);
	state = (state & 0xf0f0_0f0f_f0f0_0f0fl) | ((state & 0x0f0f_0000_0f0f_0000l) >>> 12) | ((state & 0x0000_f0f0_0000_f0f0l) << 12);
	// then relabel
	state = ((state & 0x3333_3333_3333_3333l) << 2) | ((state & 0xcccc_cccc_cccc_ccccl) >>> 2);
	return state;
}
```

In addition, I also added the walking distance (WD) heuristic. This provides a very tiny speedup (like a few percent), but it doesn't seem to be worse and I already spent the time coding it, so I might as well just leave it in. By itself, the WD heuristic also allows solving random states reasonably quickly (a few positions per second) without large lookup tables; this is the distribution:

distance 0: 1 double cosets / 1 cosets
distance 1: 2 double cosets / 512 cosets
distance 2: 46 double cosets / 72544 cosets
distance 3: 540 double cosets / 3322528 cosets
distance 4: 2781 double cosets / 24128154 cosets
distance 5: 4350 double cosets / 27447240 cosets
distance 6: 1886 double cosets / 7456910 cosets
distance 7: 492 double cosets / 625312 cosets
distance 8: 49 double cosets / 9799 cosets
total number of double cosets: 10147
average (for one axis): 4.647083646512218
average (for both axes): 9.294167293024437

While the average value of the WD heuristic is smaller than the 8-piece PDB (9.29 versus >9.7), it also has a larger maximum (16 versus 13). Since we're already computing the transposed board for the 8-piece PDB, we reuse that instead of transposing again. (Note that walking distance is a uniform improvement over Manhattan distance, in the sense that WD ≥ MD for _any_ board, so it makes no sense to compute MD once we have WD. Furthermore, viewing WD as distance in the double-coset space (with the subgroups on both sides being generated by arbitrary row permutations), it turns out that the WD of a board is always the same as the WD of its inverse, so there's no need to explicitly compute that either (like we do for the 8-piece PDBs).)

The last optimisation I did was the very obvious thing of making use of the permutation parity of the board to exclude known-fruitless searches. E.g. if the board has even parity, we can skip searches of odd-length solutions. This provides something like a 3× speedup. (This parity constraint only works if the width and height are both even, so e.g. it wouldn't work on 3×4 or 5×5.) All in all, my current optimal solver manages around 240-250 random positions per second, compared to 27-ish before yesterday.

The main motivation for doing this was really just to check the effectiveness of the WD heuristic, to prepare for writing a 5×5 optimal solver. While it's not especially useful on 4×4 (thanks to the 8-piece PDB being at just about the right size to fit in free RAM), it seems that n-piece PDBs would have to be really big on 5×5 in order to be effective. Unlike 15-puzzle/24-puzzle, it's not clear how to create useful additive pattern databases on Loopover because every move has "nonlocal" effects. Stuff like linear conflict or invert distance that apply for 15-puzzle are basically useless on Loopover.


----------



## zman (Oct 4, 2019)

very nice  I added it to the research sheet


----------



## Ben Whitmore (Oct 5, 2019)

xyzzy said:


> tl;dr STM GN for 5×5 is at least 22.



Applying the same method to other n gives the following bounds:



Spoiler



3 - 6
4 - 14
5 - 22
6 - 35
7 - 48
8 - 66
9 - 86
10 - 109
11 - 134
12 - 163
13 - 194
14 - 229
15 - 265
16 - 306
17 - 348
18 - 394
19 - 442
20 - 495
21 - 548
22 - 606
23 - 666
24 - 730
25 - 796
26 - 866
27 - 937
28 - 1013
29 - 1091
30 - 1173
31 - 1256
32 - 1344
33 - 1434
34 - 1528
35 - 1623
36 - 1724
37 - 1825
38 - 1931
39 - 2039
40 - 2151
41 - 2265
42 - 2383
43 - 2503
44 - 2628
45 - 2753
46 - 2884
47 - 3016
48 - 3153
49 - 3291
50 - 3434



The branching factor is 1/x where x is the positive real root of \( (1+2x+2x^2+\cdots+2x^{(n-1)/2})^n=2 \) for odd n and \( (1+2x+2x^2+\cdots+2x^{n/2-1}+x^{n/2})^n=2 \) for even n. For n=5, this is \( \displaystyle{\frac{2}{\sqrt{2^{6/5}-1}-1}\approx 14.3850497528\cdots} \)


----------



## coolcomputery (Nov 29, 2019)

4x4 STM GD is at most 23








Loopover-Brute-Force-and-Improvement/LoopoverBruteForce.java at master · coolcomputery/Loopover-Brute-Force-and-Improvement


using block-building to find upper bounds on God's numbers of various RxC Loopover puzzles - Loopover-Brute-Force-and-Improvement/LoopoverBruteForce.java at master · coolcomputery/Loopover-Brut...




github.com





The solved 4x4 board will look like this:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
1. Enumerate all ways of building the 2x3 whose upper-left corner is 0, 0 (i. e. the pieces 0, 1, 2, 4 5, and 6) and store the BFS tree
this gives GD 11


Spoiler: STM distribution



0: 1
1: 10
2: 89
3: 786
4: 6292
5: 44605
6: 267634
7: 1163031
8: 2605100
9: 1586474
10: 91700
11: 38


2. Improve the resulting distribution by seeing if any permutation with depth D can be avoided by solving a translated 2x3 block, ex. solving the pieces {1, 2, 3, 5, 6, 7} or {4, 5, 6, 8, 9, 10} that is guaranteed to be solved with depth <D.
This makes a very small improvement.


Spoiler: Improved 2x3 STM distribution



8: 2604856
9: 1572528
10: 58932
11: 0
no permutations with depth <8 are improved


3. Enumerate all ways of building the last two layers and last column and store the BFS tree
this gives GD 18 (it's not the optimal solver xyzzy mentioned; I don't know how to program it; this solver only moves the last two rows and the last column, so it does not allow temporarily destroying the solved 2x3)


Spoiler: STM distribution



0: 1
1: 6
2: 23
3: 84
4: 301
5: 1056
6: 3622
7: 11838
8: 36287
9: 101888
10: 251901
11: 535540
12: 929991
13: 1040929
14: 584196
15: 122857
16: 8076
17: 202
18: 2


(Steps 1 and 3 take 36.042 seconds; Step 2 takes 408.836 seconds.)
4. Create every permutation that will be solved in 24 moves or greater when applying these BFS trees on it directly (i. e. solving pieces {0, 1, 2, 4, 5, 6}, then all other pieces).
Try solving each permutation by applying the BFS trees, but translated (ex. first solving {1, 2, 3, 5, 6, 7}, then the rest; or first solving {4, 5, 6, 8, 9, 10}, then the rest).

There are 270,178,609,964 such permutations. Running them took 359547.840 seconds (about 4 days and 4 hours) on an Intel i5 and 16 GB RAM.
To make everything run fast, I compressed certain data into 64-bit ints and compressed specific sequences of moves into single permutation operations.

*IMPORTANT UPDATE: the stuff crossed out below is incorrect;* it assumes that the pieces in the 5x5 that are not in the 3x4 region are in specific positions and thus its upper bound might be more optimistic than it should be.
*Update:* 5x5 STM GD is at most 53
From earlier work on this Google Sheets page, the GDs of making a 2x3, expanding to a 3x4, and expanding that to the entire board are 13, 17, and 25 respectively.


Spoiler: 2x3 STM distribution



0: 1
1: 10
2: 94
3: 880
4: 7558
5: 58432
6: 402862
7: 2335840
8: 10374813
9: 30419907
10: 47958515
11: 30962779
12: 4936603
13: 53706





Spoiler: 3x4 STM distribution



0: 1
1: 4
2: 20
3: 102
4: 482
5: 2222
6: 9748
7: 39836
8: 150138
9: 511391
10: 1506067
11: 3451772
12: 5352468
13: 5069035
14: 2687355
15: 693629
16: 60221
17: 549


I did the same improvement algorithm I did above but this time with making a 2x3 and expanding it to a 3x4, reducing the total GD to 28 moves.
Total of 5973908667 permutations; took 8508.611 seconds to run.
I decided not to do the single BFS improvement like I did in step 2 of the above procedure because I didn't think it would give any significant improvement and it would be one less algorithm for the others to verify (unless someone has already checked my code).
Also I had to abandon using an int[][][] table to reduce memory usage (I'm not writing data to any files so everything has to run in Java heap space).
I might try reducing it to 27 moves in the future.

*UPDATE: *So far this algorithm cannot further reduce the 4x4 STM GD; I will add new transformations (ex. rotations, reflections) or add something completely different in the future.


----------



## coolcomputery (Mar 13, 2020)

5x5 STM GD is indeed at most 53
I improved the 0x0->2x3 and the 2x3->3x4 steps differently: instead of solving translated regions of each scramble (which requires testing over all permutations of where the non-3x4 pieces can go in a 5x5), I added 1 prefix move before running the block-building to lower the solution length, so that I only have to consider pieces in the 3x4 region. A total of 5,973,908,667 scrambles took 22581.416 seconds (including the BFS tree building time) to process. See https://github.com/coolcomputery/Loopover-Brute-Force-and-Improvement for more detail.

UPDATE: 6x6 STM is at most 114 111


Spoiler: 0x0-2x2



1:8
2:64
3:496
4:3054
5:15768
6:62788
7:179036
8:336315
9:406485
10:294620
11:105050
12:10016
13:19





Spoiler: 2x2->3x3



1:4
2:20
3:107
4:534
5:2622
6:12208
7:53226
8:213156
9:752989
10:2185203
11:4717064
12:6901080
13:6172742
14:2727849
15:413986
16:12313
17:16


Naively the GD of these two phases is 30. Using the same improvement algorithm as above for the 5x5 brings this down to 27 moves (133,268,049 scrambles processed in 240.018 seconds, including BFS tree building time). So far I can't improve this further.


Spoiler: 3x3->3x4



1:2
2:6
3:25
4:86
5:288
6:891
7:2295
8:4166
9:4871
10:3425
11:1320
12:171
13:3





Spoiler: 3x4->4x4



1:2
2:6
3:25
4:84
5:270
6:868
7:2682
8:7757
9:19860
10:40438
11:60152
12:61370
13:41555
14:16756
15:3106
16:92





Spoiler: 4x4->4x5



1:2
2:6
3:25
4:82
5:254
6:800
7:2356
8:6498
9:15370
10:27218
11:32295
12:22767
13:7720
14:871
15:15





Spoiler: 4x5->5x5



1:2
2:6
3:21
4:58
5:156
6:441
7:1165
8:2945
9:7508
10:17927
11:38631
12:72472
13:108595
14:123522
15:99620
16:43574
17:7258
18:256
19:2





Spoiler: 5x5->6x6



1:4
2:12
3:34
4:96
5:272
6:766
7:2156
8:5908
9:15958
10:42012
11:108858
12:274021
13:656998
14:1491906
15:3136152
16:5834236
17:8849090
18:9745835
19:6792578
20:2547005
21:395978
22:16596
23:322
24:6


(2020-3-14) The GD of 4x5->5x5 and 5x5->6x6 was reduced from 43 to 40. 161364 scrambles were processed in 1.716 seconds., along with 3.365 seconds of preprocessing. The BFS trees took 84.170 seconds to build. So far I can't improve this further.
(2020-3-15) *UPDATE: 6x6 STM GD is at most 103.*
The GD of building 3x3->4x4 is 21. 4,475,671,200 scrambles took 12029.851 seconds to calculate.


Spoiler: 3x3->4x4



1:4
2:20
3:107
4:532
5:2618
6:12659
7:60053
8:277611
9:1235833
10:5239206
11:20861508
12:75949199
13:239831312
14:604848130
15:1098191475
16:1285531774
17:848066735
18:264240092
19:30468615
20:851708
21:2008


----------



## coolcomputery (Apr 2, 2020)

4x4 STM GD is at most 22
I added row reflection, column reflection, and transposition (flipping along the main diagonal) to my previous algorithm on improving the 0x0->2x3 and 2x3->4x4 block-building.
A total of 1647318090782 scrambles that required >=23 moves when the block-building was applied naively took about 17 days to process (I had to interrupt the search two times to restart my computer but I made sure it printed to stdout how far it was in the search so that I could resume it). Adding the transposition was very important as previous search attempts without it failed within the first hour.
See https://github.com/coolcomputery/Loopover-Brute-Force-and-Improvement for more detail. The version of the algorithm I used for this search should be a much faster version than the one I used for proving that 4x4 STM GD is at most 23.
*UPDATE (2020-05-30):* Currently I cannot bring down the STM GD to 21. An example scramble that fails to be reduced to <=21 moves is:
GDCB
OPMN
ILEJ
AHKF


----------



## xyzzy (May 7, 2020)

GN for \( 2\times n \) in STM is at most \( n(\lfloor\log_2n\rfloor+20)-12\lfloor\log_2n\rfloor \).

Algorithm for 2×n implemented in Python, together with an analysis of the algorithm in the embedded comments.

(Reminder: I'm using "matrix notation" for dimensions here, so this means two rows and n columns; a width of n cells and a height of 2.)

The gist of the algorithm is to shift all the pieces that belong to the left half of the board to the top row first (this takes \( O(n) \) moves), then move the right half of the top row into the left half of the bottom row (also \( O(n) \) moves); repeat this on the left and on the right sub-boards and eventually it will be almost solved. Sorting within a column takes at most 1 move, so finishing the solve takes \( O(n) \) additional moves. This gives a bound of \( O(n\log n) \).

The top row is fixed throughout, and only the bottom row is used for moving pieces between different columns; by making use of the same bottom-row movement for the different sub-boards simultaneously, the constant factor in the \( O(n\log n) \) bound can be made as small as \( 1/\log2 \).

More generally, for any fixed \( R \), GN for \( R\times n \) Loopover is \( O(n\log n) \). The hidden constant here depends on \( R \), so this is not a uniform improvement over my earlier result of \( RC\log^2(RC) \) with a hidden constant independent of \( R,C \). I haven't analysed this as carefully as the \( 2\times n \) case, so it might be incorrect. The algorithm follows the same idea:

Bring \( n \) of the pieces that belong in the left half to the top row, then transfer the right half of the top row to the left half of the second row.
Bring \( n \) of the pieces _not in the already-done section_ that belong in the left half to the third row, then transfer the right half of the third row to the left half of the fourth row.
Do the same thing with the 5th/6th rows, 7th/8th rows, etc. until the left half has only pieces that belong in the left half. (I think this takes \( O(R^3n) \) moves in total. Also, the last row needs special handling if \( R \) is odd.)
If \( R \) is odd, make sure the left half and the right half both have even parity. (This takes at most 7 moves.)
Recurse into the subboards until the board is sorted into columns.
Make use of Shell sort within the columns to decompose the resulting permutation into \( O(\log^2R) \) uniform-displacement involutions and finish the solve in \( O(Rn\log^2R) \) more moves.

---
(2020-05-08)

The above construction for \( 2\times n \) can be adapted to applying any _even_ permutation to a \( 2\times n \) section of a board of any size, still in \( O(n\log n) \) moves (although the hidden constant will necessarily be a lot bigger). The key adjustment we need to make is to replace any part of the algorithm that needs a column move (a 2-cycle) with a 3-cycle of the same effect.

For example, to insert a left-belonging piece from the bottom row to the top row, we split into these two cases:
If the piece in the top row one column to the right is also a left-belonging piece, do an anticlockwise cycle with the two pieces in the current column and that piece.
Otherwise, the piece in the top row one column to the right is a right-belonging piece; do a clockwise cycle instead.
(Plus two more cases if we're at the last column, where we do the mirror.)

This leads to only a constant-factor increase in the number of moves at worst.

An additional step we need to make in the algorithm is to ensure that the parities of the left and the right halves are both even. This can be done by swapping the two pieces in the rightmost column of the left half and the two pieces in the leftmost column of the right half, which takes 8 moves. This leads to \( O(n) \) additional moves.

(We're now restricted to doing only even permutations because the net movement of the rows and columns is forced to be zero.)

I initially thought this could be used as a building block for an \( O(RC\log^2\min(R,C)) \) algorithm but I made a mistake somewhere and I can't repair the argument. My idea was to use a variant of odd-even merge sort or bitonic sort to sort the board by rows, but it runs into the problem that rows that are far apart might need \( \Theta(RC) \) setup moves to bring them together first. (Relevant reading: this wall of text I wrote for DS&A homework that I'm pretty sure the TA never read…)

---

On another note, new _lower_ bound for solving LSLL (last side last layer, i.e. last row + last column), moving _only_ the last row and the last column. This is isomorphic to rotational graph puzzles of type (1+, 1, 1+) on Jaap's Puzzle Page.

(In group theory terms, this is a bound on the word metric on \( \langle(1,2,\cdots,m),(m,m+1,\cdots,m+n-1)\rangle \). It's possible to phrase everything about GN as a word metric problem, but the general case is messy to describe and we gain nothing. We also gain nothing here (lol) but at least it's easy to describe. Note that group theory is often more concerned with the word metric of finitely-generated _infinite_ groups, where the choice of generators doesn't matter much, while this post is more concerned with asymptotic bounds on the word metrics of a family of _finite_ groups wrt specific generating sets.)

First, the counting argument bound. There are at most four possible choices of move to make (up, down, left, right) and either \( (R+C-1)! \) or \( (R+C-1)!/2 \) states, so this gives a lower bound of \( \log_4((R+C-1)!/2)=\Omega((R+C)\log(R+C))\equiv\Omega(\max(R,C)\log\max(R,C)) \). The constant factor can be tightened by counting canonical move sequences more carefully (see e.g. posts #6 and #8 in this thread).

*The new result:* GN for 2-gen LSLL is \( \Omega\left(\max\left(\frac{R^2}C,\frac{C^2}R\right)\right) \) as \( R+C\to\infty \). Note that this bound is worse than the counting argument bound if \( R\ll C\ll R \) (i.e. the aspect ratio is bounded), but is better than the counting argument bound if we fix \( R \) and let \( C \) increase.

The first thing we need to do is to change perspective: instead of moving the bottom row, we imagine that we keep the bottom row fixed and move all the other rows instead. If this:

```
. . . . . a
. . . . . b
. . . . . c
d e f g h i
```
is a solved state, then so are all of these:

```
. . . . . a
. . . . . b
. . . . . c
d e f g h i

. . . . a .
. . . . b .
. . . . c .
e f g h i d

. . . a . .
. . . b . .
. . . c . .
f g h i d e

. . a . . .
. . b . . .
. . c . . .
g h i d e f

. a . . . .
. b . . . .
. c . . . .
h i d e f g

a . . . . .
b . . . . .
c . . . . .
i d e f g h
```

(This is _only_ a matter of changing perspective to make analysis easier; on the actual Loopover board, we're still making moves on only the bottom row while leaving the other rows untouched.)

Now consider the _sum of horizontal distances_ (SOHD), keeping the left-right wrapping in mind and ignoring all pieces that don't belong to LSLL. Given any LSLL state, we can compute its SOHD from any one of the solved states, and that will give a lower bound on the number of moves needed to bring it to _that_ solved state. To get a correct lower bound for the underlying Loopover board, we need to use the minimum of the SOHD over all solved states. As an example, consider the following LSLL state:

```
. . . . . i
. . . . . c
. . . . . e
a b d f g h
```
The SOHD to the six solved states (listed above) are 10, 17, 20, 17, 10 and 7 respectively, so the minimal SOHD to solved is 7. (I calculated this by hand; it might not be correct, but you get the idea.)

Each horizontal move affects the horizontal distance of \( R-1 \) pieces by at most 1] each, so the SOHD changes by at most \( R-1 \) each move. This gives a lower bound of \( \lceil\text{minimal SOHD}/(R-1)\rceil \) horizontal moves needed. In the above example, this is \( \lceil7/3\rceil=3 \) moves.

How large can the minimal SOHD be? Consider the reversal permutation on the bottom row, with the other pieces in the column solved. (This might not be a solvable state due to parity if both \( R \) and \( C \) are odd.) The SOHD for the row's pieces (i.e. ignoring the column) to _any_ of the solved states is:

\( \frac{(C-1)(C+1)}4 \) if \( C \) is odd. (The horizontal distances will be some arrangement of 0 and two copies of \( 1,\cdots,(C-1)/2 \). Proof: exercise.)
\( \frac{C^2}4 \) if \( C\equiv0\pmod4 \).
\( \frac{(C-2)(C+2)}4 \) if \( C\equiv2\pmod4 \).

When \( C=2 \), then \( C^2/R\to0 \) as \( R+C\to\infty \), so it is "trivially" true that we have a lower bound of \( \Omega(C^2/R) \).

Otherwise, when \( C\ge3 \), the SOHD for the row's pieces is \( \Theta(C^2) \). The reversal permutation may not lead to a solvable state, but swapping any two adjacent pieces to fix parity changes the SOHD by at most 2, which is still \( \Theta(C^2) \). (Exercise: As written, this is not an airtight argument. I'm lazy, but maybe you're not; work out the details.) Since \( R=\Theta(R-1) \), we have a lower bound of \( \Omega(C^2/R) \) here as well.

By transposing the above argument, we get a lower bound of \( \Omega(R^2/C) \); these can be combined to get \( \Omega\left(\max\left(\frac{R^2}C,\frac{C^2}R\right)\right) \).

An interesting consequence of this lower bound is that when solving LSLL on a \( 2\times n \) board, restricting yourself to not use the other columns means you _have_ to do \( \Omega(n^2) \) moves in the worst case, while using the other columns lets you solve it in \( O(n\log n) \) moves.


----------



## xyzzy (May 19, 2020)

First _explicit_ example of a 5×5 state that requires 22 moves to solve:

```
S T P Q R
X M U V W
D E Y B C
I J F G H
N O K L A

(as a zero-indexed list)
18, 19, 15, 16, 17,
23, 12, 20, 21, 22,
3,  4,  24, 1,  2,
8,  9,  5,  6,  7,
13, 14, 10, 11, 0,
```
Optimal solution (SiGN-like notation): 2U2' 3U' 4U' 5U' 1L' 2L' 3L' 4L' 5L2' 5U' 4L' 3U' 4U' 3L' 2U' 1L' 2L' 1U' 5L' 4U' (22 STM)

It was already known that 5×5 STM GN ≥ 22, but only via "nonconstructive" counting arguments. Finite counting arguments are constructive only in a weak sense: they tell you there are some 22-move states out there, so you could find them via brute force in principle, but they don't tell you how to find them _quickly_.

This was found by using a slightly enhanced version of the Manhattan distance heuristic. With the usual MD heuristic, we compute the sum of each tile's MD and then divide by 5, since that's the maximum change to the MD, and finally round up to the nearest integer. We can squeeze more precision out of this approach by upgrading to the walking distance heuristic (see spoilerbox in post #6 and the link within), but WD seemed a bit troublesome to implement performantly. After some thinking I came up with this compromise that I'll call the enhanced MD (EMD) heuristic.

In EMD, we don't immediately sum up each tile's distance; instead, we compute the number of tiles that are in the correct column, the number that need to move one cell left, the number that need to move two cells left, the number that need to move three cells left (= two cells right), and the number that need to move four cells left (= one cell right). This gives a 5-tuple \( (x_0,x_1,x_2,x_3,x_4) \) adding up to 25 (since there are 25 tiles), with the additional constraint that the weighted sum \( \sum_{i=0}^4ix_i \) is divisible by 5 (since each move has zero change to this sum mod 5). There are 4751 such 5-tuples, and we can do a breadth-first search among these 5-tuples.



Spoiler: distribution





```
total states: 4751
distance 0: 1 nodes / 1 weighted
distance 1: 2 nodes / 106260 weighted
distance 2: 17 nodes / 1046003800 weighted
distance 3: 101 nodes / 1092278370160 weighted
distance 4: 385 nodes / 260012086280560 weighted
distance 5: 715 nodes / 6047479429371242 weighted
distance 6: 1069 nodes / 25764503650691770 weighted
distance 7: 1083 nodes / 23320404112024440 weighted
distance 8: 804 nodes / 4110971424442750 weighted
distance 9: 440 nodes / 100044933950310 weighted
distance 10: 130 nodes / 135814034332 weighted
distance 11: 4 nodes / 115000 weighted
average distance (weighted): 6.423998
```
It is a priori not obvious whether every one of these 5-tuples is actually possible on a real Loopover board. I'm guessing that's the case, but I have no proof. It's also not relevant for our current purposes: if there's an "impossible" tuple, that would make EMD weaker, which retains admissibility.

The weighting here is approximate, with each 5-tuple \( (a,b,c,d,e) \) being weighted by \( \frac{25!}{a!b!c!d!e!} \). This is definitely not the exact weight (which is hard to compute), but it's probably close enough. I'll try a Monte Carlo approximation later on to see how accurate this approximation is.

Edit (2020-05-23): Actual distribution, from 10^8 samples:

```
total samples: 100000000
distance 0: 0 samples
distance 1: 0 samples
distance 2: 7 samples
distance 3: 2662 samples
distance 4: 503231 samples
distance 5: 10467480 samples
distance 6: 42636133 samples
distance 7: 38886264 samples
distance 8: 7297714 samples
distance 9: 206104 samples
distance 10: 405 samples
distance 11: 0 samples
average distance (weighted): 6.426197
```
The tails of the distribution are underestimated with the multinomial approximation, but distances 5 to 8 are fairly close and the weighted averages obtained with sampling and with the multinomial approximation are very close.



The original MD heuristic has an average of about 6.4 and a maximum of 10 (per axis). While EMD prunes only very slightly further on average, the maximum is one higher. The four distance-11 5-tuples are:
(0, 1, 3, 21, 0)
(0, 0, 21, 3, 1)
(0, 2, 1, 22, 0)
(0, 0, 22, 1, 2)

The board given at the start of this post was constructed to have (0,0,22,1,2) both horizontally and vertically, which means that it needs at least 11 horizontal moves and 11 vertical moves to be solved, for a total of 22 moves. This was done by starting with the solved board and shifting everything two cells down and two cells right, then applying a 3-cycle along the diagonal. Feeding this to an optimal solver, it turns out that optimal is indeed 22 moves.

---

Note that MD ≤ EMD ≤ WD _always_ holds. Just as EMD is a refinement of MD, WD can be thought of as a refinement of EMD. Compared to EMD, it's harder to start from a WD pattern and manually construct an example state that has that specific WD pattern, which was also part of why I decided to implement EMD first.

While WD is still feasible to implement for 5×5, I don't think it's feasible for 6×6. On the other hand, EMD is feasible up to maybe 8×8. But that said, EMD also provides very little improvement over MD on average. Memory requirement for MD is basically nothing (you can speed it up with a lookup table, but that's optional); memory requirement for EMD is roughly n^(2n); memory requirement for WD is… hard to estimate, but likely around n^(n^2).

The analogue of EMD on 15-puzzle is just the same thing as the original MD heuristic, since on 15-puzzle we're only ever moving one piece at a time and there's no looping around the sides.

---

I'm running my optimal solver on the transposed state

```
A F K P U
B G L Q V
C H M R W
D I N S X
E J O T Y
```
and after a few hours it's finished exhausting depth 21, so this must also take at least 22 moves. It will probably take over a day to exhaust depth 22 (if there are no depth-22 solutions). My naïve expectation is that this is either an antipode or close to it, considering that on 4×4, the transposed state is believed to be an antipode. (Thanks to symmetry, we do know it must be a "local maximum": applying any one move must reduce its depth.)

---
(2020-07-15)

Not writing a new post since there isn't any "concrete" result yet. Been reading into AKS sorting network and Paterson's simplification thereof, and at first glance it looks like it _might_ lead to a decomposition into \( O(\log N) \) uniform-distance involutions, but the two main issues are that (i) I don't know whether the ε-halver / (ε, α)-halver proofs can be adapted to comparators of the same gap (the original proofs are probabilistic and I suspect the answer is "yes but the constant factor is much worse") and (ii) the actual structure of the AKS sorting network involves rearranging the data into a tree and moving elements up and down the tree at every iteration, and this motion seems to be not doable within a constant number of u-d involutions per iteration.

Speaking of which, I tried to count the number of u-d involutions on \( n \) (as in, the set of integers \( \{0,1,2,\cdots,n-1\} \)) and I believe it's \( (1+o(1))\phi^{n+2} \) (where \( \phi\approx1.618 \) is the golden ratio), but I'm having some difficulty bounding the tail terms in a sum rigorously. Instead, here's a much less involved argument for an upper bound of \( (n-1)\cdot2^{n-1} \) (for \( n\ge2 \)) on the number of u-d involutions:

Among the u-d involutions, there are \( n-1 \) choices for what the gap can be: anything from \( 1 \) to \( n-1 \). Fix a choice. For any u-d involution \( \pi \) with a chosen gap \( g \), we can convert it to an \( n \)-bit binary string \( s \) via \( s_k:=\begin{cases}0&\text{if }\pi(k)=k\\1&\text{if }\pi(k)\ne k\end{cases} \). Since \( \pi \) is an involution, all non-fixed points come in pairs, so the resulting bit string must be one of \( 2^{n-1} \) bit strings with even parity.

We claim that, given the gap \( g \), this conversion is reversible (and hence there are at most \( 2^{n-1} \) u-d involutions with gap \( g \)). To recover \( \pi \) from the bit string, we pair up the '1' bits in the bit string thus: iterate over the bits and every time we encounter an unpaired '1' bit, we pair it up with the '1' bit \( g \) positions later. Once all the '1' bits are paired up, simply set the output \( \pi' \) to be the permutation swapping the elements of those pairs.

Suppose for contradiction that this fails to recover the original \( \pi \), i.e. there is some '1' bit that gets paired with the wrong '1' bit. Let \( 0\le i\le n-1 \) be the smallest index of a '1' bit that is assigned the wrong partner. The only possible partners it can be assigned are \( i-g \) and \( i+g \). In the former case, \( i-g \) is also assigned the wrong partner, contradicting minimality. In the latter case, the correct partner of \( i \) must then be \( i-g \) (i.e. \( \pi(i)=i-g \)). Since \( \pi(i-g)=i\ne i-g \), it follows that there is a '1' bit at position \( i-g \). Since the algorithm skipped over this '1' bit, it must have already been paired, and hence it was paired with \( i-2g \), which also means that it was incorrectly paired, again contradicting minimality of \( i \). Therefore the algorithm always recovers the original u-d involution correctly.

For each of the \( n-1 \) gaps, there are at most \( 2^{n-1} \) u-d involutions with that gap, and hence there are at most \( (n-1)2^{n-1} \) u-d involutions on \( n\ge2 \) elements. While there are some "obvious" inefficiencies in this encoding, this is good enough for our purposes, which is…

*Theorem*: The smallest value of \( m \) such that every \( \pi\in S_n \) can be written as the composition of \( m \) uniform-distance involutions is \( \Omega(\log n) \).

Proof: Standard counting argument: \( \Omega\left(\frac{\log n!}{\log O((n-1)2^{n-1})}\right)=\Omega\left(\frac{\Theta(n\log n)}{O(n)}\right)=\Omega(\log n) \).

The consequence of this theorem is that in the framework of using u-d involutions to solve a Loopover board, unless we restrict to special types of u-d involutions or otherwise figure out a way to do a u-d involution in \( o(N) \) moves, this approach will never be able to improve the upper bound below \( O(N\log N) \). Even if we somehow manage to adapt the AKS sorting network to get an \( O(N\log N) \) upper bound for GN, we need a new technique/approach to push the upper bound even lower.

---

This kind of doesn't really belong anywhere, but I wrote a 5×5 two-phase solver over the last two weeks and it manages to find solutions in the 23-29 range consistently. There's a huge gap between this and our current upper bound (53 moves, three phases with optimisations), but the sizes of the two phases I'm using in the solver are kind of big (25!/16! ~ 7e11 and 16!/2 ~ 1e13) so I'm not really expecting much improvement soon.

---
(2020-07-29)

More partial results. Will split this into a separate post if something useful comes out of it.

Last row + last column can always be solved in at most 16 moves if we allow moving the second-last row and second-last column as well. This improves on the bound of 17 moves in the Loopover Research spreadsheet. 16 moves is tight, but there is essentially only one LRLC state that requires at least 16 moves even when all moves are allowed, up to symmetry.


Spoiler: distribution



0: 1
1: 4
2: 12
3: 32
4: 88
5: 240
6: 644
7: 1724
8: 4460
9: 10462
10: 22081
11: 39686
12: 53537
13: 39670
14: 8420
15: 369
16: 10
average: 11.499840

These are optimal within moving only last two rows + last two columns; the 9!/2 = 181440 solves took about 7 seconds to complete.





Spoiler: the 16-movers



0,1,2,3,9,5,6,7,8,19,10,11,12,13,4,15,16,17,18,14,22,20,23,21,24,
0,1,2,3,14,5,6,7,8,4,10,11,12,13,19,15,16,17,18,9,21,23,20,22,24,
0,1,2,3,14,5,6,7,8,9,10,11,12,13,19,15,16,17,18,4,23,22,21,20,24,
0,1,2,3,19,5,6,7,8,9,10,11,12,13,4,15,16,17,18,14,23,22,21,20,24,
0,1,2,3,19,5,6,7,8,14,10,11,12,13,9,15,16,17,18,4,22,21,23,20,24,
0,1,2,3,19,5,6,7,8,14,10,11,12,13,9,15,16,17,18,4,23,21,20,22,24,
0,1,2,3,20,5,6,7,8,21,10,11,12,13,22,15,16,17,18,23,19,14,9,4,24,
0,1,2,3,21,5,6,7,8,23,10,11,12,13,20,15,16,17,18,22,9,19,4,14,24,
0,1,2,3,22,5,6,7,8,20,10,11,12,13,23,15,16,17,18,21,14,4,19,9,24,
0,1,2,3,23,5,6,7,8,22,10,11,12,13,21,15,16,17,18,20,4,9,14,19,24,

#2 has a 15-move solution: 5U 5L' 5U 4U' 4L 1U 5L' 5U2' 1U' 5L 4L' 4U 5U 5L' (optimal)
#1 is the inverse of #2, so it's also a 15-mover.

#6 has a 15-move solution: 4U 5U' 5L' 5U' 5L' 1L 5U' 5L 5U2' 5L 5U' 1L' 4U' 5L' (optimal)
#5 is the inverse of #6, and #3/#4 are mirrors of #5/#6, so they're also 15-movers.

#7 has a 14-move solution: 1U 5L2' 5U' 5L' 5U' 1L' 4U' 5L' 5U' 5L' 4U 1L 1U' (optimal)
#10 is the inverse of the #7, so it's also a 14-mover.

#8 and #9 (inverses of each other) are truly 16-movers even with all moves allowed.



Going from 3×3 block to 4×4 block can be done in at most 18 moves.


Spoiler: distribution



distance 0: 1 nodes
distance 1: 4 nodes
distance 2: 20 nodes
distance 3: 99 nodes
distance 4: 446 nodes
distance 5: 1975 nodes
distance 6: 8480 nodes
distance 7: 34865 nodes
distance 8: 136901 nodes
distance 9: 500300 nodes
distance 10: 1658797 nodes
distance 11: 4805567 nodes
distance 12: 11120723 nodes
distance 13: 17679617 nodes
distance 14: 15542104 nodes
distance 15: 5611876 nodes
distance 16: 545774 nodes
distance 17: 9995 nodes
distance 18: 56 nodes



Depth distribution for randomly sampled 2r2c states. 23-move 4-gen states exist, but are much rarer than 22-movers. 24-movers probably exist too; I suspect GN for 4-gen 2r2c is between 24 and 26.


Spoiler: distribution (200000 samples)



8: 1
9: 1
10: 0
11: 1
12: 19
13: 72
14: 275
15: 1140
16: 4104
17: 13783
18: 37377
19: 69647
20: 61047
21: 12253
22: 280
average: 19.013045
This took about five hours (15900 seconds) to complete.


----------



## xyzzy (Jul 30, 2020)

Continuing from the previous post:

If you want to play with it, I've uploaded my 4×4 and 5×5 solver to GitHub. (The 4×4 optimal solver is _not_ the fast one I mentioned earlier in this thread that needs 4 GB of RAM to run; it's much slower, but I believe it's still faster (and easier to use) than the ksolve++ one. Some kind of Java 8+ runtime is needed.)

Following coolcomputery's method (post #9 in this thread), I've run a search on last two rows two columns to bound the diameter by T = 29. (This is restricted to using only moves of the two free rows and two free columns.)


```
. . . D E
. . . I J
. . . N O
P Q R S T
U V W X Y
```

There are 16!/2 states (all even permutations are legal), divided into 16!/9! = 57657600 right cosets of size 9!/2 = 181440 each, with respect to the subgroup Alt({E, J, O, T, Y, X, W, V, U}). We first precompute solutions for all positions in the solved coset; per the previous post, the optimal solution is always at most 16 moves.

For each coset \( C \), we do the following:

1. Check if the coset's distance (between 0 and 18, incl.) is at most T−16. If it is, then we can apply any optimal solution for solving DINSRQP (≤T−16 moves), followed by any optimal solution for the last row last column (≤16 moves; see last post) to get a full solution of length ≤T moves, and we're done. If not, proceed to the next step. (When T is 29 or higher, this lets us skip checking many cosets altogether.)

2. Find all optimal solutions for solving DINSRQP for that coset; let these be \( \{s_0, s_1, \cdots, s_{N-1}\} \), so (the permutations induced by) \( s_i^{-1} \) are all elements of the right coset, and in particular, we have a bijection \( \operatorname{Alt}(\mathsf{E}, \mathsf{J}, \mathsf{O}, \mathsf{T}, \mathsf{Y}, \mathsf{X}, \mathsf{W}, \mathsf{V}, \mathsf{U}\})\to C \) given by \( p\mapsto ps_0^{-1} \). We use this to enumerate the elements of the coset. For each state \( ps_0^{-1} \) in the coset, we check if there is some DINSRQP solution \( s_i \) such that \( |s_i|+|ps_0^{-1}s_i|\le T \). If there is, we are done (at least one optimal solution to DINSRQP leads to a full solution of length ≤T). If not, proceed to the next step. (This filters out 90% of the states that reach this step. The permutations \( s_0^{-1}s_i \) are precomputed.)

3. For the states \( ps_0^{-1} \) for which _no_ optimal solution of DINSRQP leads to a full solution of length ≤T, try the first optimal solution of EJOTPQR, the first optimal solution of NIDXWVU, and the first optimal solution of OJEYUVW, to see if any of these lead to a full solution of length ≤T. If yes, we are done. If not, try the first optimal solutions of DINSRQP, EJOTPQR, NIDXWVU, OJEYUVW on the inverse \( s_0p^{-1} \). If one of these works, we are done. If still not, proceed to the next step. (At T=29, this filters out every state that reaches this step, but this is not necessarily the case for lower thresholds.)

4. For the states \( ps_0^{-1} \) that make it through the earlier filters, run an optimal solver. Increase T and continue if any state is found to not be solvable within T moves. (The optimal solver here is a faster version of phase 2 in the two-phase solver I put on GitHub; this uses more memory and a lot more initialisation time, in exchange for being about eight times as fast.)

I first ran the algorithm with T=27 for a few hours, and it finished searching through cosets 0..694739 with no states needing at least 28 moves. (There is no special meaning to 694740; that's just where I decided it would take too long to finish.) For the remaining cosets (694740..57657599), the algorithm was run to completion with T=29, with no states needing at least 30 moves. A total of around 13 billion "solves" was done in around 9.6 hours. Information needed to restart the computation was logged every 100 seconds.

Threshold 27:
elapsed: 10216.071687
cosets checked: 528337 (166403 skipped, 694740 total)
5468064278 alt solves, 563420944 two-phase solves, 522 optimal solves

Threshold 29:
elapsed: 24341.288339 (finished)
cosets checked: 21467972 (36189628 skipped, 57657600 total)
7248809427 alt solves, 210763133 two-phase solves, 0 optimal solves

(Potential optimisation: The state space has sixteen symmetries/antisymmetries; for any state that makes it past step 2, check if applying a symmetry/antisymmetry leads to the DINSRQP coset index becoming smaller. If yes, then we've already checked that coset earlier, so we can skip this state too. This probably cuts down work needed by a factor of around 5-10, and may allow a T = 28 run to finish within a day.)

---

This alone does not improve the GN upper bound for 5×5 yet (25 + 29 = 54 is worse than coolcomputery's bound of 53 moves), but I believe I can push the upper bound for solving a 3×3 block down from 25 to 20-21 moves. In practice, it's usually solved in 16 or less moves.

Consider the distribution for solving the 2×3 block ABC FGH (see coolcomputery's post; the numbers there match mine). Instead of fully solving ABC FGH and then solving KLM, we take any solution for ABC FGH and apply all but the last 5 moves (in STM). (*) If the solution is already shorter than 5 moves, we do nothing. Since an optimal solution for ABC FGH is at most 13 moves, this "preprocessing" step takes at most 13−5 = 8 moves.

Now there are (1 + 10 + 94 + 880 + 7558 + 58432 = 66975) possible combinations of locations for the ABC FGH pieces; do a breadth-first search on the 66975 × 19!/16! = 389392650 possible combinations if we include the KLM pieces as well, where we allow only moves that keep the ABC FGH pieces solvable within 5 moves. (Double-tile moves that "jump over" a state where ABC FGH temporarily goes above 5 moves are not allowed.) The maximum distance here is 15 moves.


Spoiler: solving ABC FGH KLM, starting from ABC FGH at most 5 moves



total states: 389392650
distance 0: 1 nodes
distance 1: 12 nodes
distance 2: 132 nodes
distance 3: 1460 nodes
distance 4: 15572 nodes
distance 5: 159704 nodes
distance 6: 1001591 nodes
distance 7: 4703914 nodes
distance 8: 18390066 nodes
distance 9: 54700075 nodes
distance 10: 107765251 nodes
distance 11: 122764990 nodes
distance 12: 66333489 nodes
distance 13: 12907702 nodes
distance 14: 643867 nodes
distance 15: 4824 nodes



The 4824 15-move states were then separately solved with an optimal ABC FGH KLM solver; all can be solved in at most 14 moves.


Spoiler: optimal move counts for the 15-move states from above



11:	24
12:	458
13:	2582
14:	1760



Therefore solving ABC FGH KLM can be done in at most 8 + 14 = 22 moves. This reduces the *upper bound for 5×5 GN* to 22 + 29 = *51 moves*.

(*) We could use other thresholds. At one extreme, if we set the threshold to 0, that's the same thing as fixing the first two rows and the first three columns; solving KLM takes at most 12 moves there, giving an upper bound of 13+12 = 25 moves. Thresholds of 1 to 4 moves (incl.) improve the upper bound to 24 moves. A threshold of 5 moves improves it to 23. Prior to the computation, I was naïvely hoping this would already be good enough, but it unfortunately wasn't. A threshold of 6 moves is roughly on the edge of what my computer can handle (~7.5 GB memory needed) so I might try that later.

---
(2020-08-07)

Source code to replicate the results of this post (to be used with the main loopsolver code base). It's even uglier than the rest of the loopsolver code, sorry.

Phase 2 (solving the last two rows + last two columns) has been reduced to 28 moves. The computation was done "multithreaded", by which I mean I divided the number of cosets by three (roughly), ran three separate instances of the program, and (manually) split up the search on the largest chunk left whenever one of the three instances completed. A total of 82,926,755,238 scrambles was processed in about 149,117 seconds (= 41.4 hours) of CPU time, or about 15 hours of real time (I paused the computation for about an hour). This is without any additional optimisations from what I described above.

78,602,637,235 scrambles (94.79%) were solved in ≤28 moves by using alternate DINSRQP solutions. 4,324,117,953 scrambles (5.21%) were solved in in ≤28 moves by applying a symmetry/antisymmetry first, then applying the first optimal DINSRQP solution. 50 scrambles (0.00000006%) were solved directly.

As a sanity check, 82,926,755,238 matches the number obtained by convolving the distributions for DINSRQP and for last row last column together, and taking the tail sum.

This reduces the overall bound to 22 + 28 = *50* moves.


----------



## rokicki (Jun 12, 2021)

I've run loopover 4x4 (and some other sizes) in both STM and MTM and these are the results.
Numbers in parentheses are the count of antipodes. For 3x6 I give a lower and upper bounds.

I used a coset solver (twsearch with modifications) for the 4x4 and 3x6 results.

STM:


234567824 (1)7(3)10(4)13(205)16(2302)20(1680)2338(2475)14(6)17(15)19..23418(32)

MTM:


234567824 (1)7(3)8(2264)12(315)14(288)18(196)1938(2475)13(2)14(6415)16..20414

Distance 16 move in MTM on 3x6:
1H 2V3 4H' 3V' 2H 1H' 2V2' 4H 3V 1H' 2V2' 6H' 1V3 6H' 2H 2V2

Distance 19 move in STM on 3x6:
1H 1V' 2H' 3V 5H' 2V 2V 4H 3V 2H 3V 2V' 2H' 1H 1V 1V 4H 1H' 3V

I completed all of this quite some time ago but just haven't gotten around to writing it up.

On the MTM antipodes for 4x4: I think I found too many to easily count.

For 4x4, the subgroup 1H,3H,1V,3V has tremendous symmetry that can be exploited.


----------



## xyzzy (Jun 12, 2021)

rokicki said:


> For 4x4, the subgroup 1H,3H,1V,3V has tremendous symmetry that can be exploited.


Just to check:

The symmetries are:
- (×2) switch 1H with 1H' = switch B and D tiles
- (×2) switch 3H with 3H' = switch J and L tiles
- (×2) switch 1V with 1V' = switch E and M tiles
- (×2) switch 3V with 3V' = switch G and O tiles
- (×4) translate
- (×4) rotate
- (×2) mirror
- (×2) transpose
for a total of 512 128 symmetries, right?
(edit: fixed overcounting, but also see below replies)

I had the idea of using the subgroup where the pieces are separated like a checkerboard pattern:

```
A . C .
. F . H
I . K .
. N . P

. B . D
E . G .
. J . L
M . O .
```
(So the ACFHIKNP pieces are all among those eight locations, and likewise the BDEGJLMO pieces are among the other eight locations.) This has "only" 128 symmetries, iirc: 16 translation, 4 rotation, 2 reflection.


----------



## rokicki (Jun 12, 2021)

Actually, I only see 32 symmetries for the 1H,3H,1V,3V subgroup.

This subgroup has size 12! or 479M. The number of cosets is 16!/12! or 43680, but there are only 1556 unique with respect to symmetry, and each individual coset easily fits into memory. That's pretty much all I did; I ran the 1556 different cosets.

Here's a sample run:


```
[email protected] twsearch % ./twsearch --maxdepth 9 --coset 1H,3H,1V,3V "2H 4H 1V 1H 3H2 3V 3H" lo44r.tws
# This is twsearch 0.2 (C) 2020 Tomas Rokicki.
# ./twsearch --maxdepth 9 --coset 1H,3H,1V,3V 2H 4H 1V 1H 3H2 3V 3H lo44r.tws
Created new moves 1H2 1H' 2H2 2H' 3H2 3H' 4H2 4H' 1V2 1V' 2V2 2V' 3V2 3V' 4V2 4V'
Rotation group size is 128
State size is 20922789888000 log2 44.2501
Requiring 61 bits 8 bytes per entry; 8 from identity.
Found 9 canonical move states.
Calculated canonical states in 0.0012269
State size is 43680 log2 15.41468523580722
Requiring 46 bits 8 bytes per entry; 8 from identity.
Coset size is 479001600
For memsize 8470184192 bytesize 8192 subshift 42 memshift 49 shardshift 9
Initializing memory in 0.0001358985900878906
Filling table at depth 0 with val 0 saw 1 (1) in 0.0001981258392333984
Filling table at depth 1 with val 0 saw 12 (25) in 0.0001058578491210938
Filling table at depth 2 with val 0 saw 131 (421) in 0.0002961158752441406
Filling table at depth 3 with val 1 saw 1273 (6685) in 0.003032922744750977
Doing solve . . .
Filling table at depth 4 with val 2 saw 6118 (87434) in 0.01086091995239258
At 7 total 218 (222)
Prepass for depth 8 see 2816 in 0.05623316764831543
At 8 total 11594 (10120)
Prepass for depth 9 see 131959 in 0.03109288215637207
Depth 9 finished in 9.189453125
At 9 total 343656 (282232)
Prepass for depth 10 see 3521561 in 0.5305309295654297
Prepass for depth 11 see 24779836 in 3.570284128189087
Prepass for depth 12 see 139082456 in 21.69013595581055
Prepass for depth 13 see 410834092 in 110.2196960449219
Prepass for depth 14 see 478970711 in 16.28442788124084
Prepass for depth 15 see 479001600 in 0.01905488967895508
```


----------



## xyzzy (Jun 12, 2021)

Ah, I think I get it: the 1H 3H 1V 3V subgroup does have the "weird" symmetries that preserve distance in STM and MTM, but these symmetries don't preserve distance in the full group, so you can't use them to reduce the number of cosets to check.


----------



## rokicki (Jun 12, 2021)

I'm confused; the symmetries that it has are *precisely* those that map the generators of the subgroup directly
onto, and thus they are precisely the ones you can reduce the set of symmetries by.

For instance, conjugating by 1-4H2 (that is, shifting the whole puzzle two left or right) leaves the H moves alone,
but remaps the V moves (1V <=> 3V, 2V <=> 4V). Thus, conjugation by this rotation does not change the coset
distance distribution because it doesn't change the subgroup generating set.

On the other hand, conjugating by 1-4H maps 1V to 2V, so the subgroup generating set is mapped to moves that
leave the subgroup, so you can't reduce by conjugations by 1-4H.


----------



## xyzzy (Jun 12, 2021)

In the subgroup, we have the FHNP pieces solved (no other restriction on the other 12 pieces):

```
. . . .
. F . H
. . . .
. N . P
```
The generators are 1H, 3H, 1V, 3V.
Then conjugating these generators by a swap of these two locations:

```
. X . X
. . . .
. . . .
. . . .
```
gives 1H', 3H, 1V, 3V respectively. So this swap _is_ a symmetry, but only within the subgroup generated by 1H, 3H, 1V, 3V. (And now that I've written this out, it seems I overcounted the symmetries initially: the horizontal reflection symmetry (1H↔1H' and 3H↔3H') is the composition of the 1H↔1H' and 3H↔3H' symmetries.)

Conjugating 2V or 4V by the above swap produces something that's not a generator anymore, so it's not a symmetry within the full group of 16! permutations.


----------



## coolcomputery (Jun 26, 2021)

6x6 GN is at most 101.
I reduced the GN of 4x5->5x5 + 5x5->6x6 to 38, by applying at most 5 prefix moves to every scramble that would naively take >38 moves. There were 249347110 total scrambles, which took 4294.610 seconds to process (including making the two BFS trees). Referring to this earlier post, this means that the GN of 6x6 is at most *27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 15 (4x4->4x5) + 38 (4x5->5x5->6x6)=101.*
I've also rewritten my BFS tree and tree optimization programs and put them on https://github.com/coolcomputery/Loopover-Brute-Force-and-Improvement
UPDATE (2021-06-27): 6x6 GN is at most 100.
This time I reduced the GN of 4x4->4x5->5x5 to 28, by applying at most 7 prefix moves 6 prefix moves. There were 709300008 total scrambles, which in total took 3167.242 seconds 42296.808 seconds. by applying at most 6 prefix moves. Thus, 6x6 GN is at most *27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 28 (4x4->4x5->5x5) + 24 (5x5->6x6)=100.*
Doing 4x4->5x5 brute-force requires tracking 20!/11!=~60 billion states, which is too big for Java arrays to be use to track whether a state has been visited before or not during the BFS. It _might_ be possible to replace Java arrays with several thousand or so I/O files, but that will take a lot of work to program and will probably result in a very slow BFS.
UPDATE (2021-06-28): 6x6 GN is at most 99.
I further reduced the GN of 4x4->4x5->5x5 to 27, by applying at most 7 prefix moves. There were 2821027911 total scrambles, which took 16478.048 seconds to process. *27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=99.*
UPDATE (2021-06-29): 6x6 GN is at most 98.
This time I reduced the GN of 0x0->2x2->3x3 to at most 26. 5629775526 total scrambles took 28655.157 seconds to process. *26 (0x0->2x2->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=98.*
Currently, trying to reduce 4x4->4x5->5x5 to 26 moves results in java.lang.OutOfMemoryError because my program is forced to try generating all prefix move sequences consisting of 9 moves.


----------



## coolcomputery (Jul 1, 2021)

5x5 GN is at most 49.
I reduced the GN for 0x0->2x2->3x3 (i.e. solving AB FG, then C H KLM) to at most 21 moves., by considering every scramble of the pieces ABC FGH KLM that would take >21 moves by naively applying solving the two phases, applying at most 2 prefix moves, and solving the two phases of the resulting scramble. In total, 2922776484 scrambles took 3625.230 to process.
Since the GN for 3x3->4x4->5x5 is already known to be at most 28, this reduces the 5x5 GN to at most *21+28=49*.
*UPDATE (2021-07-01):* 5x5 GN is at most 48.
I further reduced the GN for 0x0->2x2->3x3 to at most 20 moves, this time by applying at most 3 prefix moves. 22,088,910,396 scrambles took 37362.881 seconds to process. *20+28=48*.
*UPDATE (2021-07-06): * 5x5 GN is at most 47.
I further reduced the 0x0->2x2->3x3 GN to 19 moves, using at most 5 prefix moves. 88,669,385,160 scrambles took 438839.540 seconds to process. *19+28=47*.
Below is the stdout of the program I used.


Spoiler: stdout



5x5
[11111, 00111, 00011],[11111, 00111, 00011]
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, 1, 5, 6]
ncombos=303600
0:1
1:8
2:64
3:492
4:2974
5:14584
6:49562
7:97448
8:95449
9:39425
10:3592
11:1
#reached=303600
D=12
total time=703
-1 -1 0 1 2
-1 -1 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
[0, 3, 6, 7, 8]
ncombos=2441880
0:1
1:4
2:20
3:105
4:508
5:2386
6:10441
7:41483
8:143791
9:398056
10:738804
11:744707
12:321693
13:39351
14:530
#reached=2441880
D=15
total time=3905
threshold=19, P=1
#mvseqs=20
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
NOT REDUCED:
..FB.
..C.G
.....
K....
LM.AH
t=0; [0, 0, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, 1] [0, 0, 1]
t=1; [0, 4, -1] [1, 4, -1] [0, 4, -1] [1, 4, -1] [0, 2, -1] [1, 4, -1] [0, 3, -1] [0, 3, -1] [0, 2, 1] [1, 3, -1] [1, 2, 1] [1, 2, 1] [0, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=2
#mvseqs=320
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 4194697
13591 14330036
20566 22731789
23454 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
NOT REDUCED:
LM.B.
H...G
.....
C....
K.FA.
t=0; [1, 2, 1] [0, 0, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, 1] [0, 0, 1]
t=1; [1, 4, 1] [0, 3, -1] [1, 4, 1] [1, 2, -1] [0, 4, -1] [0, 4, -1] [1, 3, 1] [1, 3, 1] [0, 2, 1] [1, 3, 1] [1, 2, 1] [0, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=3
#mvseqs=4640
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 5639768
13591 15895846
20566 24364229
22136 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1843207
13591 7205813
20566 12453106
28261 17683133
36945 23931376
46782 30156822
57912 38056072
70470 49324924
84594 60226892
100427 74363891
118121 89821904
137835 107773693
159738 126368443
184009 147449049
210839 170503217
240428 196172792
272990 223179404
308753 252034290
347956 282139166
390855 315699165
437717 357259160
488829 407675011
544492 457802155
605024 510049433
670764 564532796
742065 621033191
819305 690464104
902880 761328186
993208 830751427
1090730 916032486
NOT REDUCED:
.LA.C
.....
....G
...BH
KM.F.
t=0; [1, 4, -1] [1, 3, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, -1] [0, 0, -1]
t=1; [0, 4, -1] [1, 3, -1] [0, 4, -1] [1, 3, -1] [0, 2, -1] [1, 4, -1] [1, 4, -1] [0, 3, -1] [1, 2, -1] [0, 3, -1] [0, 2, -1] [1, 2, -1] [0, 2, -1]
--------------------------------

threshold=19, P=4
#mvseqs=65560
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 5424021
13591 15568919
20566 23654225
22655 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1941354
13591 7494878
20566 12647504
28261 17865289
36945 24142040
46782 30224398
57912 38090731
70470 49318891
84594 59705711
100427 73761790
118121 89136460
137835 106980474
159738 125431249
184009 146489407
210839 169203960
240428 195066989
272990 222107639
308753 250888586
347956 280713560
390855 315150416
437717 355339142
488829 405879973
544492 456493697
605024 508305824
670764 561866412
742065 619044882
819305 688432964
902880 759910399
993208 830639305
1090730 914962991
1195910 999428960
1309240 1082106762
1431233 1184350896
1562434 1284532704
1703414 1395080047
1854773 1519564037
2017143 1650417732
2191190 1777322834
2377612 1928998394
2577140 2093367660
2790547 2265512253
3018641 2444796664
3262270 2630874009
3522324 2838463422
3799738 3041414772
4095490 3268200261
4410608 3482307172
4746166 3738874871
4887273 3834676248
[7, 14]: ncombos=51647440
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 3104966
13591 9367853
20566 13684325
28261 17810915
36945 23171213
46782 29232132
57912 35828302
70470 42862466
84594 49678518
88527 51647440
[8, 12]: ncombos=30705275157
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1912357
13591 5170250
20566 7225947
28261 10671055
36945 13920836
46782 17702050
57912 22259717
70470 27545084
84594 32923969
100427 37493569
118121 44962412
137835 52052458
159738 60713878
184009 69427571
210839 78450098
240428 90711901
272990 105416641
308753 122759128
347956 149210379
390855 176463040
437717 207507680
488829 234382785
544492 262959996
605024 294889554
670764 322803674
742065 356264827
819305 396531897
902880 447443902
993208 496528860
1090730 546042186
1195910 598881447
1309240 652257249
1431233 713383257
1562434 800508138
1703414 889802345
1854773 983398635
2017143 1070792909
2191190 1180782076
2377612 1312266558
2577140 1461365716
2790547 1621512833
3018641 1779084770
3262270 1935576309
3522324 2110451822
3799738 2294714116
4095490 2502033157
4410608 2699003932
4746166 2913274117
5103292 3120795334
5483165 3337783860
5887023 3563116575
6316157 3802569509
6771923 4063340640
7255737 4338409959
7769080 4653828462
8313503 5054462475
8890625 5480151826
9502140 5887074487
10149817 6302641673
10835506 6718543089
11561138 7169784935
12328729 7643289607
13140387 8136066005
13998309 8651179664
14904789 9176189774
15862223 9794520721
16873106 10315828746
17940045 10759407911
19065756 11303363927
20253072 11945179165
21504944 12637723966
22824451 13232821252
24214799 13797095541
25679329 14613481818
27221521 15497874096
28845000 16370921031
30553538 17141237279
32351067 17898582126
34241676 18835012882
36229621 19849629060
38319332 20822958627
40515419 21886249026
42822676 22929179746
45246087 24085828014
47790841 25325447366
50462328 26474145110
53266154 27852903509
56208145 28994296117
59294357 30451562168
59985716 30705275157
[8, 13]: ncombos=3756013599
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 856169
13591 2341330
20566 3613636
28261 4690163
36945 6136822
46782 7629478
57912 9310749
70470 11636631
84594 14862136
100427 21917896
118121 28250172
137835 34419737
159738 39605963
184009 46035723
210839 55476798
240428 64041823
272990 73206345
308753 81447875
347956 95284956
390855 113182072
437717 129584893
488829 151164385
544492 181827394
605024 214304958
670764 245875933
742065 278732732
819305 316183761
902880 354313389
993208 388896646
1090730 422400781
1195910 461832994
1309240 506963662
1431233 553241016
1562434 627421068
1703414 700152268
1854773 770560833
2017143 843528224
2191190 919129211
2377612 1001362130
2577140 1087621447
2790547 1179078074
3018641 1278336452
3262270 1321890632
3522324 1394185083
3799738 1484872504
4095490 1594725425
4410608 1669811318
4746166 1775333651
5103292 1915925097
5483165 2052293672
5887023 2153890077
6316157 2314791345
6771923 2488828572
7255737 2658938769
7769080 2822268513
8313503 3009174064
8890625 3189939235
9502140 3376953470
10149817 3509899095
10835506 3704282558
11063922 3756013599
[8, 14]: ncombos=50587970
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 550865
13591 2746955
20566 5144179
28261 7198491
36945 10708997
46782 14218108
57912 17427278
70470 19182903
84594 21938170
100427 25337678
118121 28959854
137835 34392727
159738 39524401
184009 45039135
210839 49287655
218219 50587970
[9, 11]: ncombos=29360073475
memoizing scramble actions: 0 ms
elapsed ms #combos
5001 2920907
13591 4529497
20566 5883486
28261 7410213
36945 10166316
46782 14052565
57912 17779900
70470 21262466
84594 23684752
100427 28193399
118121 31711406
137836 34910065
159738 39477797
184009 46647958
210839 55542795
240428 66039995
272990 76165898
308753 88163077
347956 102496350
390855 116975087
437717 131360711
488829 140878149
544492 155172494
605024 174621831
670764 185405984
742065 208488571
819305 231094822
902880 260562889
993208 288225296
1090730 312548611
1195910 339915382
1309240 373735776
1431233 415249904
1562434 454536057
1703414 496421810
1854773 557231011
2017143 617588336
2191190 684434520
2377612 760644189
2577140 826415792
2790547 886848038
3018641 959654976
3262272 1040180239
3522324 1110946990
3799738 1205672700
4095490 1305853516
4410608 1421635805
4746166 1537660804
5103292 1645648363
5483165 1765232816
5887023 1896154093
6316157 2032967878
6771923 2198486677
7255737 2392432268
7769080 2577352246
8313503 2765802429
8890625 2969252677
9502140 3222415317
10149817 3489879820
10835506 3754695584
11561138 4015837486
12328729 4288830057
13140387 4586127706
13998309 4870652538
14904789 5188110478
15862223 5497974072
16873106 5800945247
17940045 6128796701
19065756 6457148115
20253072 6839410212
21504944 7100224473
22824451 7448206657
24214799 7820206464
25679329 8274811703
27221521 8860416348
28845000 9403841408
30553538 9961912437
32351067 10557978284
34241676 11133071281
36229621 11668663030
38319332 12203420956
40515419 12850042951
42822675 13646203621
45246087 14389910828
NOT REDUCED:
LK..H
.....
C.AB.
...G.
...FM
t=0; [1, 3, -1] [1, 3, -1] [1, 2, -1] [0, 2, -1] [1, 2, -1] [0, 1, -1] [0, 1, -1] [0, 0, -1] [0, 0, -1]
t=1; [1, 4, -1] [1, 4, -1] [1, 3, 1] [1, 3, 1] [0, 2, 1] [0, 2, 1] [1, 4, -1] [0, 4, -1] [0, 4, -1] [1, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=5
#mvseqs=910744
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 2536153
13591 10320515
20566 17897045
28218 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1779871
13591 6246350
20566 10832328
28261 15801970
36945 20456191
46782 26539946
57912 32985199
70470 43335750
84594 54465175
100427 65827778
118121 80453877
137835 96016900
159738 115502863
184009 134960171
210839 156024893
240428 180760029
272990 206208779
308753 233515312
347956 258527545
390855 285819993
437717 316034466
488829 350666361
544492 398827277
605024 449340377
670764 498920101
742065 555093742
819305 617250872
902880 687253497
993208 755181395
1090730 823411626
1195910 895524089
1309240 965552210
1431233 1012880823
1562434 1070499529
1703414 1177259472
1854773 1282498655
2017143 1393276656
2191190 1521277206
2377612 1649361465
2577140 1772598541
2790547 1893265221
3018641 2036482759
3262270 2197118229
3522324 2372020989
3799738 2547772372
4095490 2743835553
4410608 2942241855
4746166 3156410703
5103292 3366777950
5483165 3577277509
5887023 3799573830
5968126 3834676248
[7, 14]: ncombos=51647440
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1755417
13591 5993345
20566 9887075
28261 13632057
36945 17373775
46782 22033217
57912 27354414
70470 33733338
84594 37715663
100427 43790052
118121 50289402
123168 51647440
[8, 12]: ncombos=30705275157
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1584101
13591 4561573
20567 5307887
28261 6964896
36945 8543052
46782 12153903
57912 14871474
70470 18638570
84594 22806167
100427 26979084
118121 30793145
137835 36410262
159738 42344836
184009 50026156
210839 57884728
240428 65311281
272990 73710886
308753 84604711
347956 97956381
390855 112623861
437717 137260764
488829 163853736
544492 191706336
605024 219018562
670764 244423442
742065 271810919
819305 303819875
902880 329576370
993208 362857779
1090730 405574244
1195910 455322630
1309240 505702769
1431233 555016708
1562434 602360125
1703414 666138892
1854773 724005112
2017143 807691698
2191190 908383924
2377612 1007448803
2577143 1087443340
2790547 1197880638
3018641 1311844370
3262270 1460543377
3522324 1610582483
3799738 1747523767
4095490 1882185674
4410608 2025294296
4746166 2179499745
5103292 2395833456
5483165 2613219349
5887023 2819913165
6316157 3023684616
6771923 3231065584
7255737 3437339280
7769080 3713489714
8313503 3941794496
8890625 4190995195
9502140 4497042295
10149817 4934334702
10835506 5453773238
11561138 5940598962
12328729 6421482798
13140387 6933923431
13998309 7449201636
14904789 8030490077
15862223 8603229512
16873106 9199812670
17940045 9893254033
19065756 10524710077
20253072 11020200453
21504944 11791631726
22824451 12576775003
24214799 13301435320
25679329 13985758890
27221521 14956336742
28845000 15849514049
30553538 16823269568
32351067 17660517901
34241676 18766565148
36229621 19877419619
38319332 21023083723
40515419 22188887243
42822675 23316807041
45246087 24624215705
47790841 25914924101
50462328 27192606501
53266154 28396306830
56208145 29669558371
58592310 30705275157
[8, 13]: ncombos=3756013599
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 858479
13591 2356061
20566 3657816
28261 4711592
36945 6188545
46782 7721711
57912 9400055
70470 11752562
84594 15089747
100427 22268557
118121 28528839
137835 34694736
159738 39656484
184009 46535361
210839 55864191
240428 64459261
272990 73402361
308753 81955867
347956 96549601
390855 114611559
437717 130447042
488829 152873642
544492 184015556
605024 216573815
670764 248181036
742065 280566171
819305 318083046
902880 356060876
993208 390273608
1090730 424934546
1195910 464603093
1309240 508851981
1431233 556266869
1562434 631331355
1703414 704586090
1854773 774293095
2017143 847969887
2191190 923118471
2377612 1004556780
2577140 1090935625
2790547 1183549247
3018641 1279255718
3262270 1324639305
3522324 1397406814
3799738 1489109562
4095490 1597054001
4410608 1672257413
4746166 1782687594
5103292 1920786624
5483165 2058483258
5887023 2160684829
6316157 2321956001
6771923 2496656961
7255737 2668047567
7769080 2830766795
8313503 3016786031
8890625 3195806266
9502140 3383503015
10149817 3514420781
10835506 3714160936
11030022 3756013599
[8, 14]: ncombos=50587970
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 734851
13591 3063805
20566 5429276
28261 7556994
36945 11085850
46782 14555703
57912 17474012
70470 19303249
84594 22043513
100427 25385229
118121 28989568
137835 34430797
159738 38989974
184009 44648845
210839 48916189
220530 50587970
[9, 11]: ncombos=29360073475
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 2945360
13591 4715499
20566 5949282
28261 7615602
36945 10372929
46782 14303702
57912 17887755
70470 21456219
84594 23819789
100427 28716541
118121 32003190
137835 35454920
159738 40166438
184009 46893834
210839 56860964
240428 66627342
272990 77084894
308753 89521748
347956 103282639
390855 117958824
437717 131530252
488831 141070865
544492 155649220
605024 175046846
670764 186453604
742065 209324366
819305 232080569
902880 261484429
993208 289284140
1090730 313423527
1195910 340854110
1309240 375051883
1431233 416740858
1562434 455654845
1703414 498090509
1854773 560056286
2017143 620757472
2191190 688131140
2377612 762330650
2577140 828435239
2790547 890018716
3018641 961571005
3262270 1041008084
3522324 1113509877
3799738 1207595245
4095490 1307376947
4410608 1423497483
4746166 1540504869
5103293 1649481251
5483165 1768112897
5887023 1898938486
6316157 2040238575
6771923 2208330742
7255737 2399521066
7769080 2593382494
8313503 2781308037
8890625 2997031570
9502140 3270362557
10149817 3575752703
10835506 3845881204
11561138 4149412895
12328729 4467645297
13140387 4795705814
13998309 5134514691
14904789 5472053623
15862223 5805494631
16873106 6146305057
17940045 6520880708
19065756 6885890594
20253072 7280255167
21504944 7664873108
22824451 8127139915
24214799 8730599957
25679329 9321158278
27221521 9884576035
28845000 10474523649
30553538 11109402115
32351067 11730161739
34241676 12281459187
36229621 12969384036
38319332 13743697213
40515419 14417834401
42822675 14995922507
45246087 15778023751
47790841 16610218001
50462328 17439264253
53266154 18188614136
56208145 19056399493
59294357 20066111557
62531083 21068273590
65924860 21943001401
69482480 23082988776
73210999 24187281258
77117743 25308119156
81210321 26409923899
85496631 27442860647
89984875 28419561072
94683564 29335163333
94811270 29360073475
[9, 12]: ncombos=12682746525
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1401828
13591 2356078
20566 2837656
28261 4100464
36945 5892547
46782 7668978
57912 9048688
70470 10166493
84594 12295942
100427 13732435
118121 14835679
137835 16612715
159738 20153840
184009 25306741
210839 29473030
240428 33670285
272990 39433633
308753 45339771
347956 53574855
390855 59553389
437717 64358362
488829 72540542
544492 77512410
605024 86230863
670764 96386431
742065 109597747
819305 122422846
902880 133815175
993208 147156643
1090730 162811396
1195910 182366636
1309240 198677537
1431233 222095061
1562434 258099620
1703414 292970404
1854773 330860334
2017143 360808583
2191190 392151227
2377612 429166134
2577140 457454844
2790548 494814497
3018641 541675289
3262270 592735996
3522324 649656089
3799738 695473667
4095490 752801952
4410608 807422513
4746166 868988173
5103292 944750175
5483165 1046144557
5887023 1146995280
6316157 1228101853
6771923 1354447080
7255737 1515887010
7769080 1659329490
8313503 1816496082
8890625 1985035112
9502140 2147314223
10149817 2324908194
10835506 2477474966
11561138 2640560677
12328729 2806263449
13140387 2984422619
13998309 3164744446
14904789 3358782177
15862223 3603356898
16873106 3914305381
17940045 4193346962
19065756 4468927903
20253072 4781356764
21504944 5077453573
22824451 5329708075
24214799 5664918826
25679329 6037288165
27221521 6276367404
28845000 6470694163
30553538 6768312376
32351067 7104091039
34241676 7460832056
36229621 7781954593
38319332 8060697671
40515419 8543737976
42822675 8978997959
45246087 9337733876
47790841 9861592151
50462328 10388096099
53266154 10900878268
56208145 11380017578
59294357 11840774986
62531083 12248420901
65924860 12632490349
66400801 12682746525
[9, 13]: ncombos=1551413175
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 431361
13591 1186889
20566 1653608
28261 1857155
36945 2471100
46782 3512350
57912 4259103
70470 5404146
84594 7033505
100427 8034191
118121 9358762
137835 10825411
159738 12916861
184009 15442106
210839 17596496
240428 20617698
272990 23855368
308753 27624955
347956 35256896
390855 42088472
437717 47005395
488829 53546372
544492 57127025
605024 64977390
670764 74166226
742065 82868263
819305 91885034
902880 100536148
993208 109891247
1090730 128809896
1195910 145639939
1309240 162254538
1431233 193964117
1562434 219571313
1703414 249509667
1854773 280311276
2017143 306985104
2191190 331955516
2377612 363529318
2577140 393977468
2790547 428704594
3018641 480235421
3262270 526546033
3522324 578287805
3799738 626389417
4095490 673359498
4410608 731734458
4746166 765197644
5103292 788483928
5483165 826768222
5887023 876015831
6316157 922383988
6771923 963620509
7255737 1023083698
7769080 1085754441
8313503 1141653180
8890625 1229185673
9502140 1308988717
10149817 1374184733
10835506 1448870713
11561138 1506975394
12136485 1551413175
[9, 14]: ncombos=20895250
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 270013
13592 1015286
20566 1620902
28261 2705457
36945 4114273
46782 5343057
57912 7131231
70470 8970658
84594 10367124
100427 11313158
118121 12765552
137835 14351260
159738 16558362
184009 18878900
210839 20599475
215086 20895250
[10, 10]: ncombos=2653783968
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1056944
13591 2098636
20566 3255404
28261 4324420
36945 5617827
46782 7324338
57912 8524570
70470 10833600
84594 12897232
100427 14847050
118121 18597966
137835 21408708
159738 24605483
184009 27733765
210839 31620173
240428 38527514
272990 43279062
308753 47949331
347956 52699460
390855 57592882
437717 64345371
488829 72208634
544492 81212579
605024 90531493
670764 100218657
742065 110609211
819305 120789647
902880 135646235
993208 148629821
1090730 163086818
1195910 177692667
1309240 196058417
1431233 215280570
1562434 237728824
1703414 265898341
1854773 286693724
2017143 308901675
2191190 333159967
2377612 358935154
2577140 389322076
2790547 421797005
3018641 454158735
3262270 492579841
3522324 523825688
3799738 568953844
4095490 613536877
4410608 665251232
4746166 717887777
5103292 775493134
5483165 840425390
5887023 906446299
6316157 979768138
6771923 1051523735
7255737 1127011389
7769080 1200182041
8313503 1275428354
8890625 1357153329
9502140 1443156266
10149817 1545252797
10835506 1649998365
11561138 1756381327
12328729 1862493217
13140387 1969982489
13998309 2088497473
14904789 2202749142
15862223 2335965117
16873106 2469232066
17940045 2604642383
18539769 2653783968
[10, 11]: ncombos=2674987544
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 675660
13591 1619497
20566 2066296
28261 2847916
36945 3754540
46782 4415248
57912 5513132
70470 6449457
84594 7785559
100427 9080244
118121 10814282
137835  12531558
159738 14081217
184009 16555234
210839 19908113
240428 22627666
272990 25761314
308753 28618093
347956 32658638
390855 39489315
437717 44096562
488829 48372614
544492 52635036
605024 56769374
670764 62241845
742065 69625775
819305 77493307
902880 86047448
993208 93863987
1090730 103308179
1195910 112780375
1309240 122888133
1431233 136812116
1562434 149535046
1703414 163476522
1854773 177020754
2017143 195095780
2191190 213241705
2377612 234998586
2577140 262056261
2790547 283771754
3018641 301602075
3262270 326029651
3522324 348844854
3799738 372993428
4095490 402606117
4410608 435976700
4746166 468032591
5103292 503097978
5483165 534032121
5887023 575614544
6316157 617836204
6771923 664942826
7255737 718220111
7769080 770384539
8313503 834444243
8890625 900143526
9502140 976619849
10149817 1049112328
10835506 1127344081
11561138 1199934229
12328729 1269223858
13140387 1355025779
13998309 1439114375
14904789 1530579343
15862223 1636585024
16873106 1740933541
17940045 1846796642
19065756 1954882214
20253072 2063105164
21504944 2161110189
22824451 2273336632
24214799 2387654905
25679329 2507909812
27221521 2633172501
28018655 2674987544
[10, 12]: ncombos=1155521256
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 417551
13591 939942
20566 1537512
28261 1890752
36945 2424081
46782 2841675
57912 3429822
70470 4113723
84594 4969143
100427 5658538
118121 6676275
137835 8278475
159738 9585278
184014 11402424
210839 13228222
240428 15693619
272990 18602273
308753 21146538
347956 23168646
390855 25861207
437717 28571202
488829 31906615
544492 35963957
605024 39951151
670764 44337965
742065 49093828
819305 54509515
902880 60993977
993208 67814409
1090730 73826966
1195910 82087832
1309240 90801050
1431233 101550045
1562434 115003567
1703414 123876428
1854773 132575125
2017143 143249059
2191190 154004147
2377612 165684287
2577140 180217388
2790547 196727746
3018641 213501821
3262270 229001574
3522324 248265665
3799738 267379019
4095490 288198320
4410608 313720053
4746166 340048164
5103292 373498594
5483165 407608598
5887023 443171340
6316157 482534491
6771923 518583955
7255737 552295833
7769080 596137608
8313503 635339125
8890625 686081176
9502140 735484541
10149817 785973670
10835506 839153689
11561138 890164312
12328729 929674162
13140387 975417213
13998309 1024885188
14904789 1077370659
15862223 1134112786
16383311 1155521256
[10, 13]: ncombos=141348792
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 273812
13591 554546
20566 820349
28261 1220869
36945 1682118
46782 2346190
57912 2880365
70470 3406741
84594 4208329
100427 4991746
118121 5937505
137835 7019966
159738 8332206
184009 9519612
210839 11389317
240428 13745797
272990 15318491
308753 17043628
347956 18816178
390855 20737945
437717 23718698
488829 26859146
544492 29849136
605024 33008596
670764 37002096
742065 41235078
819305 46970800
902880 53387341
993208 60652617
1090730 66101472
1195910 73942941
1309240 81236247
1431233 89347910
1562434 98527617
1703414 107927677
1854773 113411153
2017143 120154597
2191190 128095784
2377612 135837655
2504993 141348792
[10, 14]: ncombos=1903760
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 230880
13591 662337
20566 1103491
28261 1504401
36945 1813342
39358 1903760
[11, 9]: ncombos=398056
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 148995
13591 372757
14587 398056
[11, 10]: ncombos=738804
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 114523
13591 300441
20566 433481
28261 575015
36945 734803
37126 738804
[11, 11]: ncombos=744707
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 94144
13591 265856
20566 380764
28261 509165
36945 661988
41897 744707
[11, 12]: ncombos=321693
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 92657
13591 246396
17798 321693
[11, 13]: ncombos=39351
memoizing scramble actions: 0 ms
elapsed ms #combos
1999 39351
[11, 14]: ncombos=530
memoizing scramble actions: 0 ms
elapsed ms #combos
20 530
time=438839540

Process finished with exit code 0


----------



## xyzzy (Jul 6, 2021)

(No new result in this post; just some observations regarding the asymptotic bounds.)

In post #13 I calculated a lower bound for the uniform-distance swaps method, which _must_ have worst case at least \( \Omega(N\log N) \) moves. This is because:
- there are \( \exp(\Theta(N)) \) possible u-d involutions on an \( N \)-element set
- thus counting argument forces the worst case number of u-d involutions needed in a decomposition to be \( \Omega(\log N) \)
- we have a method to do u-d involutions in worst-case \( \Theta(N) \) moves
- therefore this approach must have worst-case at least \( \Theta(N)\Omega(\log N)\equiv\Omega(N\log N) \) moves

The current proven upper bound using the u-d involution approach is only \( O(N\log^2N) \), so it's a priori plausible that we could continue using the same approach and reduce it further to \( O(N\log N) \). Two years of thinking about this problem on and off has not yielded any new result.

Uniform-distance swaps are very restrictive, which is the feature that allows us to do a lot of "long-distance" swaps in only \( O(N) \) moves, but it also makes using them very difficult. Probabilistic constructions of sorting algorithms (see e.g. AKS sorting network) basically repeatedly throw in random comparators/swaps until there's a nonzero chance that a correct sorting algorithm is produced (we don't know _which_ collection of random choices leads to a correct algorithm, just that some collection exists), and the algorithms thus produced have no guaranteed clean structure, the exact opposite of uniform-distance swaps.

---

What other types of permutations can we provably do in \( O(N) \) moves? Consider the following class of permutations on the set \( \{0,\cdots,N-1\} \):
\( 
\begin{aligned}
S:=\{&(a_0,b_0)(a_1,b_1)\cdots(a_{m-1},b_{m-1}):m\text{ is even and}\\
&0\le a_0<b_0<\cdots<a_{m-1}<b_{m-1}\le N-1\}\\
\end{aligned}
\)
Then by pairing these up in order, we have that all of these swaps can be done in \( O(\sum_{k=0}^{m-1}(b_k-a_k)+\sum_{k=1}^{m-1}(a_k-b_{k-1}))=O(N) \) moves. (See Lemma 8 in post #4.) The size of \( S \) is \( |S|=2^{N-2}+O(2^{N/2}) \). (See OEIS A038503. Exercise for the reader: prove this using a discrete-time Fourier transform.) Thus, as with the u-d involutions, the same idea shows that it's plausible that we can prove an \( O(N\log N) \) upper bound.

Unfortunately, this just doesn't work. Each of the permutations in \( S \) can change the number of inversions by at most \( 2N \), and since there exist permutations with \( \Theta(N^2) \) inversions, it follows that there are \( S \)-decompositions of length at least \( \Omega(N) \).

More generally, any approach that uses only 3-cycles or (2,2)-cycles _without any inter-alg cancellation or shared setup moves_ must take \( \Omega(N\cdot\max(R,C)) \) moves in the worst case. This is because a 3-cycle or (2,2)-cycle alg that uses \( n \) moves can move three or four pieces by at most \( n \) spaces each, thereby reducing the summed distance by at most \( 3n \) or \( 4n \) respectively, but the maximum possible summed distance is \( \Theta(N\cdot\max(R,C)) \). (The u-d involutions method gets a better bound despite also being built on (2,2)-cycles because the setup moves are shared across many (2,2)-cycles.)

---

We can apply arbitrary even permutations to a 2×n region of the board in \( O(n\log n) \) moves. (See post #12.) Using this as a building block, we can sort the rows and the columns in at most \( O(N\log R+N\log C)\equiv O(N\log N) \) moves, up to parity (as in, at most two of the pieces may be out of order). From here… I'm not sure if there's any reasonable progress to be made. If \( R-C=O(1) \) (i.e. the board is square or almost square), then this row-sorting and column-sorting process cuts down the state space by a square root (from \( N!/2 \) to \( N!^{1/2+o(1)} \)), which isn't a lot.

(See also: (standard) Young tableaux.)


----------



## coolcomputery (Jul 13, 2021)

5x5 GN is at most 46.
I reduced the GN of 5x5: 0x0 --> 3x3 to 18, using several new techniques:
First, I split this solving stage into the phases null --> AC KM --> 3x3 (ABC FGH KLM) instead of null --> AB FG --> 3x3, which decreases the scrambles I would have to process from ~233e9 to ~188e9.
Second, in addition to applying prefix move sequences to each scramble I test, I also try solving it with different block-building phases; for example, I try solving a given scramble of the pieces ABC FGH KLM by first solving AB FG and then the rest, or first solving GH LM and then the rest. (A similar technique was used by xyzzy to solve 5x5: 3x3 --> 5x5). On each of these alternative block-building phases, I also apply prefix move sequences if necessary.
A total of 188,592,895,657 scrambles was processed in 100368.865 seconds (about 27.8 hours). At most 3 moves were needed for a prefix move sequence. *18+28=46*.
*UPDATE (2021-07-18): *So far, trying to reduce 5x5: 0x0 --> 3x3 to 17 moves has resulted in a java.OutOfMemoryError. Improving the second phase (3x3->entire board) also seems to require processing hundreds of billions of scrambles.
*UPDATE (2021-08-01): 5x5 GN is at most 45.*
I finally reduced 5x5: 0x0 --> 3x3 to 17 moves. The process was split into two parts. The first part was slightly faster but hit a java.OutOfMemoryError partway through. The second part consumed less memory but ran much more slowly. The combined computation time was about 11-12 days. At most 6 prefix moves were needed. Code and stdout is at https://gist.github.com/coolcomputery/c4af0f79f7a2d8a9c774395845058c04.


----------



## coolcomputery (Jul 24, 2021)

*Disclaimer: No new results.*
Slightly tighter counting of 5x5 move sequences at fixed depths, continuing from xyzzy's post #6 (https://www.speedsolving.com/threads/loopover-gods-number-upper-bounds-4×4-asymptotics-etc.75180/#post-1333877).

On a 5x5, the move sequences R1 C0 R0 C0' and C0 R0 C0' R1 yield the same scramble.
To prevent counting both of these syllable sequences, consider syllables A, B of opposite type (i.e. one is horizontal and another is vertical). Define \( S(A,B)=\{r | (>>r)A^{-1}BA == A^{-1}BA(>>r)\} \), where (>>r) is the action that shifts row r right one unit, or \( \{(,,c)A^{-1}BA == A^{-1}BA(,,c)\} \), where (,,c) is the action that shifts column c down one unit, according to the types of A, B. Also, define \( M(A)=\{r|A[r]==0\} \), where A[r] is the amount that syllable a shifts row/column r one unit in the right/down direction.
Then we can restrict our counting of syllable sequences to the following: for any set of 4 consecutive syllables in the sequence that are of the form \( \dots A^{-1} B A C \dots\), we must have \( S(A,B) \cap M(C) = \emptyset \). We can call such syllable sequences "good".
We can count the number of "good" syllable sequences at each depth using DP (source code). Define \( dp_a(k,t,d)_{A,B}= \) # "good" syllable sequences with \( d \) total moves, \( k \) total syllables, and last syllable being of type \( t \) that end as \( \dots C A B \) for any \( C\neq B^{-1} \). Define \( dp_b(k,t,d)_{A,B}= \) same thing but require syllable sequences to end as \( \dots B^{-1} A B \). Then we have the following:

\[ dp_a(k,t,d)_{A,B}=\sum_{C\neq B^{-1}} dp_a(k-1,1-t,d-|B|)_{C,A} + \sum_{C\neq B^{-1}\wedge S(A,C)\cap M(B)=\emptyset} dp_b(k-1,1-t,d-|B|)_{C,A} \]

\[ dp_b(k,t,d)_{A,B}=dp_a(k-1,1-t,d-|B|)_{B^{-1},A} + (S(A,C)\cap M(B)=\emptyset) dp_b(k-1,1-t,d-|B|)_{B^{-1},A} \]

Here, \( |A|= \) total # of moves needed to execute syllable \( A \).

The base cases occur when \( k=3 \). The cases \( k<3 \) can be dealt with separately.

Computing these DP states naively would take about \( O((N^N)^3) \) time for each triplet \( (k,t,d) \), which is too slow, so we add some helper variables:

\[ h_a(k,t,d)_A=\sum_C dp_a(k-1,1-t,d)_{C,A} \]

\[ h_b(k,t,d)_{A,M}=\sum_{M' | M'\cap M=\emptyset} h_c(k,t,d)_{A,M'} \]

\[ h_c(k,t,d)_{A,M}=\sum_{C | S(A,C)=M} dp_b(k-1,1-t,d)_{C,A} \]

Then we can evaluate \( dp_a(k,t,d)_{A,B} \) as \( h_a(k,t,d-|B|)+h_b(k,t,d-|B|,M(B))-dp_b(k,t,d)_{A,B} \). To reduce memory usage, we avoid directly storing any values in \( dp_a(k,t,d) \). Also, we split the DP dependence into two chains based on tuples (k,t): (3,0)<--(4,1)<--(5,0)<--... and (3,1)<--(4,0)<--(5,1)<--... and evaluate each chain separately. In each chain, after computing all \( h_a(k,t,d)_A, h_b(k,t,d)_{A,M}, dp_b(k,t,d)_{A,B} \), we delete \( h_a(k-1,1-t,...), h_b(k-1,1-t,...), dp_b(k-1,1-t,...) \). Additionally, for each fixed (k,t), after computing all \( h_a(k,t,d)_A, h_b(k,t,d)_{A,M} \), we first fix a value \( d_n \), then evaluate \( dp_b(k,t,d)_{A,B} \) only for \( B \) such that \( |B|=d-d_n \), then delete \( dp_b(k-1,1-t,d_n) \). Before deletion, though, we store several totals, \( T(k,t,d)=\sum_{A,B} dp_a(k,t,d)_{A,B}+dp_b(k,t,d)_{A,B} \). We use these in the end to count how many good syllable sequences there are with total move count at or below a certain threshold, \( d_{max} \).

Unfortunately, the 5x5 GN lower bound of 22 is not improved. Here are the cumulative total number of good syllable sequences at or below 0, 1, 2, ... 22 moves, versus the cumulative totals for normal syllable sequences:



Spoiler: good vs. normal syllable sequence counts



good syllables
0:1
1:21
2:321
3:4641
4:65561
5:923145
6:12994265
7:182929945
8:2575201225
9:36251812425
10:510322952217
11:7183898083097
12:101128894777897
13:1423607949716137
14:20040360519744777
15:282111408726963753
16:3971328093414571593
17:55905030207130704553
18:786984184955193366713
19:11078504118051284217113
20:155953900775003742325737
21:2195388376234705442432377
22:30904838535964351025431817

normal syllables:
0:1
1:21
2:321
3:4641
4:66761
5:960345
6:13814665
7:198724745
8:2858665225
9:41122041225
10:591542609417
11:8509369868297
12:122407708919817
13:1760840982947337
14:25329785146646537
15:364370219564769289
16:5241483736914045449
17:75399004334521259529
18:1084618428671161162249
19:15602290059346154478089
20:224439718762861186359817
21:3228576520930493071364617
22:46443233884627791532876297



*Note: *It is possible to further tighten syllable sequence counts by requiring that in all syllable sequences, for every set of 4 consecutive syllables \( \dots A B C D \dots \), we have \( S(A,B,C) \cap M(D)=\emptyset \), where\( S(A,B,C) \) is an extension of \( S(A,B) \) for the syllable composition \( ABC \) instead of \( A^{-1}BA \). However, the only DP I know to count such syllable sequences requires far too much memory (on the order of \( O((N^N)^3) \) states for each fixed triple \( (k,t,d) \) instead of \( O((N^N)^2) \) states) to calculate in a reasonable amount of time.


----------



## rokicki (Jul 24, 2021)

coolcomputery said:


> On a 5x5, the move sequences R1 C0 R0 C0' and C0 R0 C0' R1 yield the same scramble.


I've pursued this up to length-12 identities (length-6 identical subsequences) and you're right, it doesn't tighten the bound. (This functionality is built into twsearch; use -C in conjunction with --newcanon # where # goes as high as you can until you run out of memory or patience.)

For comparison, if you want, here are the first several values I get for --newcanon 4:



Spoiler





```
D 0 this 1 total 1
D 1 this 20 total 21 br 20
D 2 this 300 total 321 br 15
D 3 this 4320 total 4641 br 14.4
D 4 this 60920 total 65561 br 14.10185185185185
D 5 this 845184 total 910745 br 13.8736703873933
D 6 this 11720315 total 12631060 br 13.86717566825685
D 7 this 162618240 total 175249300 br 13.87490353288286
D 8 this 2255712285 total 2430961585 br 13.87121324766521
D 9 this 31289289688 total 33720251273 br 13.87113502731134
D 10 this 434046099165 total 467766350438 br 13.87203428051818
D 11 this 6021036796248 total 6488803146686 br 13.87188321201601
D 12 this 83522805650006 total 90011608796692 br 13.87183112749836
D 13 this 1158617782388288 total 1248629391184980 br 13.87187335688124
```


----------



## GodCubing (Jul 24, 2021)

What is God's Number for 2x2 and how is it optimally solved? Is it like 2 phase or is there another way


----------



## coolcomputery (Jul 24, 2021)

GodCubing said:


> What is God's Number for 2x2 and how is it optimally solved? Is it like 2 phase or is there another way


For 2x2 Loopover, God's number is 4. There are only 24 possible scrambles so it is possible to brute-force the entire configuration space. A 4-move scramble is:


```
DC
BA
```


----------



## GodCubing (Jul 24, 2021)

coolcomputery said:


> For 2x2 Loopover, God's number is 4.


I meant upper bound, and what's loopover


----------



## xyzzy (Jul 24, 2021)

GodCubing said:


> what's loopover







__





Loopover


Loopover is a single-player sliding tile puzzle game.




loopover.xyz




A simple puzzle game that has been reinvented many times over, as a 2D Rubik's Cube-like puzzle.

If you're asking about the 2×2×2 cube, maybe you should repost the question in the puzzle theory OAQT thread.


----------



## coolcomputery (Aug 15, 2021)

*6x6 GN is at most 96.*
I reduced the GN for solving the 1,2,3,7,8,9,13,14,15 block (i.e. the top-left-most 3x3 block).
First, I split it into solving 1,3,13,15 and then solving the rest of the pieces.
Then, I applied a symmetry reduction to avoid testing as many possible scrambles for the first phase as I would have to (this reduced the total # of scrambles by about 8 times).
Finally, on top of the prefix move trick and the alternate block-building trick as described in post #24, I added "transformed solving", where given a scramble, I test if solving a "transformed" version of that scramble leads to a shorter solution. If it does, then applying the inverse transformation to that solution yields a solution for the original scramble. A total of 34,961,702,384 scrambles was processed in about 20-21 hours. *24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=96.

(2021-08-21) *Using this same symmetry reduction technique, *5x5 GN is at most 44. *I reduced the two phases 3x3->4x4->5x5 to at most 27 moves. A total of 274,724,883,578 scrambles was processed in about 7 days (the program was split into two sessions after the first session was accidentally stopped partway through). *17 (0x0->ACKM-->3x3) + 27 (3x3->4x4->5x5)=44.

(2021-08-23) 6x6 GN is at most 95. *The two phases 4x4->4x5->5x5 take at most 26 moves to solve. 7,747,057,906 scrambles were processed in 28625.784 seconds (about 8 hours).

*Rigorous explanation of symmetry reduction and scramble transformation:*
We represent all scrambles, permutations, and transformations as lists of numbers.
For two lists of numbers \( A, B \), define the product \( AB=[ \dots A[B[ i ]] \dots ]_i \). If, for any i, \( B \) is out of index range of \( A \), then \( AB \) is undefined. Note that for three lists \( A, B, C \), if \( ABC \) is defined, then we have \( (AB)C=A(BC) \), i.e. the product of lists is associative.
We represent a permutation (aka a "scramble action") on the board as \( A \), where location i on the board is moved to location \( A \) for each i. All elements must be distinct and in the set \( \{0\dots len(A)-1 \} \). (Technically any indexing of the cells of the Loopover board will work, although I use row-major indexing).
Denote \( \mathcal{M} \) the set of permutations that are individual moves of the RxC Loopover Board.
We represent a space transformation, i.e. a transformation of the entire board, as a permutation \( S \), where location i on the board is moved to location \( S \) for each i. Then a permutation \( A \) that is transformed under \( S \) is defined as the permutation \( SAS^{-1} \).
All space transformations \( S \) that we consider must be "rigid", meaning that for all permutations \( M \in \mathcal{M} \) we have \( SMS^{-1} \in \mathcal{M} \). Consequently, if \( A \) can be represented as the product of \( k \) individual moves \( \prod_{i=0}^{k-1} M_i \), then \( SAS^{-1} \) can be also represented as the product of \( k \) moves \( \prod_{i=0}^{k-1} SM_iS^{-1} \). This is a very important property.

Now suppose we have a scramble \( P \) of only a subset of pieces on the Loopover board, ex. of the pieces ABEF on the 4x4 board. We want to transform \( P \) into a target \( T \). In our example, \( T=[0,1,4,5] \). Let's have \( P=[6,15,2,13] \). The board will look like this:

```
..E.
..A.
....
.F.B
```
Suppose some permutation \( A \) over the entire board solves \( AP=T \). Now, what could the scramble \( SAS^{-1} \) solve, for a carefully chosen S? Suppose S rotates the board clockwise around the 2x2 square occupied by AB EF in the solved board:

```
ABCD     EAIM
EFGH --> FBJN
IJKL     GCKO
MNOP     HDLP
S=[1,5,9,13,0,4,8,12,3,7,11,15,2,6,10,14]
```
If we transform the locations of pieces described by \( P \) under \( S \), we get \( SP \). Applying \( SAS^{-1} \) yields \( SAS^{-1}SP=SAP=ST \), which is not necessarily equal to \( T \). However, for our specific \( S \), the 2x2 region that \( T \) occupies is preserved, i.e. the locations that AB EF are supposed to occupy only get permuted among each other, and not to any other locations outside of \( T \). This means there exists a permutation \( Q \) s.t. \( STQ=T \). Consequently, \( SAS^{-1} \) solves the scramble \( SPQ \).

To generalize, define the function \( \mathcal{Q}_T(S)=Q \texttt{ s.t. } STQ=T \texttt{ if such Q exists else } \emptyset \) and the set \( \mathcal{T}(T)=\{S \texttt{ s.t. } \mathcal{Q}_T(S)\ne\emptyset\} \). (Note that if \( \mathcal{Q}_T(S)\ne\emptyset \), then \(\mathcal{Q}_T(S) \) must have a unique value.)
Then we have \( \forall S\in \mathcal{T}(T), SAS^{-1} \texttt{ solves } SP\mathcal{Q}_T(S) \). This is the essence of the "transformed solving" trick: instead of solving a given scramble \( P \) directly, we first see if there is a space transformation \( S\in \mathcal{T}(T) \) and a sufficiently short solution \( B \) that solves \( SP\mathcal{Q}_T(S) \); if so, then we have a solution \( A=S^{-1}BS \) to the original scramble \( P \). The crucial thing is that the number of individual moves required to obtain \( B \) is the same as the number of individual moves required to obtain \( S^{-1}BS \), which is why it is correct to use this trick in the first place.

*Phase 0 symmetry reduction:*
For a specific target list \( T \) (and a restriction on which individual moves are allowed on the Loopover board), a BFS tree \( tree_T \) for \( T \) maps every possible scramble \( P \) to an arbitrarily chosen scramble action \( A=tree_T(P) \) over the entire board, such that \( AP=T \) and that the number of individual moves required to obtain \( A \) is minimized.
Now suppose our two phases are described by the targets \( T_0,T_1 \). The overall target of these two phases combined is \( T=[T_0|T_1] \), where | is list concatenation. Let a pair of phase scrambles \( P_0, P_1 \) represent the composite scramble \( f(P_0, P_1):=[P_0|A^{-1}P_1] \), where \( A=tree_{T_0}(P_0), B=tree_{T_1}(P_1) \), and we require that \( BT_0=T_0 \), i.e. that phase 1 does not disrupt any pieces that are solved at the end of phase 0. Thus, \( BAf(P_0,P_1)=T \).
Traditional two-phase optimization involves finding alternative solutions to all scrambles \( \in\cup_{\texttt{all necessary P_0}} \mathcal{S}_{P_0} \), where \( \mathcal{S}_{P_0}:=\{ f(P_0,P_1) \ \forall P_1 \} \). However, we can use the above idea of transformed solving, although we must be more restrictive on \( S \) than we were previously: if we let \( E \) be the set of pieces that are unsolved before either phase 0 or phase 1 start (ex. for the phases 3x3->4x4->5x5 on 5x5 Loopover. \( E=[3, 4, 8, 9, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24] \)), then we require that \( S\in\mathcal{T}(T_0)\cap\mathcal{T}(T_1)\cap\mathcal{T}(E) \).
Using this idea of transformed solving, if there exists a solution \( C \) s.t. \( C[P_0|A^{-1}P_1]=T \), then \( (SCS^{-1})[SP_0\mathcal{Q}_{T_0}(S)|SA^{-1}P_1\mathcal{Q}_{T_1}(S)]=T \). Therefore, if we obtain a solution to \( [P_0|A^{-1}P_1] \) requiring \( \leq t \) moves for some threshold \( t \), we immediately know that \( [SP_0\mathcal{Q}_{T_0}(S)|SA^{-1}P_1\mathcal{Q}_{T_1}(S)]=T \) is also solvable in \( \leq t \) moves. Thus, if we prove that all scrambles \( \in\mathcal{S}_{P_0} \) are solvable in \( \leq t \) moves for a fixed \( P_0 \), then we know that all scrambles \( \in\mathcal{S}_{SP_0\mathcal{Q}_{T_0}(S)} \) are also solvable in \( \leq t \) moves, for all valid \( S \). Therefore, we can partition the set of all \( P_0 \) into equivalence classes, where for two phase-0 scrambles \( X,Y \), we define equivalence \( X\equiv Y \) as \( \exists S\in \mathcal{T}(T_0)\cap\mathcal{T}(T_1)\cap\mathcal{T}(E) \texttt{ s.t. } X=SY\mathcal{Q}_{T_0}(S) \). Then, during two-phase optimization, we only iterate over one \( P_0 \) in each equivalence class.

(Update 2021-08-20: fixed a minor technical error in phase 0 symmetry reduction by adding the list E)


----------



## coolcomputery (Nov 7, 2021)

*6x6 GN is at most 94.*

The two phases 4x4->4x5->5x5 take at most 25 moves to solve.
*24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 25 (4x4->4x5->5x5) + 24 (5x5->6x6)=94.*
Code (specifically the BFS.java and BFS2improve files): https://github.com/coolcomputery/Lo...tree/3aaf37d8e94059b41622e17c2d2cd4779ccac4e3
Stdout: https://gist.github.com/coolcomputery/f1c46f1c24e8a341afa7bc7cda7a4bfe
Total running time was 129523.756 seconds (about 36 hours), although I estimate that about 27000 seconds were of my laptop sleeping (I was traveling and didn't have access to laptop charging for a few hours, and my laptop was almost dead, so I had to pause the program during then by making my laptop sleep; the actual running time was about 28 hours).

I completely rewrote my BFS and BFS-pair-optimization programs to use a much more generalized and powerful method of improving 2-phase God's numbers. In summary, for every scramble that by default would take too many moves, I now iteratively DFS over every possible phase 0 solution move sequence, in increasing order of move count, to find a sufficiently short alternative solution to the scramble.

*Rigorous explanation* (using the same notation as in my previous forum post):

A scramble of \( R\times C \) Loopover is defined as an permutation array \( S \), where the cell at location index \( i \) goes to location index \( S_i \); the \( (r,c) \) location in the Loopover board is given the index \( rC+c \). Applying a scramble \( B \) on top of a scramble \( A \) forms the "product scramble" \( BA \), where \( (BA)_i=B_{A_i} \). Solving a scramble \( S \) across the entire board consists of finding a list of single-cost moves \( M_0,\dots,M_{m-1} \) such that \( (\prod_{i=m-1}^{i=0} M_i)S=I=[0,1,\dots RC-1] \), i.e. such that we transform \( S \) to the identity permutation \( I \). If we want to only solve a list of location indices \( T \) within a scramble \( S \), then we transform \( S \) to some permutation \( S' \) such that \( S'T_0=T_0 \).

Let our solving blocks be \( T_0 \) and \( T_1 \) and our "pre-block" be \( T_p \). By building our two BFS trees, for every scramble \( S \) such that the region \( T_p \) is already solved, we have a default phase 0 solution \( \mathcal{A}(S)=A=\prod_{i=m-1}^{i=0} M_i \), for some single-cost moves \( M_i \) s.t. \( M_iT_p=T_p \), such that \( AST_0=T_0 \), and a default phase 1 solution \( \mathcal{B}(AS)=B=\prod_{i=n-1}^{i=0} N_i \), for some single-cost moves \( N_i \) s.t. \( N_iT_0=T_0 \), such that \( BAST_1=T_1 \) (note that in the product expressions for \( A, B \) the index \( i \) is in the opposite order it usually is). This way, we never disturb block \( T_p \) during phase 0 or block \( T_0 \) during phase 1. Since \( BAST_1=T_1 \), we say that \( A \) and \( B \) together solve \( S \) "up to \( T_1 \)".
The 4x4->4x5->5x5 phases for 6x6 Loopover would correspond to the blocks \[ T_p=[0,1,2,3,\ 6,7,8,9,\ 12,13,14,15,\ 18,19,20,21],\]\[T_0=[0,1,2,3,4,\ 6,7,8,9,10,\ 12,13,14,15,16,\ 18,19,20,21,22],\]\[T_1=[0,1,2,3,4, 6,7,8,9,10,\ 12,13,14,15,16,\ 18,19,20,21,22,\ 24,25,26,27,28,29].\]

In BFS-pair-optimization, for every scramble \( S \) such that the default phase solutions together take \( >t \) moves, we find an alternative solution for \( S \). In the past, I would first apply an arbitrary product of a sequence of moves \( P \) on scramble \( S \), then check if the default solutions \( A=\mathcal{A}(PS) \) and \( B=\mathcal{B}(APS) \) together take \( \le t \) moves, then repeat with some other \( P \) if needed, with \( P \) increasing in number of moves until a short enough solution for solving \( S \) up to \( T_1 \) was found. Later on I also allowed \( alternative\ block-building \), in which I replace \( T_0 \) with something else when finding an alternative solution for \( S \), ex. extending the 4x4 block to 5x4 instead of 4x5, which corresponds to \( T_0'=[0,1,2,3,\ 6,7,8,9,\ 12,13,14,15,\ 18,19,20,21,\ 24,25,26,27] \), but this method would still have to try too many possible \( P \) and thus become too slow for larger BFS-pair-optimization test case. Additionally, because I used BFS to generate all possible \( P \) within a certain move count, the program would run out of Java heap space; this is exactly what happened in the 4x4->4x5->5x5 phase optimization at threshold \( t=25 \) that the new method solves.

In the new method, I choose some number \( l \), starting at the minimum number of moves needed to solve \( S \) up to \( T_0 \), then DFS over all possible \( A \) obtainable with \( \le l \) moves such that \( AST_0=T_0 \), which can be done reasonably quickly with some pruning, until \( A \) together with the resulting phase 1 scramble \( \mathcal{B}(AS) \) take \( \le t \) moves. If no such sufficiently short solution is found, try alternative block-building. If still no solution is found, increase \( l \) by 1 and try again.

Because this new method is much more direct in searching for alternative phase 0 solutions, and it generates them using DFS instead of BFS, it finds sufficiently short solutions far more quickly and uses far less memory. The code is also simpler, as I can remove the "transformed solving" technique I described in the last forum post, as well as several now-obsolete helper methods. (Edit: transformed solving actually can still have an effect; I just didn't include it because I wanted to start off simple when rewriting my programs; I will probably add back transformed solving at some point).

*Important speed optimizations:*

I use a lot of lookup tables. Also, when not using alternative block-building, I try improving all scrambles \( S \) with a certain fixed phase 0 scramble portion (i.e. with the same sub-scramble \( ST_0 \)) at once, by only DFSing on the phase 0 solution once and then testing all applicable \( S \) with each generated solution.

I didn't use phase 0 symmetry reduction this time, as in the case of 6x6: 4x4->4x5->5x5 it does nothing. However, it will be important in other BFS-pair-optimization test cases I plan to do later.


----------



## coolcomputery (Nov 18, 2021)

*6x6 GN is at most 93.*

The phase 4x4->5x5 has a GN of 24, and this time it's tight. After finally realizing that I have a 64-bit JVM and can increase Java heap space beyond 4 GB, I simply ran a BFS over the entire phase instead of using the 2-phase + threshold technique like I have been for the past several months.
*24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 24 (4x4->5x5) + 24 (5x5->6x6)=93.*

Code: https://github.com/coolcomputery/Lo...1d92941c7cbb18da1c09900db05/BFSLargeFile.java
There are 20!/11!=60949324800 states in the phase. BFSing all of them took 175950.654 seconds, or about 49 hours. Total memory usage was <=10 GB in Java heap space (using the flag \( \texttt{-Xmx10g} \) in the command line) and 304.83 GB on disk.

Distribution:

```
0:1
1:4
2:20
3:101
4:462
5:2093
6:9298
7:40215
8:171078
9:712885
10:2892970
11:11380055
12:42963444
13:154142212
14:518897987
15:1599501934
16:4319908641
17:9553119850
18:15751315904
19:16900073140
20:9726694660
21:2217469365
22:147741036
23:2285403
24:2042
```

I use 0-indexing, so the solved state for the 4x4->5x5 phase looks like this:

```
X  X  X  X  4  .
  X  X  X  X 10  .
  X  X  X  X 16  .
  X  X  X  X 22  .
 24 25 26 27 28  .
  .  .  .  .  .  .
```
There are 2042 antipodes for this phase. One of them is:

```
X  X  X  X 16  .
  X  X  X  X  4 10
  X  X  X  X  .  .
  X  X  X  X  . 27
  . 26 25  .  .  .
 24 28  . 22  .  .
```
I have attached a file to this forum post containing the full list of antipodes.


----------



## coolcomputery (Apr 4, 2022)

No new upper bounds, but I have found that the 0x0->3x3->5x5 block-building approach for solving 5x5 Loopover can at best yield an upper bound of 16+25=41, if during the 3x3->5x5 phase we are only allowed to move the last two rows and last two columns.

```
.....
.....
..MLK
..HGF
..CBA

depth 16: R2' R3' C1' C3 R0 R3' C3 R0 C4 R1 C1' R3' C1' R2' R0 C2

...PU
...QV
...RW
DINSX
EJOTY

depth >=25, where only the last two rows and last tow columns can be moved: no explicit solution found
```

I first run a partial BFS over the entire scramble space, then for a given scramble I iteratively DFS over (canonical) move sequences of increasing length until applying the move sequence to the scramble yields a new scramble that has already been visited in the partial BFS. "Canonical" means that a move cannot be immediately followed by its inverse, and if there are two consecutive row moves Ra(s),Rb(t) or column moves Ca(s),Cb(t), where s,t=1,-1, then a<=b (since such pairs of moves are commutative, so we can force an order on them). Code is at https://github.com/coolcomputery/Lo...cbc445a60866be2faa986dd1dcae9744/BFS_DFS.java, along with (partial) program output (click on the three dots next to the commit message to show).

Note that from an earlier result, God's number of 0x0->3x3 is at most 17, which is only one more than the current lower bound of 16 (as shown above). I've been trying to prove an upper bound of 16 (in fact I already tried it once back in November 2021), but my code requires trying a few hundred to a few thousand solutions per scramble, and I estimate that with my current code it will take about 13 days to complete, so for now I will focus on optimizing my code.


----------



## coolcomputery (Apr 11, 2022)

*6x6 GN is at most 23+19+23+24=89.*


```
......     #.#...     #.#.#.
......     ......     ......
...... --> #.#... --> #.#.#.
......     ......     ......
......     ......     #.#.#.
......     ......     ......
GN <= 23 (2-phase improvement)
https://gist.github.com/coolcomputery/8df7c6376572177e96ef77a518c92a49
59874.516 seconds
```


```
#.#.#.     ###.#.
......     ###.#.
#.#.#. --> ###.#.
......     ......
#.#.#.     ###.#.
......     ......
GN = 19 (BFS)
https://gist.github.com/coolcomputery/58244113ebe484b2ec69d1f762126057#file-6x6-010101x010101-000101x000101_stdout-txt
4180.937 seconds
```



Spoiler: depth distribution



0:1
1:4
2:28
3:170
4:932
5:4892
6:24946
7:123168
8:586358
9:2659448
10:11316244
11:44222892
12:153644726
13:450373068
14:1013585741
15:1481606620
16:1061671686
17:246558712
18:9284500
19:7064




```
###.#.     #####.
###.#.     #####.
###.#. --> #####.
......     #####.
###.#.     #####.
......     ......
GN = 23 (BFS)
https://gist.github.com/coolcomputery/58244113ebe484b2ec69d1f762126057#file-6x6-000101x000101-000001x000001_stdout-txt
116255.370 seconds
```



Spoiler: depth distribution



0:1
1:4
2:20
3:98
4:444
5:1980
6:8695
7:37618
8:160443
9:674029
10:2779829
11:11186512
12:43572549
13:162549363
14:571952209
15:1849682401
16:5239753101
17:11949256158
18:19002513098
19:16462006262
20:5266439024
21:382800089
22:3949330
23:1543




```
#####.     ######
#####.     ######
#####. --> ######
#####.     ######
#####.     ######
......     ######
GN = 24 (BFS)
already known; can also be calculated with the line
    new BFS("000001x000001","000000x000000");
~23 seconds
```

Source code is at https://github.com/coolcomputery/Lo...tree/f1197382a3d2811debeb240bb6c66465bff8c054 with classes BFS.java, BFS2improve.java, BFS_DFS.java, and BFSLowMemory.java used (BFS_DFS.java is referenced in the code of BFS2improve.java but it was not actually used in the specific 2-phase improvement).

(Note: some parts of the standard out may look strange because my laptop may have been asleep for a few hundred seconds at a time.)

I simplified my 2-phase improvement by making symmetry reduction less restrictive, which allows me to use all 72 symmetries between the start and final state in the 2-phase improvement section. I also made a new and even more memory-efficient BFS program that uses two bitsets stored as binary files, rather than several lists of indices of all nodes at each depth. For the larger test case that took 116255.370 seconds, the old program for large BFS trees would use about 20x as much disk memory.

*Explanation* (for a third time but I hope this time it is clearer than the last two):

Again, we represent the location on row \( r \) and column \( c \) on the \( R\times C \) Loopover board with the index \( rC+c \). A permutation ("scramble") over a board is represented with a list \( A \), where tile \( i \) is sent to location \( A_i \).

The product of two lists \( A,B \) is defined as \( C=AB \) such that \( C=A_{B_i} \). This product is associative.

The set of all permutations made from a single move (i.e. a single-unit shift of one row or column) is \( \mathcal{M} \).

In 2-phase optimization, we are given three lists of pieces \( R_0,R_1,R_2 \) such that \( R_0\subset R_1\subset R_2 \) (i.e. all pieces in \( R_0 \) are contained in \( R_1 \), all pieces in \( R_1 \) are contained in \( R_2 \), and the three lists are all different from each other). For each scramble \( P \) such that \( PR_0=R_0 \) (i.e. all pieces in \( R_0 \) are already solved), we want to find a permutation \( A=M_{k-1}\dots M_1 M_0 \) made of \( k\le \) some threshold \( t \) number of moves, such that \( APR_2=R_2 \) (i.e. applying \( A \) to \( P \) solves all pieces in \( R_2 \) (which includes all pieces in \( R_0 \))), and none of the moves \( M_i \) affect any pieces in \( R_0 \).

However, directly finding such \( A \) may be too expensive, since the search space may be too big. Instead, we construct the BFS tree of all permutations of pieces in \( R_1 \) with \( R_0 \) already solved, and the BFS tree of all permutations of pieces in \( R_2 \) with \( R_1 \) already solved. When solving a \( P \), we first apply an optimal permutation \( A \) (i.e. a permutation made of the lowest number of moves) to solve up to \( R_1 \) (i.e. \( APR_1=R_1 \)), then apply another optimal permutation \( B \) to solve up to \( R_2 \) (i.e. \( BAPR_2=R_2 \)), using the BFS trees to find such optimal permutations. Then if \( A \) and \) B \) collectively require more than \( t \) moves, we try to find a better solution (explained in more detail at the end of the post).

*Symmetry reduction*:

Let \( S \) be a "rigid" transformation over the entire board, meaning that for every single-move permutation \( M \) in \( \mathcal{M} \), \( SMS^{-1} \) is also a single-move permutation (ex. \( S \) can be a translation, rotation, reflection, or any composition of these transformations, of the entire board). We further require that there exist permutations \( Q_0,Q_2 \) such that \( S R_0 Q_0 = R_0 \) and \( S R_2 Q_2 = R_2 \) (i.e. the region that the pieces \( R_0 \) form is preserved, and so is for \( R_2 \)).

Suppose we have \( P \) such that \( PR_0=R_0 \), and \( A=M_{k-1}\dots M_1 M_0 \) such that \( APR_2=R_2 \). Let \( P'=SPS^{-1} \) and \( A'=SAS^{-1} \); then \( P'R_0=(SPS^{-1})(SR_0 Q_0)=SP(S^{-1}S)R_0 Q_0=SPR_0 Q_0=SR_0 Q_0=R_0 \) and \( A'P'R_2=(SAS^{-1})(SPS^{-1})(SR_2 Q_2)=SA(S^{-1}S)P(S^{-1}S)R_2 Q_2=SAPR_2 Q_2=SR_2 Q_2=R_2 \), so \( P' \) already has \( R_0 \) solved and \( A' \) solves \( P' \) up to \( R_2 \). Also, since \( SAS^{-1}=(SM_{k-1}S^{-1})\dots (SM_1 S^{-1})(SM_0 S^{-1}) \), \( A \) and \( A' \) can be made of the same number of moves.

This means that if we can solve \( P \) in \( \le t \) moves, we can also solve \( SPS^{-1} \) in \( \le t \) moves. Therefore, from the set of all permutations \( \{SPS^{-1}\} \) for valid \( S \) under fixed \( P \), we only have to solve one of them. Currently, we choose the lexicographically lowest permutation.

In the algorithm, we actually only care about the part of \( P \) that are in \( T= R_2 \setminus R_0 \) (i.e. the set of pieces we are trying to solve); the existance of \( Q_0 \) and \( Q_1 \) imply the existence of some \( Q \) such that \( STQ=T \); then \( (SPS^{-1})T=SPS^{-1}(STQ)=S(PT)Q \), so the "subscramble" \( U=PT \) is transformed into \( SUQ \).

In the past, I would further restrict \( S \) to also preserve the region that the pieces \( R_1 \) form, since that would allow us to do symmetry reduction over all \( P \) without having to iterate over every possible \( P \). However, I currently don't know any tricks to analyzing the lexicographic order of \( U \) changes when it becomes \( SUQ \), so for now I iterate over all possible \( U \). When the threshold \( t \) is high enough and it is not too difficult to find alternative solutions for permutations that initially require \( >t \) moves, this program is much slower than my previous 2-phase improver. However, for low enough \( t \) (ex. 5x5: 0x0->ACKM->3x3, \( t=16 \)), both programs' running times are similar.

*More detail on how to find solutions of* \( \le t \)* moves*:

We first iteratively DFS over every permutation \( A \) made of \( l_a \) moves that solves \( P \) up to \( R_1 \) (i.e. \( APR_1=R_1 \)), then check if \( AP \) can be solved up to \( R_2 \) in \( \le t-l_a \) moves (which can be done efficiently with the second BFS tree). After each DFS, we increment \( l_a \) and repeat; if \( l_a \) goes past \( t \), then we know \( P \) cannot be solved up to \( R_2 \) in \( \le t \) moves.

(Not used in the 6x6 2-phase improvement but it could be useful for other test cases) At some point in the middle of this process, we may terminate and switch to a meet-in-the-middle approach: we run a partial BFS of all pieces in \( R_2\) with \( R_0 \) already solved up to a cetain depth, then iteratively DFS over all permutations \) A \) made of an increasing number of moves until \( APR_2 \) appears in our BFS tree, and check if the generated solution is at most \( t \) moves. This solution is guaranteed to be optimal, so if is more than \( t \) moves, then \( P \) cannot be solved in \( \le t \) moves, and the God's number of \( R_0 \rightarrow R_2 \) is more than \( t \).


----------



## coolcomputery (Apr 17, 2022)

*6x6 GN is at most 22+19+23+24=88*.

```
......     #.#...     #.#.#.
......     ......     ......
...... --> #.#... --> #.#.#.
......     ......     ......
......     ......     #.#.#.
......     ......     ......
GN <= 22 (2-phase improvement)
stdout: https://gist.github.com/coolcomputery/ba0713fad041ae32b0bd777c30b7230a
94537.805 seconds
```

New code (of BFS2improve.java) is at https://github.com/coolcomputery/Lo...6a724c373a9770aeba99787d1528/BFS2improve.java.

In my last post, I said


> ...I currently don't know any tricks to analyzing the lexicographic order of U changes when it becomes SUQ, so for now I iterate over all possible U.


Well, a few days later, I found a trick:

Let \( T_a=R_1\setminus R_0 \) and \( T_b=R_2\setminus R_1 \) be the sets of pieces that are solved by applying the first and second phases, respectively. We call these sets of pieces "target" regions.

For a scramble \( P \) over the entire board, we calculate the subscramble of \( P \) with pieces \( T=T_a||T_b \) as \( U=PT \). We use this value of \( T \) specifically and not just any arbitrary permutation of \( R_2\setminus R_0 \), for reasons that will become clear shortly:

Earlier, we defined \( Q \) as the permutation such that \( STQ=T \), and derived \( (SPS^{-1})T=SPS^{-1}STQ=S(PT)Q=SUQ \). In some cases, \( S \) will also keep the target regions \( T_a \) and \( T_b \) separated from each other, i.e. there exist \( Q_a,Q_b \) such that \( ST_aQ_a=T_a, ST_bQ_b=T_b \); we call such transformations \( S \) "friendly".

Then, since we defined \( T \) as \( T_a||T_b \), we have that \( STQ=T \rightarrow S(T_a||T_b)Q=T_a||T_b=(ST_aQ_a)||(ST_bQ_b) \), so \( TQ=(T_a||T_b)Q=(T_aQ_a)||(T_bQ_b) \). This also allows us to split the subscramble \( U \) into ( U_a,U_b \); \( U_a=PT_a, U_b=PT_b \).

Finally, we have \( U=U_a||U_b \), and for friendly \( S \) we have \( SUQ=SPTQ=SP((T_aQ_a)||(T_bQ_b))=(SPT_aQ_a)||(SPT_bQ_b)=(SU_aQ_a)||(SU_bQ_b) \).

The reason this fact is useful is because we currently perform symmetry reduction by only considering a subscramble \( U \) if it is a lexicographically minimum element in the set \( \{SUQ\}_{S\textrm{ rigid, } STQ=T} \). If \( S \) is friendly, then for \( U \) to be lexicographically not greater than \( SUQ=(SU_aQ_a)||(SU_bQ_b) \), \( U_a \) must be lexicographically not greater than \( SU_aQ_a \). Thus, when iterating over possible \( U \), we can restrict all \( U_a \) to be a lexicographically minimum element in the set \( \{SU_aQ_a\}_{S\textrm{ friendly, } ST_aQ_a=T_a} \).

For this 2-phase improvement, we reduce the number of possible \( U_a \) to consider by about 8 times, compared to my previous algorithm; we end up reducing the total time spent on symmetry reduction by maybe 5 times, according to some smaller test cases I ran (I'm still not sure why it is not 8 times). Even then, for this test case (proving a God's number of <= 22 for these two phases), we still spend about 40,000 seconds on symmetry reduction alone, which is over 40% of the total running time, so more improvements should be made.

*NOTE (2022-04-17)*: By using a partial BFS + DFS program I mentioned in an earlier post, the following scramble takes at least 17 moves to solve, showing that with the current solving scheme of 6x6 Loopover we are using (i.e. 0x0->2x2->3x3->4x4->5x5->6x6, with some lattices being spaced out), the best upper bound on 6x6 GN we can obtain is 17+19+23+24=83:

```
0  .  12 .  24 .            0  .  2  .  4  .
.  .  .  .  .  .  solve to  .  .  .  .  .  .
2  .  14 .  26 .    --->    12 .  14 .  16 .
.  .  .  .  .  .            .  .  .  .  .  .
4  .  16 .  28 .            24 .  26 .  28 .
.  .  .  .  .  .            .  .  .  .  .  .
depth >= 17
https://gist.github.com/coolcomputery/059144327f7b8cc07b9361688e34d063
```

Currently, I am thinking of using a different solving scheme, such as 0x0->2x2->3x3->3x5->4x5->5x5->6x6 (with some lattices being spaced out), as this allows us to do practical 2-phase improvements in more places:

```
......       #.#...       #.#.#.
......       ......       ......
......  -->  #.#...  -->  #.#.#.
......       ......       ......
......       ......       #.#.#.
......       ......       ......
2-phase improvement
GN <= 22

#.#.#.       #####.       #####.
......       ......       #####.
#.#.#.  -->  #####.  -->  #####.
......       ......       ......
#.#.#.       #####.       #####.
......       ......       ......
2-phase improvement
GN <= 35
8289.403 seconds
https://gist.github.com/coolcomputery/16bed7efbf4951801345b7e9bb6ab91c#file-6x6_010101x010101-010101x000001-000101x000001_stdout-txt

#####.       #####.       ######
#####.       #####.       ######
#####.  -->  #####.  -->  ######
......       #####.       ######
#####.       #####.       ######
......       ......       ######
2-phase improvement
GN <= 37
4644.727 seconds
https://gist.github.com/coolcomputery/16bed7efbf4951801345b7e9bb6ab91c#file-6x6_000101x000001-000001x000001-000000x000000_stdout-txt
```
--------------------------------------------------------------------------------------------------------------------------------
(2022-04-23): *5x5 GN <=* 17 (0x0 --> ACKM --> 3x3) + 26 (3x3 --> 4x4 --> 5x5) = *43*.

```
###..       ####.       #####
###..       ####.       #####
###..  -->  ####.  -->  #####
.....       ####.       #####
.....       .....       #####
GN <= 26
113217.506 seconds
stdout: https://gist.github.com/coolcomputery/9033eee59e40446004c93de19516b945
```
--------------------------------------------------------------------------------------------------------------------------------
(2022-05-10): *5x5 GN *<= 17 (0x0 --> ACKM --> 3x3) + 25 (3x3 --> 4x4 --> 5x5) = *42*.

```
###..       ####.       #####
###..       ####.       #####
###..  -->  ####.  -->  #####
.....       ####.       #####
.....       .....       #####
GN <= 25
304814.840 seconds
stdout: https://gist.github.com/coolcomputery/6b4d6be5d26bb10f5ce74500083b5289
```
I found an even more powerful (and simpler) optimization to symmetry reduction: given scrambles \( U=U_a || U_b \) of the set of pieces we want to solve, and \( S U Q \) a transformed version of \( U \): if we only know what \( U_a \) is and not \( U_b \), we can fill in as many elements of \( S U Q \) that we can determine, then lexicographically compare \( U \) and \( S U Q \) by comparing corresponding elements until we reach an element of unknown value in either scramble. If we find \( U \) is lexicographically greater than \( S U Q \) even with incomplete knowledge of either scramble, then even if we know \( U_b \), \( U \) is still lex. greater than \( S U Q \), so this tactic allows us to better eliminate \( U_a \). This also removes the need to designate certain transformations \( (S,Q) \) as "friendly", since all transformations are treated the same.


----------

