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).

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

Offset: 1

Author

M. F. Hasler, Nov 16 2021

Keywords

• nonn
• more
• hard

Comments

Consider the infinite square matrix filled with the nonnegative integers by falling antidiagonals (cf. A001477 displayed as table / square array),

0 1 3 6 10 ...

2 4 7 11 ...

5 8 12 17 ...

...

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.

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.

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.

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)].

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.

Examples

			After the three moves a(1..3) = (1, 4, 2), the upper left becomes
   1  4  3 ...
   0  2  7 ...
  ...
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
   4  2  3 ...
   1  0 ...
  ...
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).
Read as a table whose n-th row completes transposition of the (1+n)-th antidiagonal, the sequence reads:
row 1: [1, 4, 2, 5, 8, 12, 7, 3, 4, 2, 5, 1] \\ here antidiagonals 1 & 2 are transposed
row 2: [2, 5, 3, 4, 5, 2, 1, 3, 4, 7, 12, 8, 3, 1] \\ here, antidiagonals 1-3 are transposed.
		

Links

• M. F. Hasler, in reply to J. Propp, Infinite sliding block puzzle, math-fun discussion list, Nov. 3, 2021
• Wikipedia, 15 puzzle, retrieved Nov. 2021

Crossrefs

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).

Cf. A000096 = A000217(1, 2, ...) - 1.

Cf. A349245 (variant where goals [1], [2], [3], ... are achieved "individually").

Programs

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*/
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}
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, Y00, check goal if d=0, if d<0 do DFS with d=1, 2, 3...*/
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()))}
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}
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)