|
| |
|
|
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
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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, Y0<L, X0<L) ]), if(NM, [M[NM]], []))}
/* do DFS of depth d>0, 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)
|
|
|
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. A349245 (variant where goals [1], [2], [3], ... are achieved "individually").
|
|
|
KEYWORD
|
nonn,more,hard
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
