• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

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

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
Summary of current knowledge (2023-03-22):

STM:
4×4: 18 (by rokicki)
5×5: ≤42 (by coolcomputery)
6×6: ≤86 (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.
(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)
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.
Code:
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
Code:
 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.
Code:
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.
Code:
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

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.

Code:
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:

Code:
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.

Code:
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.

========

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.)
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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.
 
Last edited:

zman

Member
Joined
Feb 4, 2019
Messages
33
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

Member
Joined
Dec 24, 2015
Messages
2,877
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:
Code:
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:
Code:
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.

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: )
Code:
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.
 
Last edited:

Ben Whitmore

Member
Joined
Sep 28, 2019
Messages
48
tl;dr STM GN for 5×5 is at least 22.

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

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} \)
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
4x4 STM GD is at most 23

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
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.
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)
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.
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
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.
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
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
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
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.
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
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
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
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
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.
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
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
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
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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:
Code:
. . . . . a
. . . . . b
. . . . . c
d e f g h i
is a solved state, then so are all of these:
Code:
. . . . . 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:
Code:
. . . . . 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.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
First explicit example of a 5×5 state that requires 22 moves to solve:
Code:
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.

Code:
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:
Code:
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
Code:
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.
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.
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.
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.
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.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
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.)

Code:
. . . 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.
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.
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.
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
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:

2345678
24 (1)7(3)10(4)13(205)16(2302)20(1680)23
38(2475)14(6)17(15)19..23
418(32)

MTM:

2345678
24 (1)7(3)8(2264)12(315)14(288)18(196)19
38(2475)13(2)14(6415)16..20
414

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

Member
Joined
Dec 24, 2015
Messages
2,877
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:
Code:
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.
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
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:

Code:
rokicki@Clerestory 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

Member
Joined
Dec 24, 2015
Messages
2,877
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

Member
Joined
Oct 31, 2008
Messages
301
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

Member
Joined
Dec 24, 2015
Messages
2,877
In the subgroup, we have the FHNP pieces solved (no other restriction on the other 12 pieces):
Code:
. . . .
. F . H
. . . .
. N . P
The generators are 1H, 3H, 1V, 3V.
Then conjugating these generators by a swap of these two locations:
Code:
. 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.
 
Top