PROBLEMA 21:            PUZZLE
DEADLINE:               Luni, 7 iunie 1999
TIMP DE IMPLEMENTARE:   Mare (4-5 ore)
DOMENIU:                Gasirea unei strategii de joc
PUNCTAJ:                60 dexteri

Se da un puzzle binecunoscut, de 4x4 spatii. In 15 din aceste spatii se
afla numerele de la 1 la 15, iar al 16-lea este gol. Se mai da o
configuratie initiala a acestui puzzle. Se cere ca efectuand mutari, sa se
ajunga in configuratia:

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

Exista patru tipuri de mutari, codificate prin literele N, S, E si V.
Aceste litere indica directia pe care se deplaseaza patratelul gol.
Nu se cere rezolvarea puzzle-ului intr-un numar minim de mutari, dar
solutia nu are voie sa depaseasca 50000 mutari.

Cei care nu au la indemana un asemenea joc, il pot folosi pe cel virtual
din Microsoft FoxPro (meniul Help, pare-mi-se).

INTRAREA: Fisierul PUZZLE.IN contine 4 linii a cate 4 numere cuprinse intre
0 si 15. 0 indica patratelul gol.

IESIREA: Fisierul PUZZLE.OUT va contine o singura linie pe care se vor afla
caractere din multimea {N, S, E, V}. Iesirea nu va contine spatii sau
caractere newline.

EXEMPLU:
PUZZLE.IN                       PUZZLE.OUT (o solutie posibila)
  1  2  3  4                    VSE
  5  6  7  8
  9 10 12  0
 13 14 11 15

TIMP DE EXECUTIE: 1 secunda/test.