cp's OEIS Frontend

A349244 Minimal sequence of single-tile sliding moves that transpose the upper-left triangle of size 2, then 3, then 4, ... of an infinite square matrix (see comments for details).

%I A349244 #21 Dec 04 2021 12:41:01
%S A349244 1,4,2,5,8,12,7,3,4,2,5,1,2,5,3,4,5,2,1,3,4,7,12,8,3,1
%N A349244 Minimal sequence of single-tile sliding moves that transpose the upper-left triangle of size 2, then 3, then 4, ... of an infinite square matrix (see comments for details).
%C A349244 Consider the infinite square matrix filled with the nonnegative integers by falling antidiagonals (cf. A001477 displayed as table / square array),
%C A349244    0  1  3  6  10 ...
%C A349244    2  4  7  11 ...
%C A349244    5  8  12 17 ...
%C A349244   ...
%C A349244 Similar to the moves in the well-known sliding puzzle, "move m" consists in shifting the nonzero elements between the "empty tile" 0 and a number m in the same row or column as 0, one place towards the 0, and placing the 0 in the former location of m, cf. EXAMPLE. If m is an immediate neighbor of 0 (so m and 0 simply exchange their places) this is a single-tile move, else a multi-tile move.
%C A349244 The target configuration is the transposed matrix, cf. A061579 read as table / square array. More precisely, we call goal [k] any infinite matrix where all of {0, ..., k} are in the same position as in the transposed matrix. The position of numbers > k is irrelevant.
%C A349244 This sequence gives the shortest (and in case of a tie, the lexicographically earliest) sequence of single-tile moves that successively achieves goal [k], k = 2, 5, 9, ... = A000096(1, 2, 3, ...), i.e., completely transposes the upper left triangle of size 2, then of size 3, etc.: see EXAMPLE for more details.
%C A349244 The sequence can be read as irregular table where row r gives the moves which yield goal [k = A000096(r)] starting from the previous goal [A000096(r-1)].
%C A349244 There are several possible variants of this sequence, mainly corresponding to different goals (see A349245 for achieving goal [1], [2], [3], ...; one may also consider goals (k) where only the positions of {1, ..., k} matter, but the location of 0 and the element in the top left corner do not matter) and/or allowing multi-tile moves.
%H A349244 M. F. Hasler, in reply to J. Propp, <a href="https://mailman.xmission.com/hyperkitty/list/math-fun@mailman.xmission.com/message/NZ6VRF3Q4VTGOIVVGUUAVRFC3XJGKBOK/">Infinite sliding block puzzle</a>, math-fun discussion list, Nov. 3, 2021
%H A349244 Wikipedia, <a href="https://en.wikipedia.org/wiki/15_puzzle">15 puzzle</a>, retrieved Nov. 2021
%e A349244 After the three moves a(1..3) = (1, 4, 2), the upper left becomes
%e A349244    1  4  3 ...
%e A349244    0  2  7 ...
%e A349244   ...
%e A349244 One further move '1' would place the tile = value 1 in its final position (row 2, column 1); then moves 4 and 2 would lead to
%e A349244    4  2  3 ...
%e A349244    1  0 ...
%e A349244   ...
%e A349244 where 1 and 2 have their final position. (This is called goal (2) in COMMENTS.) However, to achieve goal [2] with also 0 in its initial position (row 1, column 1), one has to proceed differently, see a(4..12).
%e A349244 Read as a table whose n-th row completes transposition of the (1+n)-th antidiagonal, the sequence reads:
%e A349244 row 1: [1, 4, 2, 5, 8, 12, 7, 3, 4, 2, 5, 1] \\ here antidiagonals 1 & 2 are transposed
%e A349244 row 2: [2, 5, 3, 4, 5, 2, 1, 3, 4, 7, 12, 8, 3, 1] \\ here, antidiagonals 1-3 are transposed.
%o A349244 (PARI) (init(n=4)={M=X=Y=vector(2*(n-1)*n); NM=!X0=Y0=1; B=matrix(n, n, y, x, if( n=(x+y)*(x+y-1)\2-y, X[n]=x; Y[n]=y; n))})(); M349244=Map()/*for memoization*/
%o A349244 move(m/*0 = undo*/)={if(m>0, #M>NM||M=Vec(M,NM+9); M[NM++]=m, m=M[NM]; NM--); B[Y0, X0]=m; [X0, Y0, X[m], Y[m]]= [X[m], Y[m], X0, Y0]; B[Y0, X0]=0}
%o A349244 movelist(L=#B)={setminus( Set([ B[Y0+imag(I^k), X0+real(I^k)] | k<-[0..3], if(k>2, Y0>1, k>1, X0>1, k, Y0<L, X0<L) ]), if(NM, [M[NM]], []))}
%o A349244 /* do DFS of depth d>0, check goal if d=0, if d<0 do DFS with d=1, 2, 3...*/
%o A349244 find(goal, d=-1, L=#B)={if( !d, !for(y=1, #goal, for(x=1, #goal[y], B[y, x]==goal[y][x]||return)), d<0, d=0; until(find(goal, d++, L),); M[NM-d+1..NM], foreach(movelist(), m, move(m); find(goal, d-1, L)&& return(1); move()))}
%o A349244 goal(k, g=[[0]])={for(j=1, k, if(#g[#g]>1, g=concat(g, [[j]]), g[k=j-g[#g][1]]=concat(g[k], j))); g}
%o A349244 A349244_row(r)=iferr(mapget(M349244, r), E, init(r+2); for(k=1, r-1, apply(move, A349244_row(k))); mapput(M349244, r, r=find(goal(r*(r+3)\2))); r)
%Y A349244 Cf. A001477 (read as square array = initial configuration), A061579 (read as square array = final configuration), A004736 and A002260 (x- and y-coordinates of 0, 1, 2, ... in initial resp. final configuration).
%Y A349244 Cf. A000096 = A000217(1, 2, ...) - 1.
%Y A349244 Cf. A349245 (variant where goals [1], [2], [3], ... are achieved "individually").
%K A349244 nonn,more,hard
%O A349244 1,2
%A A349244 _M. F. Hasler_, Nov 16 2021