3240：Solution to the n2 − 1 Puzzle

In addition to the eight queen puzzle, another famous puzzle that has also been generalized is the fifteen puzzle. For a puzzle of size n × n, natural numbers below n² are placed into squares leaving one empty. The puzzle is solved by sliding the squares until it looks similar to that shown in the figure below. Given the starting configuration, you are to find a solution or report that no solution exists.

The input contains exactly one test case. The first line of input contains n (n ≤ 10). The next n² numbers describe the puzzle by rows. The empty square is represented by zero.

If no solution exists, just print “No Answer!”. Otherwise print a string consisting of the letters “L” (left), “R” (right), “U” (up), “D” (down) showing how the empty square moves to solve the puzzle.