The Fifteen-Tile Tray, Optimally

A tray of rows x cols cells holds the tiles 1 .. rows*cols - 1 and one gap, written 0. A move slides a tile that is next to the gap (up, down, left or right of it) into the gap. The tray is sorted when the tiles read 1, 2, 3, ... row by row with the gap in the bottom-right corner.

Return the fewest moves that sort board, or -1 if it can never be sorted.

The boards in the tests are up to 4 x 4 and need up to 40 moves: far too many boards for a search that looks in every direction equally, so the search must be steered well and must stay cheap per board. The setup provides shuffled_tray(rows, cols, slides, seed), which makes a tray by sliding random tiles away from the sorted position; the larger tests use it. Try it with Run: print(shuffled_tray(4, 4, 30, 3)).

Examples

Input:  board = [[ 1,  2,  3,  4],
                 [ 5,  6,  7,  8],
                 [ 9, 10, 11, 12],
                 [13, 14,  0, 15]]
Output: 1

Input:  board = [[ 1,  2,  3,  4],
                 [ 5,  6,  7,  8],
                 [ 9, 10, 11, 12],
                 [13, 15, 14,  0]]
Output: -1
Explanation: no sequence of moves swaps just two tiles.

Input:  board = [[9, 1,  3,  4],
                 [6, 2,  7,  8],
                 [5, 0, 10, 11]]
Output: 12

Constraints

• 2 <= rows, cols <= 4; board holds every number 0 .. rows*cols - 1 exactly once
• every sortable test board can be sorted in at most 40 moves
• the answer never depends on the clock or on randomness

Goals

• Strengthen the Manhattan estimate with linear conflicts without losing admissibility
• Keep the search's memory and time small with iterative deepening or incremental updates
• Decide solvability for even-width trays, where the gap's row matters