A349245 Minimal sequence of single-tile sliding moves that progressively transpose elements 0 through k (k = 1, 2, 3, ...) of the infinite square matrix, cf. comments for details.

1, 4, 2, 1, 4, 2, 1, 4, 2, 3, 7, 12, 8, 5, 4, 1, 3, 2, 1, 3, 5, 4, 3, 1, 2, 5, 4, 8, 12, 7, 5, 2, 1, 3, 8, 13, 9, 8, 3, 1, 2, 5, 6, 11, 7, 6, 5, 2, 1, 4, 6, 12, 13, 6, 4, 3, 6, 9, 8, 6, 3, 1, 2, 4, 12, 7, 17, 13, 7, 12, 9, 7, 12, 9, 4, 2, 1, 3, 7, 8, 18, 12, 8, 18, 12, 24, 13, 17, 9

Offset: 1

Author

M. F. Hasler, Nov 18 2021

Keywords

• nonn
• more
• hard
• tabf

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

2 4 7 11 ...

5 8 12 17 ...

...

Similar to the moves in the well-known sliding puzzle, "move m" consists in shifting one place towards "empty tile" 0 all nonzero elements between 0 and the nonzero number m in the same row or column as 0, and moving 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 achieve goal [1], then [2], then [3], etc. It can be considered as an irregular table where row k gives the moves needed to go from goal [k-1] to goal [k]. See EXAMPLE for details.

It is interesting to note that goal [2] cannot be achieved without using a tile outside the upper left 2 X 2 square, and goal [5] can't be achieved within the 3 X 3 square. Goal [9] can be achieved within the 4 X 4 square, with moves (2, 5, 11, 9, 8, 11, 5, 4, 7, 18, 11, 8, 17, 11, 18, 7, 4, 2), but the minimal solution (row 9, see EXAMPLE) requires using row 5.

There are several variants of this sequence, mainly by achieving different goals and/or considering multi-tile moves. See A349244 for successive goals [1], [2], [3], .... One can also consider goals (k) where only the position of {1, ..., k} must be as given. Then goal (2) is achieved through moves (1, 4, 2, 1, 4, 2).

Examples

			Starting from the initial configuration (cf. comments), the first possible move "1" means to slide the 1 from row 1, column 2 to the "empty square" 0 at (1,1); then move "4" slides the 4 one up, and move "2" slides the 2 to the right:
   0  1  3 ...   (1)   1  0  3 ...   (4)   1  4  3 ...   (2)   1  4  3 ...
   2  4  7 ...   ==>   2  4  7 ...   ==>   2  0  7 ...   ==>   0  2  7 ...
   ... ... ...         ... ... ...         ... ... ...         ... ... ...
The next move, 1, will place that tile in its final position (row 2, column 1):
   (1)   0  4  3 ...
   ==>   1  2  7 ...
         ... ... ...
Given that the 0 is also in its final position (1,1), this achieves what we call goal [1]. Now further moves 4 and 2 would move the 2 in its final position (1,2), so {1, 2} are in their final position, but 0 isn't. (This is called goal (2) in comments.)
However, to achieve goal [2] with also 0 in its initial position (row 1, column 1), in a minimum number of moves, one has to proceed differently: see a(4..18).
Formatted as an irregular table with rows ending with achieved goals [1], [2], [3], ... the sequence reads:
row 1: [1, 4, 2, 1]   \\ here {0, 1} are at their final position
row 2: [4, 2, 1, 4, 2, 3, 7, 12, 8, 5, 4, 1, 3, 2] \\ here {0, 1, 2} are "done"
row 3: [1, 3, 5, 4, 3, 1] \\ here {0, 1, 2, 3} are in their final position
row 4: [2, 5, 4, 8, 12, 7, 5, 2] \\ now {0, ..., 4} are in their final position
row 5: [1, 3, 8, 13, 9, 8, 3, 1] \\ now {0, ..., 5} are in their final position
row 6: [2, 5, 6, 11, 7, 6, 5, 2, 1, 4, 6, 12, 13, 6, 4, 3, 6, 9, 8, 6, 3, 1]
row 7: [2, 4, 12, 7, 17, 13, 7, 12, 9, 7, 12, 9, 4, 2]
row 8: [1, 3, 7, 8, 18, 12, 8, 18, 12, 24, 13, 17, 9, 8, 18, 7, 3, 1]
row 9: [2, 4, 8, 18, 17, 23, 16, 10, 11, 9, 18, 8, 4, 2]
		

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. A349244 (achieve goals [2], [5], [9], ... with minimum number of moves).

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

Programs

PARI

M349245=Map()/*for memoization*/; A349245_row(k)={iferr(mapget(M349245, k), E, my(g=goal(k)); init(#g+1); for(j=1,k-1, A349245_row(j)); mapput(M349245, k, r=find(g)); r)} \\ see A349244 for helper functions find(), goal(), init()...