Regele Arthur (Timiosara - pregatire, dec. 1995)

	La curtea regelui Arthur s-au adunat n cavaleri si fiecare dintre ei 
are printre cei prezenti cel putin un dusman. Verificati daca Merlin, 
consilierul regelui, poate sa-i aseze pe cavaleri la o masa rotunda astfel 
incat niciunul dintre ei sa nu stea alaturi de vreun dusman al sau.
	Sa se gaseasca toate solutiile posibile pentru un n dat.
	Un set de date din fisierul de intrare in08.txt contine pe prima 
linie numarul n iar pe fiecare din urmatoarele n linii dusmanii cavalerului
respectiv (linia i contine dusmanii cavalerului i). Seturile de date de 
intrare sunt despartite prin cate un rand liber.
	In fisierul de iesire, ou08.txt, corespunzator unui set de date de 
intrare se afiseaza mesajul DA sau NU dupa cum cavalerii pot sau nu sa fie 
asezati; daca DA se afiseaza toate modalitatile de aranjare circulara, 
fiecare pe cate o linie.
Exemplu:
Pentru setul de date de intrare:
6
3 6
5
1 6
5
2 4
1 2
iesirea este:
DA
1 2 3 4 6 5 
1 2 3 5 6 4 
1 4 6 5 3 2 
-----------------------------------------------
Rezolvare: (Mihai Stroe)
  Se foloseste metoda backtracking;se genereaza permutari,elementul
  de pe nivelul k al stivei fiind valid daca nu este 'dusman' al
  elementului anterior.Pe primul nivel este intotdeauna 1.Daca 1 nu
  este 'dusman' al elementului de pe nivelul n,se va scrie solutia
  obtinuta.

var a:array[1..100,1..100]of byte;
    fi,fo:text;
    i,j,k,l,m,n:integer;
    st:array[1..100]of byte;
    b:boolean;

function valid:boolean;
begin
  valid:=true;
  if a[st[k-1],st[k]]=1 then valid:=false;
  for i:=1 to k-1 do
      if st[i]=st[k] then valid:=false;

end;



function solutie:boolean;
begin
  if a[st[n],1]=1 then solutie:=false
                  else solutie:=true;

end;


procedure tipar;
begin
  if not b then writeln(fo,'Da');
  for i:=1 to n do
      write(fo,st[i],' ');
  writeln(fo);
  b:=true;
end;


procedure solve;
begin
  st[1]:=1;
  k:=2;
  b:=false;
  while k>1 do
    begin
      repeat inc(st[k]);until(st[k]>n)or((st[k]<=n)and valid);
      if st[k]>n then begin st[k]:=0;dec(k);end
                 else begin
                        if k=n then if solutie then tipar;
                        if k<>n then inc(k);
                      end;
    end;
  if b=false then writeln(fo,'Nu');
  writeln(fo);
end;

procedure readdata;
begin
  assign(fi,'in08.txt');
  assign(fo,'ou08.txt');
  reset(fi);
  rewrite(fo);
  while not eof(fi) do
    begin
      fillchar(a,sizeof(a),0);
      readln(fi,n);
      for i:=1 to n do
          begin
            while not eoln(fi) do
              begin
                read(fi,j);
                a[i,j]:=1;
                a[j,i]:=1;
              end;
            readln(fi);
          end;
      readln(fi);
      solve;
    end;
  close(fi);
  close(fo);
end;



begin
  readdata;
end.
