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 ...
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).
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
EXAMPLE
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]
PROG
CROSSREFS
KEYWORD
nonn,more,hard,tabf
AUTHOR
M. F. Hasler, Nov 18 2021
STATUS
approved