mateforum.ro

Un prieten are urmatorul joc pe mobil, si m-a rugat sa ma gandesc cum poate sa ajunga la punctajul maxim. Iata jocul:


Avem o tabla \( 5\times 5 \) impartita in 25 patrate unitate. Doua patrate se numesc vecine daca au o latura in comun.

Avem la dispozitie 4 culori: rosu(R), galben(G), albastru(A), verde (V), si initial toate patratele sunt albastre.
O mutare inseamna sa schimbam culoarea unui patratel cu una diferita de a sa in felul urmator:
-un patrat poate fi colorat cu R daca are un vecin A;
-un patrat poate fi colorat cu V daca are un vecin A si unul R;
-un patrat poate fi colorat cu G daca are un vecin A, unul R si unul V.
Culorile au punctajele urmatoare:
A: 1 punct;
R: 2 puncte;
V: 3 puncte;
G: 4 puncte;

Care este punctajul maxim posibil care poate fi atins folosind doar mutarile mentionate mai sus? (Am gasit rezultatul si este surprinzator de mare... )



Pentru cunoscatori, ar fi interesant de implementat un astfel de joc intr-un limbaj de programare...

Nu am reusit sa implementez pe calculator, si cred ca e posibil sa nu prea se poata, cel putin nu prin "forta bruta". Optimul prin "forta bruta", implica generarea tuturor posibilitatilor. Backtrackingul ar intra in cicluri infinte, asa k nu este acceptabil.
O prima varianta, ar fi construirea unui graf, care sa contina toate configuratiile tablei de joc, cu legatura intre doua noduri daca se poate ajunge din unul in altul printr-o singura mutare. Apoi s-ar gasi cel mai mare nod care este in aceeasi componenta conexa cu cel initial.
Din pacate, avem \( 4^{25} \) noduri, ceea ce ar ocupa cam multa memorie, si mai ales, ar lua un timp de executie f mare.
O alta varianta ar fi folosirea metodei "Branch and Bound", dar cum se cer toate posibilitatile, ar genera si ea un timp f mare de executie si un consum insemnat de memorie.
Are cineva alte idei?