OFFSET
1,2
COMMENTS
For this sequence, a Rubik's Square is 2 dimensional and only has 2 colors. This sequence uses quarter-turn notation; a move is a reversion of either a row or column. So, if one color is '1' and the other is '0', performing a move on [0,1,1,0,0] would make that row/column [1,1,0,0,1].
There are two questions associated with this triangle. First, how many permutations are reachable for an n X n Rubik's Square (what is the maximum value in the n-th row)? Second, what is the number of moves necessary to solve an n X n Rubik's Square (when does the n-th row terminate)?
LINKS
E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, and A. Winslow, Algorithms for Solving Rubik’s Cubes, arXiv:1106.5736 [cs.DS], 2011.
E. D. Demaine, S. Eisenstat, and M. Rudoy, Solving the Rubik's Cube Optimally is NP-complete, arXiv:1706.06708 [cs.CC], 2017-2018.
EXAMPLE
The irregular triangle T(n,k) starts:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 ...
1: 1 2
2: 1 5 6
3: 1 7 30 71 119 160 184 192
4: 1 9 53 221 592 1072 1296
5: 1 11 80 488 2550 10511 35601 99142 218400 382480 538912 630080 ...
PROG
(PARI) A335136_row(n)={my(total=List([0]), completed=List(), moves=[1..2*n], moves2=select(X->X, [-n..n]), M=List([]), moves2bits=Map(Mat([moves~, apply(y-> my(Q=Map(Mat([(S=select(X->floor(X/(n^(y<0)))%n==(abs(y)-1), [0..n^2-1]))[1..ceil(#S/2)]~, Vecrev(S)[1..ceil(#S/2)]~])));
apply(X->shift(shift(1, mapget(Q, X)-X)+(X!=mapget(Q, X)), X), Mat(Q)[, 1]) , moves2)~])), mover(Y, Z)=bitxor(Z, vecsum(select(W->my(B=bitand(Z, W)); (!B||B==W), mapget(moves2bits, Y)))));
while(#completed<#total, listput(M, #total); my(new=setminus(Vec(total), Vec(completed))); completed=total; forvec(A=[[1, 2*n], [1, #new]], my(F=mover(A[1], new[A[2]]), S=setsearch(total, F, 1)); if(S, listinsert(total, F, S)))); M}
CROSSREFS
KEYWORD
nonn,tabf,more
AUTHOR
Davis Smith, Jun 02 2020
STATUS
approved