Problema Colorarii Hartilor Cu Metoda Backtracking

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.

Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5: tara 5 culoarea 4; Harta este furnizata programului cu ajutorul unei matrice An, n 0, altfel Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar st[k] 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 [1 100] of integer; var st: stiva; i, j, n, k: integer; as, ev: boolean; a: array [1. 20, 1. 20] of integer; procedure init (k: integer; var st: stiva); begin st[k]: =0; end; procedure succesor (var as: boolean; var st: stiva; k: integer); begin if st[k] < 4 then begin st[k]: =st[k]+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 (st[i]=st[k]) and (a[i, k]=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=, st[i]); writeln; end; begin write (Numarul de tari =); readln (n); for i: = 1 to n do for j: =1 to i-1 do begin write (a[, i, , , j,]=); readln (a[i, j]) 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.

...