<PREV Problem:
NEXT>
Solved by 65 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

15-Puzzle

Time limit = 5 second(s)

Memory limit = 33000 Kb

Solve 15-puzzle for less than 1000 moves.

1234
5678
9101112
131415 

Fig.1: Target position.

a1a2a3a4
a5a6a7a8
a9a10a11a12
a13a14a15a16

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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.198.246.116