Programarea calculatoarelor 2 - Laborator 13
Se da considera o tabla de joc NxN pe care sunt dispuse piese cu numerele
de la 1 la N^2 - 1, ramanand un patrat liber. Printr-o mutare, o piesa
adiacenta patratului liber poate fi lua locul acestuia, lasand liber
locul pe care se afla anterior. Sa se determine daca exista o secventa
de mutari prin care piesele se pot aranja pe linii si coloane in ordine
crescatoare, incepand cu patratul liber in coltul stanga sus.
Configuratia initiala se da cu cate N numere pe cate o linie, spatiul
liber fiind indicat prin *. Rezolvati problema pentru N = 3.
Indicatii de rezolvare
Cautati sa ajungeti la configuratia ordonata dorita prin mutari succesive.
Pentru aceasta puteti implementa o cautare cu revenire in spatiul starilor
(configuratiilor tablei de joc).
Stabiliti o codificare a configuratiilor, de exemplu cu numere consecutive
(sunt (N^2)! configuratii potentiale, adica numarul de permutari de N^2 piese).
Folositi un tablou de fanioane boolene (eventual codificate pe biti)
pentru a retine configuratiile atinse si a nu le repeta, intrand in cicluri.
Marius Minea
Last modified: Wed Jan 14 00:44:21 EET 2004