Fifteen Puzzle
The Fifteen Puzzle, invented by Noyes Chapman in 1878, is a classic puzzle game. It features a set of identical square tiles, each marked with a number, arranged within a square box. The box's side length is four times that of a tile, leaving one square space empty. The objective is to slide the tiles around to arrange them in numerical order, as depicted in the image below.
Moves are defined by shifting the empty space: it can move right ("R"), left ("L"), up ("U"), or down ("D"), swapping positions with the adjacent tile in the chosen direction.
Your task is to find the shortest sequence of moves that transforms the initial puzzle configuration into the ordered state.
Input
The input consists of 4 rows, each containing 4 numbers ranging from 0 to 15. These numbers represent the tiles in the initial puzzle configuration, where 0 denotes the empty space. Each number appears exactly once.
Output
The output should be a single line. If the puzzle cannot be solved from the given state, output "NO SOLUTION". If a solution exists, provide the shortest sequence of moves to reach the final state. If the optimal sequence is longer than 45 moves, output "TOO LONG".