Sort the Sliding Number Tray

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

Write slide_plan(board) that returns a shortest sequence of moves that sorts the tray, as a string of letters naming the direction the gap moves in each move: 'U' (up), 'D' (down), 'L' (left), 'R' (right). Return '' if the tray is already sorted and None if no sequence of moves can ever sort it.

Several shortest sequences may exist; any one of them is accepted. The checker replays your moves and compares their number with the fewest possible.

Examples

Input:  board = [[1, 2, 3],
                 [4, 5, 6],
                 [7, 0, 8]]
Output: "R"
Explanation: the gap moves right, so tile 8 slides left into place.

Input:  board = [[4, 1, 3],
                 [7, 2, 6],
                 [0, 5, 8]]
Output: "UURDDR"   (6 moves; another 6-move plan would also be accepted)

Input:  board = [[1, 2, 3],
                 [4, 5, 6],
                 [8, 7, 0]]
Output: None
Explanation: swapping just two tiles can never be done with moves.

Constraints

• 2 <= rows, cols <= 3; board holds every number 0 .. rows*cols - 1 exactly once
• the answer never depends on the clock or on randomness

Goals

• Search a graph whose nodes are whole boards, generating neighbours on the fly
• Rebuild the move sequence from parent links
• Spot unsolvable boards with a parity argument instead of searching