SOLVING - Solving the Puzzle

no tags 

The 15 puzzle is a classic puzzle made famous in the 19th century. It consists of 4x4 board with 15 sliding tiles numbered from 1 to 15. The objective is to get them into this pattern:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Here we will deal with a generalized version of the above puzzle. You should write a program that given some initial state of the nxn board finds a sequence of moves that transforms it so that in the i-th row there are tiles with numbers i*n+1,i*n+2,...,i*n+n (from left to right) - with the exception of the lower right corner where the hole should be. The less moves you use, the more points you get.

Input

The first line of input contains the number of test cases c (c<=200). Then c test cases follow, each of them begins with a line with a single integer n (3<=n<=10) in it. The next n lines describe the initial state of the board - the i-th line consists of exactly n integers describing the i-th row. The position of the hole is indicated by 0.

Output

For each test case output one line - the found sequence of moves. Write 'D' to move the hole down, 'U' to move it up, 'R' to move it right and 'L' to move it left. You shouldn't use more than 10000 moves. All moves should be valid (so for example don't try to move the hole up when it is in the first row).

Scoring

Your program will receive n^3/(m+1) points for each test case where m is the number of moves.

Example

Input:
2

4
1   2  7  3
5   6  0  4
9  10 11  8
13 14 15  12

3
0 1 2
4 5 3
7 8 6

Output:
URDDD
RRDD

hide comments
damocris: 2024-05-15 12:48:45

it seems we can only the IDA* algorithm to do the searching due to the limited memory

achung0147: 2018-07-26 04:07:11

how can I solve this ? I have no idea ! Someone can help me ?

abrunoaa: 2018-05-22 20:17:57

any hints????
which algorithm use??

kiner_shah: 2015-09-21 17:41:30

A classic branch and bound problem! Good question!

Shivam Bhardwaj: 2014-06-05 15:56:51

If user do an invalid move den it should be count to moves or not..??

Thiyagu: 2012-07-03 17:16:01

hi frineds..
can u give me some more test cases for this problem(high complex test case) plz...


Added by:gawry
Date:2004-07-27
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET