Mai jos puteti gasi programul „regine.cpp”, care rezolva problema asezarii celor n regine pe o tabla de sah cu nxn patratele, asa cum l-am scris la curs. Am folosit medoda backtracking in varianta iterativa (repetitiva). L-am scris si testat in Dev C++.
#include <iostream> using namespace std; int x[10]; int n; int k; int nrsolutii; void scrie_solutia() { nrsolutii++; cout<<"\n\nSolutia nr. "<<nrsolutii<<" este:\n"; int i,j; cout<<"-"; for (i=1; i<=n; i++) cout<<"--"; cout<<"-\n"; for (i=1; i<=n; i++) { cout<<"|"; for (j=1; j<=n; j++) if (x[j]==i) cout<<"&&"; else cout<<" "; cout<<"|\n"; } cout<<"-"; for (i=1; i<=n; i++) cout<<"--"; cout<<"-\n"; system("PAUSE"); } void scrie_solutia_altfel() { nrsolutii++; cout<<"\n\nSolutia nr. "<<nrsolutii<<" este:\n"; for (int i=1; i<=n; i++) { cout<<" - asezam regina nr. "<<i; cout<<" pe coloana "<<i<<" si linia "<<x[i]<<"\n"; } system("PAUSE"); } int continuare(int k) { for (int i=1; i<k; i++) if (x[i]==x[k] || k-i == abs(x[k]-x[i])) return 0; return 1; } int main() { int i; int bine; cout<<"\n\nProblema celor n regine\n\n"; cout<<"Dati nr. de regine: "; cin>>n; k=1; x[k]=0; while (k>0) { bine=0; while (x[k]<n && !bine) { x[k]=x[k]+1; if (continuare(k)) bine=1; } if (bine) if (k==n) scrie_solutia(); else x[++k]=0; else k--; } return 0; }