“Evolyutsion algoritmlar”

Chiqish
[2 4 1 3 ][3 1 4 2 ]
Ushbu maqola Sahil Chhabra tomonidan taqdim etilgan . Agar sizga GeeksforGeeks yoqsa va o'z hissangizni qo'shmoqchi bo'lsangiz, write.geeksforgeeks.org dan foydalanib maqola yozishingiz yoki maqolangizni [e-mail] manziliga yuborishingiz mumkin. Maqolangizni GeeksforGeeks bosh sahifasida ko'ring va boshqa Geeksga yordam bering. 
Takroriy orqaga qaytish yechimi:
Maqolaning ushbu qismida rekursiyasiz iterativ orqaga qaytish yechimi taqdim etiladi. Kod asosan ikkita ichki halqa va stekdan qirolichalarning taxtadagi o'rnini kuzatib borish va orqaga qaytish uchun ushbu stekdan foydalanadi.
Algoritm:
n: qo'shiladigan qatorlar, ustunlar va malikalar soni.
1- Doskadagi qutiga mos keladigan massivdagi har bir katak bilan doskani ifodalash uchun 2D-massiv yarating
2- Qirolichalarning pozitsiyalarini kuzatib borish uchun stek yarating, bu erda tepadagi malika har doim eng oxirgi qo'shilgan malika bo'ladi.
3- j = 1 hisoblagichni o'rnating, bu keyingi bosqichlarda ustunlar bo'ylab aylanish uchun ishlatiladi.
4- i = 1 ----> i = n dan qatorlar orqali tashqi halqa hosil qiling
5- j ----> j = n dan ustunlar orqali ichki halqa hosil qiling.
6- halqalarning ichki tanasida joriy hujayra malika qo'shish uchun yaroqliligini tekshiring
amal qilsa
- malikani taxtaga qo'shing
- stekga malika o'rnini qo'shing
- ichki halqani sindirish
7- ichki halqani tugatish yoki sindirishdan keyin
a) j = 1 ni o'rnating (shuning uchun sukut bo'yicha keyingi iteratsiyada j = 1 dan ustunlar bo'ylab aylanishni boshlash kerak)
b) joriy qatorga malika joylashtirilgan yoki yo'qligini bilish uchun stekning o'lchami qator soniga tengligini tekshiring
agar malika qo'yilmagan bo'lsa:
8- Quyidagi amallarni bajarib, oxirgi qo'shilgan malikaga qaytib boring:
a) oxirgi qo'shilgan qirolichaning pozitsiyasiga stekning tepasidan kirish
b) so'nggi qo'shilgan malikani doskadan o'chirish
c) i o'rnating (taxta qatorlari uchun hisoblagich) = oxirgi qo'shilgan malikaning qatori
d) j to'plami = oxirgi qo'shilgan malika ustuni + 1
9- agar i == n bo'lsa, endi barcha qatorlar tashrif buyurilgan va malika bilan to'ldirilgan degan ma'noni anglatadi
a) chop etish yechimi
b) stek bo'sh bo'lguncha boshqa echimlarni sinab ko'rish uchun yana 8-bosqichni bajaring



Quyidagi Amalga oshirishga ko'ra, yechimlar nol va birlarning n*n matritsasi sifatida chop etiladi, bu erda hujayralar = 1 malikalarni ifodalaydi. 
Quyida yuqoridagi algoritmni amalga oshirish ko'rsatilgan
#include
#include
#include
#include
 
using namespace std;
using vvi = vector >;
using vi = vector;
void print(vvi board)
{
 
int count = 0;
for (auto& row : board) {
for (auto& el : row)
if (el == 1)
count++;
 
}
// Not valid solution
if (count != board.size())
return;
 
// Print the matrix
for (auto& row : board) {
for (auto& el : row)
cout << el << " ";
cout << '\n';
}
}
bool validate(vvi board, int i, int j)
{
// validate rows
for (int c = 1; c <= j; c++)
if (board[i - 1] == 1)
return false;
// validate columns
for (int r = 1; r <= i; r++)
if (board[r - 1][j - 1] == 1)
return false;
// validate diagonals to right up corner
int c = j;
int r = i;
while (c != 0 and r != 0) {
if (board[r - 1] == 1)
return false;
r--;
c--;
}
// validate diagonals to left up corner
c = j;
r = i;
while (c != board.size() + 1 and r != 0) {
if (board[r - 1] == 1)
return false;
r--;
c++;
}
return true;
}
 
void n_queen(int n)
{
vvi board(n, vi(n));
stack
>
queens_positions; // stores positions of added
// queens
int j = 1;
for (int i = 1; i <= board.size(); i++) {
for (; j <= board.size(); j++) {
if (validate(board, i,
j)) { // check validity of cell
// before adding the queen
board[i - 1][j - 1] = 1;
queens_positions.push(make_pair(i, j));
break;
}
}
j = 1;
if (queens_positions.size()
!= i) { // checks if a queen was placed in the
// current row
 
if (!queens_positions.empty()) {
pair Q_last
= queens_positions
.top(); // position of last added
// queen
queens_positions.pop();
 
// backtracking
board[Q_last.first - 1][Q_last.second - 1]
= 0; // nulling the last added queen
i = Q_last.first
- 1; // going back to the row of the
// last added queen
j = Q_last.second
+ 1; // going back to the column of the
// last added queen + 1
}
}
 
if (i == board.size()) {
print(board);
cout << '\n';
if (!queens_positions.empty()) {
pair Q_last
= queens_positions
.top(); // position of last added
// queen
queens_positions.pop();
 
// backtracking
board[Q_last.first - 1][Q_last.second - 1]
= 0; // nulling the last added queen
i = Q_last.first
- 1; // going back to the row of the
// last added queen
j = Q_last.second
+ 1; // going back to the column of the
// last added queen + 1
}
}
}
}
 
int main() { n_queen(4); }
Chiqish
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0