/* Problema colorarii unei harti.
     Fiind data o harta cu n tari, se cer toate solutiile de colorare
     a hartii, utilizand cel mult 4 culori, a.i. 2 tari cu frontiera comuna
     sa fie colorate diferit
     Harta este furnizata programului cu ajutorul unei matrici A(n,n)
     definita astfel:
       A[i,j]=1, daca tara i are frontiera comuna cu tara j  si
       A[i,j]=0, in caz contrar
    Matricea A este simetrica
    - stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4
    - fiecare nivel k simbolizeaza tara k
		- st[k] semnifica culoarea tarii k
	*/
#include <stdio.h>
#include <conio.h>

int st[10],a[10][10],n,k,nr;
void Init()
 {
st[k]=0;
 }
int Am_Succesor()
 {
if(st[k]<n)
		{
    	st[k]++;
      return 1;
    }
    else return 0;
 }
int Valid()
 {
 for(int i=1;i<=k-1;i++)
 		if(st[i]==st[k] && a[i][k]==1) return 0;
 return 1;
 }
int Solutie()
 { return k==n;}
void Tipar()
 {
 for(int i=1;i<=n;i++) printf("tara %d are culoarea %d \n",i,st[i]);
 nr++;
 }
void back()
 {
 int As;
 k=1;
 Init();
 while (k>0)
 	{ do  {
				} while ((As=Am_Succesor()) && !Valid());
  	if (As)
    	if (Solutie()) Tipar();
      	else {
        			k++;
              Init();
             }
     else k--;
   }
 }
 void main()
{
clrscr();
printf("nr tari=");
scanf("%d",&n);
nr=0;
// matricea A reprezentand tarile cu vecinii se va completa
// tinand cont ca este simetrica
for (int i=1;i<=n;i++)
	for (int j=1;j<=i-1;j++)
		{ printf("a[%d,%d]=",i,j);
		  scanf("%d",&a[i][j]);
      a[j][i]=a[i][j];
    }
back();
printf("nr. solutiilor=%d",nr);
getch();
}