Enunt: b6m12mk
Fiind data o harta nu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari de frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.
Rezolvare:
Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5:

O solutie a acestei probleme este urmatoarea:
· tara 1 -; culoarea 1
· tara 2 -; culoarea 2
· tara 3 -; culoarea 1;
· tara 4 -; culoarea 3;
· tara 5 -; culoarea 4;
Harta este furnizata programului cu ajutorul unei matrice An,n
1, daca tara i se invecineaza cu tara j;
A(i,j) =
0 , altfel
Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar staki culoarea atasata tarii k. Stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4.

Rezolvare PASCAL:

Program colorarea_hartilor;
Type stiva = array a1…100i of integer; var st : stiva; i, j, n, k : integer; as, ev : boolean; a: array a1..20,1..20i of integer;

procedure init(k:integer; var st:stiva); begin staki:=0; end;

procedure succesor(var as:boolean; var st:stiva; k:integer); begin if staki < 4 then begin staki:=staki+1; as:true end else as:false end;

procedure valid (var ev:boolean; st:stiva; k:integer); var i:integer; begin ev:true; for i:=1 to k-1 do if (staii=staki) and (aai,ki=1) then ev:false end;

function solutie(k:integer):integer; begin solutie:=(k=n); end;

procedure tipar; var i:integer; begin for i:= 1 to n do

writeln(’Tara =’, i,’; culoarea=’,staii);
writeln(’===================’); end;

begin
write(’Numarul de tari = ’); readln(n); for i:= 1 to n do for j:=1 to i-1 do begin
write(’aa’,i,’,’,j,’i=’); readln(aai,ji) end; k:=1; init(k,st);
while k>0 do begin repeat succesor(as,st,k); if as then valid(ev,st,k); until (not as) or (as and ev); if as then if solutie (k) then tipar else begin k:=k+1; init(k,st) end else k:=k-1 end end.