Solved by 65 users: ...
UserDateAttemptTimeCMSC
Rizvanov`29 jan 2008`C++400.02570
qinhanlei`06 may 2009`C++500.37621
ethanhunt`17 aug 2007`C++1800.55642
Philip_PV`06 jul 2008`C++1000.28655
zard`25 dec 2009`C++3102.68719
checkil`23 nov 2010`C++100.37740
Olega.90`23 nov 2010`C++1400.37740
oleg.dudrov`06 dec 2010`C++600.38740
zard`25 dec 2009`C++2900.38740
ethanhunt`17 aug 2007`C++1300.51754
pmnox`04 feb 2009`C++3500.04838
UdH-WiNGeR`23 feb 2009`Java2400.35889
 C++ 44 FPC 10 Java 8 Kylix 5 C 2
` >  >  >  >  >  >  >  >  >  > `

## 15-Puzzle

Time limit = 5 second(s)

Memory limit = 33000 Kb

Solve 15-puzzle for less than 1000 moves.

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

Fig.1: Target position.

 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16

Fig.2: Initial position. ai = 0 for empty cell.

Input. Line with a1, a2, ..., a16 numbers.

Number 0 corresponds to empty cell.

Output. First line should contain YES (if solvable) or NO (if not). If YES, then second line should contain string describing moves. Moves are denoted by letters u, d, l, r (up, down, left and right). Do NOT place spaces between letters.

 Input#1```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ``` Output#1```YES ```
 Input#2```1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12 ``` Output#2```YES rd ```

Author:
Folklor, description and tests by Eugeny Antyshev.
3 May 2006

 © acm.mipt DevGroupThe page was generated in 190ms