IALab5

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#define N 40

using namespace std;
int *config;//configuratie = vector ce reprezinta o permutare adica o aranindexare a damelor


void init() {
	int M[N];
	int lungime_M = N;//lungime_M a vectorului M
	int i;//indicele de configuratie
	for (int i = 0; i < N; i++) {
		M[i] = i + 1;
	}
	i = 0;
	while (lungime_M > 0) {
		int g = rand() % lungime_M;
		config[i++] = M[g];
		for (int index = g; index < lungime_M - 1; index++) {
			M[index] = M[index + 1];//scoate elementul M[g] din lista
		}
		lungime_M--;
	}

}
int Evaluare(int *c) {
	int erori = 0; //nr de atacuri pe diagonala
	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (abs(config[i]) - config[j] == abs(i - j)) {
				erori++;
			}
		}
	}
	return erori;
}

int *Perturbare(int *c) {
	int x, y;
	x = rand() % N;
	y = rand() % N;
	while (x == y) {
		y = rand() % N;
	}
	int temp = c[x];
	c[x] = c[y];
	c[y] = temp;

	return c;
}

void Afisare(int *c) {
	cout << "\nAfisare:\n";
	for (int i = 0; i < N; i++) {
		cout << c[i] << " ";
	}
}

void HillClimbing() {
	init();
	cout << "init ";
	Afisare(config);
	cout << "\nevaluarea configuratiei este " << Evaluare(config);
	for (int i = 0; i <1000; i++) {
		int *config1 = Perturbare(config);
		if (Evaluare(config1)<Evaluare(config)) {
			config = config1;
		}
		if (Evaluare(config) == 0) {
			break;
		}
	}
}

void HillClimbingRestartAleator() {
	init();
	int nr_pasi=0;//umarul pasilor care nu duc la o solutie mai buna
	cout << "init ";
	Afisare(config);
	cout << "\nevaluarea configuratiei este " << Evaluare(config);
	for (int i = 0; i <10000; i++) {
		if (nr_pasi < 10) {


			int *config1 = Perturbare(config);
			if (Evaluare(config1) < Evaluare(config)) {
				config = config1;

			}
			else {
				nr_pasi++;

			}
		}
		else {
			init();
			nr_pasi = 0;
		}
		if (Evaluare(config) == 0) {
			break;
		}
	}
}

void main() {
	int *c;
	c = new int[N];
	config = new int[N];
	time_t t;
	srand((unsigned)(time(&t)));
	/*init();

	for (int i = 0; i < N; i++) {
	cout << config[i] << " ";
	}
	cout << "\nevaluarea configuratiei este " << Evaluare(config);
	//cout << "\npertubarea configuratiei este " << *Perturbare(config);
	c = Perturbare(config);
	cout <<"\nPasul schimbat "<< endl

	for (int i = 0;i < N;i++) {
	cout << c[i]<<" ";
	}*/

	HillClimbingRestartAleator();
	Afisare(config);
	cout << "\nevaluarea configuratiei este " << Evaluare(config);
	_getch();
}