Probleme2
Sa se aseze n ture pe o tabla de sah cu n linii si n coloane astfel incat sa nu se poata ataca una pe alta.
2 ture se pot ataca daca se gasesec pe aceiasi linie sau aceiasi coloana.
Liniile tablei de sah sunt numerotate cu numere 1...n iar coloanele cu numere 1...n.
x[k] reprezinta coloana ocupata pe linia k (patratica pe care este asata o tura pe linia k) - x[k] are valori intre 1...n. Deci, min=1 si max=n.
Liniile nu au cum sa se repete deoarece, ele vor fi luate in ordine de catre algorimul backtraking (k=1...n).
Problema turelor se reduce astfel la problema generarii permutarilor, insa, vom afisa de data asta solutia sub forma unei table de sah si vom numerota solutiile. Algoritmul nu este gresit daca afisarea se face ca la permutari!
#include<fstream.h>
ofstream f("ture.txt");
int x[50],k,valid,n,m,nr;
void citire()
{
cout<<"n=";cin>>n;/*citim numarul de linii si de coloane*/
}
void posibil(int k,int &valid)
{
valid=1;
for(int i=1;i<=k-1;i++)
if(x[i]==x[k]) valid=0; /*verificam daca 2 ture se gasesc pe aceiasi coloana; nu e nevoie sa se verifice daca se gasesc pe aceiasi linie deoarece liniile sunt reprezentate de variabila k=1...n*/
}
int solutie(int k)
{ /*s-a ajuns la o solutie daca s-au depus cele n ture pe tabla de sah*/
if(k==n)return 1;
else return 0;
}
void afisare(int k)
{/*afisam numarul de solutii si "oglinda" tablei de sah*/
nr++;
f<<"solutia "<<nr<<endl;
for(int i=1;i<=k;i++){
for (int j=1;j<=k;j++)
if (x[i]==j)f<<"T"<<" "; /*daca pe linia i se gaseste o tura (x[i] e diferit de 0 si este egal cu numarul coloanei pe care se gaseste tura*/
else f<<"*"<<" ";
f<<endl;}
f<<endl;
}
void back()
{
k=1;/*prima linie*/
x[k]=0;/*punem tura pe marginea tablei de sah - initializam pe x[k]=1-min*/
while(k>0)
{
valid=0;
while(!valid && x[k]<n)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++; /*trecem la ocuparea urmatoarei linii*/
x[k]=0; /*punem tura pe marginea tablei de sah. x[k]=1-min*/
}
}
}
void main()
{
citire();
nr=0;
back();
f.close();
}
Sa se aseze n nebuni pe o tabla de sah cu n linii si n coloane astfel incat sa nu se poata ataca unul pe altul.
La fel ca la problema turelor (problema precedenta) k va reprezenta numarul liniei pe tabla de sah iar x[k] numarul coloanei ocupata de piesa pe linia k.
Numarul liniilor este cuprins intre 1...n iar numarul coloanelor este cuprins intre 1...n, prin urmare valoarea minima pentru x[k] este 1 iar valoarea maxima este n.
Doi nebuni nu se pot ataca daca si numai daca ei nu se afla pe aceiasi diagonal.
Fie i=1...k-1, un nebun se poate pune pe linia k in pozitia x[k] daca si numai daca abs(x[i]-x[k])<>abs(i-k). Aceasta formula se poate obtine realizand sistemul de coordonate XOY si schitand in sistem, de exemplu, pe Y i si k iar pe X pe x[k] si x[i] si dezbatand cele 4 cazuri rezultate.
O solutie arata sub forma urmatoare:
N * * * *
N * * * *
* * * N *
N * * * *
* * N * *
#include<fstream.h>
#include<math.h>
ofstream f("nebun.txt");
int x[50],k,valid,n,m,nr;
void citire()
{
cout<<"n=";cin>>n;/*citim numarul de linii si de coloane de pe tabla de sah = numarul de nebuni care trebuie depusi*/
}
void posibil(int k,int &valid)
{
valid=1;
for(int i=1;i<=k-1;i++)
if(abs(x[i]-x[k])==abs(i-k)) valid=0; /*daca nebunul de pe linia k se afla pe aceiasi diagonala cu nebunul de pe linia i pozitia x[k] nu e corecta*/
}
int solutie(int k)
{
if(k==n)return 1; /*am ajuns la o solutie daca s-au depus toti cei n nebuni*/
else return 0;
}
void afisare(int k) /*afisam numarul solutiei si solutia sub forma de tabla de sah (matrice)*/
{nr++;
f<<"solutia "<<nr<<endl;
for(int i=1;i<=k;i++){
for (int j=1;j<=k;j++)
if (x[i]==j)f<<"N"<<" ";
else f<<"*"<<" ";
f<<endl;}
f<<endl;
}
void back()
{
k=1;
x[k]=0;
while(k>0)
{
valid=0;
while(!valid && x[k]<n)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=0;
}
}
}
void main()
{
citire();
nr=0;
back();
f.close();
}
Sa se aseze n dame (regine) pe o tabla de sah cu n linii si n coloane astfel incat sa nu se poata ataca una pe alta.
Doua dame nu se pot ataca una pe alta daca nu se afla pe aceiasi linie, aceiasi coloana sau aceiasi diagonala.
Problema damelor este o combinatie intre problema turelor (prima problema de pe pagina) si problema nebunilor (a doua problema de pe site).
Liniile sunt ocupate in ordine de la 1...n, prin urmare nu se pot ocupa.
Doua regine sunt pe aceiasi coloana daca exita un i=1...k-1 astfel incat x[k]=x[i].
Doua regine sunt pe aceaisi diagonala daca exista i=1...k-1 astfel incat abs(x[k]-x[i])=abs(k-i).
Valoarea minima pentru x[k] este 1 iar voaloarea maxima este n (x[k] reprezinta coloana ocupata de o regina pe linia k).
* * * D * *
D * * * * *
* * * * D *
* D * * * *
* * * * * D
* * D * * *
#include<fstream.h>
#include<math.h>
ofstream f("dame.txt");
int x[50],k,valid,n,m,nr;
void citire()
{
cout<<"n=";cin>>n;/*se citeste numarul de linii = numarul de coloane=numarul de dame care trebuiesc depuse pe tabla de sah*/
}
void posibil(int k,int &valid)
{
valid=1;
for(int i=1;i<=k-1;i++)
if(abs(x[i]-x[k])==abs(i-k)||(x[i]==x[k])) valid=0; /*doua dame nu se pot afla pe aceiasi linie (k), aceiasi coloana (x[k]) sau aceiasi diagonala*/
}
int solutie(int k)
{
if(k==n)return 1;/*daca s-au depus n dame s-a ajuns la solutie*/
else return 0;
}
void afisare(int k)/*afisam solutia sub forma de matrice*/
{nr++;
f<<"solutia "<<nr<<endl;
for(int i=1;i<=k;i++){
for (int j=1;j<=k;j++)
if (x[i]==j)f<<"D"<<" ";
else f<<"*"<<" ";
f<<endl;}
f<<endl;
}
void back()
{
k=1;
x[k]=0;
while(k>0)
{
valid=0;
while(!valid && x[k]<n)
{
x[k]=x[k]+1;
posibil(k,valid);
}
if(!valid)k--;
else if(solutie(k)) afisare(k);
else {
k++;
x[k]=0;
}
}
}
void main()
{
citire();
nr=0;
back();
f.close();
}
