/*

RUTINA BKTR  ( construieste solutia unui enunt utilizand un vector manevrat
                            cu strategie stiva )

-top=1
- initializeza  stiva S la varf top=1
- atata timp cat stiva nu este vida executa
            - cauta in multimea de candidati ai locului curent un prim succesor admisibil
            - daca am gasit succesor admisibil atunci executa
                                                                - daca am solutie atunci executa
                                                                                                        - tiparire
                                                                                                        sf_executa
                                                                                              altfel executa
                                                                                                         - top=top+1
                                                                                                         - initializeza  stiva S la varf top=1
                                                                                                        sf_executa
                                                                               sf_executa
                                                                altfel  executa
                                                                             -top=top-1
                                                                        sf_executa
                                                      sf_executa atata timp

rutina pentru a fi  pusa in practica trebuie sa utilizeze intrumentele :

1) initializeaza S la varf curent
    functia init(S,top) depune stiva o valoare de la care prin incrementare ajung
    pe prim candidat din multimea arondatilor locului

2) succesor la varf curent pe stiva
     functia succ(S,top) depisteaza existenta unui succesor in multimea
     de candidati arondati locului curent . In caz afirmativ functie succ(S,top)
     si depune acel candidat iar ca rezultat intoarce 1 TRUE
     in caz negativ intoare 0 FALSE

3) validarea la varf curent pe stiva
    functia succ(S,top) intoarece 1 TRUE sau 0 FALSE dupa cum candidatul
    depistat si depus de succ(S,top) este sau nu admisibil in baza unor conditii
    din anunt

4) solutie
   functia solutie (S,top) intoarece 1 TRUE sau 0 FALSE dupa cum
   pe stiva am sau solutie

5) tipar
   functia tipar (S,top) tipareste solutia adica continutul stivei din baza pana in varf

===============================================
Aplicatie :
Problema P(n)  problema generarii permutarilor unei multimi cu n componente
( prezentarii tuturor modurilor de aranjare a elementelor ei )

n=3 M={1,2,3}
Solutii  :
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Sunt intrunite conditiile unui enunt incadrabil in clasa problemelor BKTR
1) Se cer toate solutiile
2) Orice solutie este reprezentabila sub forma de forma de vector
3) Pentru toate locurile din solutie sunt multimi de candidati
    A1={1,2,3}
    A2={1,2,3}
    A3={1,2,3}

*/
#include<iostream>
using namespace std;
int n;
int S[100];
int top;

int init(int stiva[],int top)
{ stiva[top]=0;}

int succ(int stiva[],int top)
{ if (stiva[top]<n)  {
                            stiva[top]=stiva[top]+1;
                            return 1;
                            }
  return 0;}

int valid(int stiva[],int top)
{ if (top==1)   return 1;
   int i;
   i=1;
   while (i<top)
   { if (stiva[i]==stiva[top]) return 0;
      i=i+1;}
  return 1;}

int solutie(int stiva[],int top)
{ if (top==n) return 1;
   return 0;}

int tipar(int stiva[],int top)
{ cout<<endl;
   int i;
   i=1;
   while (i<=top)
   { cout<<stiva[i]<<" ";
      i=i+1;}
  return 1;}

int bktr()
{
top=1;
init(S,top);
while (top>=1)
     {
        int am;
       int este;
       do {
           am=succ(S,top);
           este=valid(S,top);
            } while(!((am&&este)||(!am)));
        if (am) {
            if (solutie(S,top)) { tipar(S,top);}
                        else {
                              top=top+1;
                              init(S,top);
                              }
                    }
                 else {
                          top=top-1;
                         }
        }
}

int main()
{  cout<<"n=";cin>>n;
    bktr();
}