“Evolyutsion algoritmlar”

Vaqt murakkabligi: O(N!)
Yordamchi fazo: O(N2)
Orqaga qaytish algoritmi 2-usul:
Maqsad malikalarni eng yuqori qatordan boshlab birin-ketin turli qatorlarga joylashtirishdir. Qirolichani ketma-ket joylashtirganda, biz allaqachon joylashtirilgan malika bilan to'qnashuvlarni tekshiramiz. Joriy ustunda, agar biz to'qnashuv bo'lmagan qatorni topsak, biz ushbu qator va ustunni yechimning bir qismi sifatida belgilaymiz. Agar biz to'qnashuvlar tufayli bunday qatorni topmasak, biz orqaga qaytamiz va yolg'onni qaytaramiz.
2-usul:
0) Doska yasang, barcha yechim holatlarini to'plash uchun joy ajrating.
1) Eng yuqori qatordan boshlang.
2) Doska holatini va joriy satr raqamini
parametr sifatida qabul qiluvchi rekursiv funksiya yarating.
3) Qirolichani xavfsiz joyga to'ldiring va keyingi rekursiv
qo'ng'iroqqa o'tish uchun ushbu taxta holatidan foydalaning, joriy qatorga 1 qo'shing. Qo'ng'iroqni amalga oshirgandan so'ng, boshqaruv kengashi holatini qaytaring.
a) Xavfsiz funksiya joriy ustunni, chap yuqori diagonalni va o'ng yuqori diagonalni tekshiradi.
b) Agar qirolicha mavjud bo'lmasa, fill else qaytaring false va bu holatni o'rganishni to'xtating 
va keyingi mumkin bo'lgan yechim holatiga qayting
4) Joriy qator chegaradan chiqmaguncha funktsiyani chaqirishni davom eting.
5) Agar joriy qator doskadagi qatorlar soniga yetsa, doska to'ldiriladi.
6) Davlatni saqlash va qaytarish.
2-usul bo'yicha Backtracking yechimini amalga oshirish:
#include
using namespace std;
// store all the possible answers
vector > answer;
// print the board
void print_board()
{
for (auto& str : answer[1]) {
for (auto& letter : str)
cout << letter << " ";
cout << endl;
}
return;
}
// we need to check in three directions
// 1. in the same column above the current position
// 2. in the left top diagonal from the given cell
// 3. in the right top diagonal from the given cell
int safe(int row, int col, vector& board)
{
for (int i = 0; i < board.size(); i++) {
if (board[i][col] == 'Q')
return false;
}
int i = row, j = col;
while (i >= 0 && j >= 0)
if (board[i--][j--] == 'Q')
return false;
i = row, j = col;
while (i >= 0 && j < board.size())
if (board[i--][j++] == 'Q')
return false;
return true;
}
// rec function here will fill the queens
// 1. there can be only one queen in one row
// 2. if we filled the final row in the board then row will
// be equal to total number of rows in board
// 3. push that board configuration in answer set because
// there will be more than one answers for filling the board
// with n-queens
void rec(vector board, int row)
{
if (row == board.size()) {
answer.push_back(board);
return;
}
for (int i = 0; i < board.size(); i++) {
// for each position check if it is safe and if it
// safe make a recursive call with
// row+1,board[i][j]='Q' and then revert the change
// in board that is make the board[i][j]='.' again to
// generate more solutions
if (safe(row, i, board)) {
board[row][i] = 'Q';
rec(board, row + 1);
board[row][i] = '.';
}
}
return;
}
// function to solve n queens
vector > solveNQueens(int n)
{
string s;
for (int i = 0; i < n; i++)
s += '.';
// vector of string will make our board which is
// initially all empty
vector board(n, s);
rec(board, 0);
return answer;
}
int main()
{
clock_t start, end; // this is to calculate the
// execution time for n-queens
start = clock();
// size 4x4 is taken and we can pass some other
// dimension for chess board as well
cout << solveNQueens(4).size() << endl;
end = clock();
double time_taken
= double(end - start) / double(CLOCKS_PER_SEC);
cout << time_taken << " time was taken(in miliseconds)"
<< endl;
cout << "Out of " << answer.size()
<< " solutions one is following" << endl;
print_board();
}