Problem n kraljica – Backtracking i optimizovano rešenje u C++

Problem n kraljica – analiza rešenja

Zadatak:
Napiši program koji određuje sve položaje n dama na šahovskoj tabli dimenzije n × n tako da se nijedne dve dame međusobno ne napadaju. Da bi dame bile raspoređene ispravno, u svakoj vrsti mora biti tačno jedna dama, pri čemu nijedne dve dame ne smeju biti u istoj koloni ili dijagonali.

Ulaz: Sa standardnog ulaza unosi se broj n (4 ≤ n ≤ 11).
Izlaz: Ispisati sve moguće rasporede dama, gde se svaka kombinacija prikazuje nizom od n brojeva koji predstavljaju kolone u kojima se dame nalaze u vrstama od 1 do n.

Primer:

Ulaz:
4
Izlaz:
3 1 4 2
2 4 1 3

Uputstvo i ideja rešenja

Ovaj zadatak je klasičan primer bektreking algoritma (backtracking). Ideja je da postavljamo dame red po red, i u svakom koraku proveravamo da li je postavljanje moguće bez sukoba sa prethodnim damama.

Koristimo niz (vektor) koji beleži u kojoj se koloni nalazi dama u svakoj vrsti.
Za svaku novu damu proveravamo da li se napada sa nekom prethodnom (u istoj koloni ili dijagonali).
Ako je pozicija bezbedna, prelazimo rekurzivno na sledeći red.
Ako nije, vraćamo se unazad i pokušavamo sledeću mogućnost (tipičan bekreking pristup).

Rešenje u C++ jeziku


#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> dame; // Vektor koji čuva pozicije dama po kolonama
int n;

// Proverava da li je bezbedno postaviti damu u red 'trenutniRed'
bool bezbedno(int trenutniRed) {
    for (int prethodniRed = 0; prethodniRed < trenutniRed; prethodniRed++) {
        // Ako su dve dame u istoj koloni
        if (dame[prethodniRed] == dame[trenutniRed])
            return false;
        // Ako su dve dame na istoj dijagonali
        if (abs(dame[prethodniRed] - dame[trenutniRed]) == abs(prethodniRed - trenutniRed))
            return false;
    }
    return true;
}

// Rekurzivna funkcija za postavljanje dama red po red
void postaviDame(int red) {
    if (red == n) {
        // Kada smo postavili svih n dama, ispisujemo rešenje
        for (int i = 0; i < n; i++) {
            cout << dame[i] + 1 << " "; // +1 da bi kolone bile od 1 do n
        }
        cout << endl;
        return;
    }

    // Pokušavamo da postavimo damu u svaku kolonu u tekućem redu
    for (int kolona = 0; kolona < n; kolona++) {
        dame[red] = kolona; // Postavljamo damu u kolonu
        if (bezbedno(red)) {
            postaviDame(red + 1); // Nastavljamo sa sledećim redom
        }
    }
}

int main() {
    cout << "Unesite broj n (4 <= n <= 11): ";
    cin >> n;

    if (n < 4 || n > 11) {
        cout << "Dozvoljene vrednosti su od 4 do 11." << endl;
        return 1;
    }

    dame.resize(n); // Inicijalizujemo vektor veličine n
    postaviDame(0); // Pokrećemo rekurziju od prvog reda

    return 0;
}

Objašnjenje koda

Program koristi vektor dame gde je svaki element broj kolone u kojoj se dama nalazi u određenom redu. Funkcija bezbedno() proverava da li se trenutna dama sukobljava sa nekom od prethodnih dama po sledećim pravilima:

Ako imaju istu kolonu → sukob;
Ako se nalaze na istoj dijagonali → sukob;
Inače → bezbedno postavljanje.

Rekurzivna funkcija postaviDame() ide redom od prvog do poslednjeg reda. Kada dođe do slučaja da je red == n, znači da su sve dame uspešno postavljene i da smo pronašli validno rešenje koje se ispisuje na ekran.

Komentar o efikasnosti i mogućim poboljšanjima

Ovaj algoritam koristi čistu rekurziju i ima eksponencijalnu složenost (reda O(n!)), jer proverava veliki broj mogućih kombinacija.

Moguća poboljšanja:

Korišćenje pomoćnih nizova za praćenje zauzetih kolona i dijagonala (kolona[], dijag1[], dijag2[]) — time se izbegava višestruko prolazak kroz sve prethodne redove u funkciji bezbedno().
Simetrijom tabli (refleksija i rotacija) može se smanjiti broj potrebnih provera.
Za veće vrednosti n mogu se koristiti heuristike ili pristupi zasnovani na ograničenjima (npr. constraint programming).

Za n = 8 (klasičan problem osam dama) postoje 92 različita rešenja. Ovaj pristup ih sve uspešno pronalazi, ali za veće n može postati spor zbog eksponencijalnog rasta kombinacija.

Problem n kraljica – optimizovano rešenje

Zadatak:
Postaviti n dama na šahovsku tablu dimenzije n×n tako da se nijedne dve dame ne napadaju. U svakoj vrsti mora biti tačno jedna dama, a dame se ne smeju nalaziti u istoj koloni niti na istoj dijagonali.

Ulaz: Unosi se broj n (4 ≤ n ≤ 11).
Izlaz: Ispisuju se svi mogući rasporedi dama, gde se svaki raspored prikazuje kao niz kolona u kojima se dame nalaze u redovima od 1 do n.

Primer:

Ulaz:
4
Izlaz:
2 4 1 3
3 1 4 2

Uputstvo i ideja rešenja

Ovo je unapređena verzija prethodnog bekreking (backtracking) algoritma za problem n kraljica. Ključna razlika je u tome što se konfliktne pozicije proveravaju u O(1) vremenu, pomoću tri pomoćna niza:

zauzetaKolona[k] – označava da li je kolona k već zauzeta,
zauzetaDijagonala1[v - k + n] – glavna dijagonala,
zauzetaDijagonala2[v + k] – sporedna dijagonala.

Na ovaj način se izbegava prolazak kroz sve prethodne redove i proverava samo tri logička uslova, što značajno ubrzava rad programa.

Rešenje u C++ jeziku


#include <iostream>
#include <vector>
using namespace std;

static const int MAKS = 16;
int n;

int pozicije[MAKS];              // pozicije[i] = kolona u kojoj se nalazi dama u vrsti i
bool zauzetaKolona[MAKS];        // da li je kolona zauzeta
bool zauzetaDijagonala1[MAKS*2]; // glavne dijagonale
bool zauzetaDijagonala2[MAKS*2]; // sporedne dijagonale

bool mozePostaviti(int vrsta, int kolona) {
    if (zauzetaKolona[kolona]) return false;
    int idx1 = vrsta - kolona + n;
    if (zauzetaDijagonala1[idx1]) return false;
    int idx2 = vrsta + kolona;
    if (zauzetaDijagonala2[idx2]) return false;
    return true;
}

void postaviDamu(int vrsta) {
    if (vrsta > n) {
        for (int i = 1; i <= n; i++)
            cout << pozicije[i] << (i < n ? ' ' : '\n');
        return;
    }

    for (int kol = 1; kol <= n; kol++) {
        if (mozePostaviti(vrsta, kol)) {
            pozicije[vrsta] = kol;
            zauzetaKolona[kol] = true;
            zauzetaDijagonala1[vrsta - kol + n] = true;
            zauzetaDijagonala2[vrsta + kol] = true;

            postaviDamu(vrsta + 1);

            zauzetaKolona[kol] = false;
            zauzetaDijagonala1[vrsta - kol + n] = false;
            zauzetaDijagonala2[vrsta + kol] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;

    for (int i = 1; i <= n; i++) zauzetaKolona[i] = false;
    for (int d = 1; d <= 2*n; d++) {
        zauzetaDijagonala1[d] = false;
        zauzetaDijagonala2[d] = false;
    }

    postaviDamu(1);
    return 0;
}

Objašnjenje koda

Program koristi globalne nizove da bi u svakom trenutku znao koje su kolone i dijagonale zauzete. Svaka dama koja se postavi označava tri vrednosti kao zauzete, a pri vraćanju (backtrack) te vrednosti se poništavaju.

Funkcija mozePostaviti() proverava samo tri logička uslova, pa je svaka provera konstantna (O(1)).

Kada se sve dame uspešno postave (tj. vrsta > n), ispisuje se validno rešenje. Rekurzivni pozivi pretražuju sve moguće kombinacije dok se ne pronađu svi rasporedi.

Analiza i efikasnost

Ovaj algoritam ima istu teoretsku složenost kao prethodni (reda O(n!)), ali praktično radi mnogo brže jer:

svaka provera validnosti traje O(1),
rano odbacuje grane koje ne mogu dati rešenje,
koristi minimalne strukture u memoriji.

Za vrednosti do n = 11 program završava u deliću sekunde i ispisuje sva rešenja. Broj rešenja za klasičan problem 8 dama je 92, a ovaj algoritam ih sve brzo pronalazi.

Moguća proširenja

Umesto ispisivanja rešenja, mogu se čuvati u vektoru i analizirati (npr. broj simetričnih rasporeda).
Dodavanjem heuristika (npr. „Least Conflicts“) moguće je rešavati i veće n.
Rešenje se može lako prilagoditi da prikazuje vizuelni raspored na tabli (npr. sa ‘Q’ i ‘.’).

Ovo optimizovano rešenje predstavlja efikasan i elegantan pristup klasičnom problemu bekreking pretrage.

Problem n kraljica – optimizovano rešenje

Zadatak:
Napisati program koji određuje sve moguće rasporede n dama na šahovskoj tabli dimenzije n × n tako da se nijedne dve dame ne napadaju. U svakoj vrsti mora biti tačno jedna dama, a nijedne dve dame ne smeju biti u istoj koloni ili na istoj dijagonali.

Ulaz: Jedan prirodan broj n (4 ≤ n ≤ 11).
Izlaz: Sve moguće rasporede dama, po jedan raspored po redu. Svaki raspored se ispisuje kao n brojeva odvojenih razmakom, gde broj na poziciji i označava kolonu dame u vrsti i.

Primer:

Ulaz:
4
Izlaz:
2 4 1 3
3 1 4 2

Uputstvo i ideja rešenja

Ovaj zadatak se rešava rekurzivnom metodom poznatom kao backtracking. Ideja je da se dame postavljaju red po red, proveravajući da li se međusobno napadaju.

Da bi se izbeglo stalno pretraživanje svih prethodnih dama, koristi se optimizacija pomoću tri pomoćna niza:

zauzetaKolona[k] – označava da li je kolona k zauzeta,
zauzetaDijagonala1[v - k + n] – za glavne dijagonale,
zauzetaDijagonala2[v + k] – za sporedne dijagonale.

Ovim pristupom svaka provera zauzetosti traje O(1) umesto O(n), što čini algoritam znatno efikasnijim.

Rešenje u C++ jeziku


#include <iostream>
#include <vector>
using namespace std;

static const int MAKS = 16;
int n;

int pozicije[MAKS];              // pozicije[i] = kolona dame u vrsti i
bool zauzetaKolona[MAKS];        // da li je kolona zauzeta
bool zauzetaDijagonala1[MAKS*2]; // glavne dijagonale
bool zauzetaDijagonala2[MAKS*2]; // sporedne dijagonale

bool mozePostaviti(int vrsta, int kolona) {
    if (zauzetaKolona[kolona]) return false;
    int idx1 = vrsta - kolona + n;
    if (zauzetaDijagonala1[idx1]) return false;
    int idx2 = vrsta + kolona;
    if (zauzetaDijagonala2[idx2]) return false;
    return true;
}

void postaviDamu(int vrsta) {
    if (vrsta > n) {
        for (int i = 1; i <= n; i++)
            cout << pozicije[i] << (i < n ? ' ' : '\n');
        return;
    }

    for (int kol = 1; kol <= n; kol++) {
        if (mozePostaviti(vrsta, kol)) {
            pozicije[vrsta] = kol;
            zauzetaKolona[kol] = true;
            zauzetaDijagonala1[vrsta - kol + n] = true;
            zauzetaDijagonala2[vrsta + kol] = true;

            postaviDamu(vrsta + 1);

            zauzetaKolona[kol] = false;
            zauzetaDijagonala1[vrsta - kol + n] = false;
            zauzetaDijagonala2[vrsta + kol] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;

    for (int i = 1; i <= n; i++) zauzetaKolona[i] = false;
    for (int d = 1; d <= 2*n; d++) {
        zauzetaDijagonala1[d] = false;
        zauzetaDijagonala2[d] = false;
    }

    postaviDamu(1);
    return 0;
}

Objašnjenje koda

Korak 1 – Inicijalizacija: Svi nizovi su na početku postavljeni na false, što znači da su sve kolone i dijagonale slobodne.

Korak 2 – Postavljanje dame: Za svaku vrstu pokušavamo da postavimo damu u neku kolonu i proveravamo da li je pozicija bezbedna pomoću funkcije mozePostaviti().

Korak 3 – Rekurzija: Ako je pozicija bezbedna, funkcija rekurzivno poziva samu sebe za sledeću vrstu. Kada se uspešno postavi svih n dama, ispisuje se jedno rešenje.

Korak 4 – Povratak (Backtracking): Nakon svakog pokušaja, vrednosti se vraćaju na početno stanje kako bi se isprobale druge mogućnosti.

Analiza i efikasnost

Provera zauzetosti kolone i dijagonala traje O(1).
Ukupan broj mogućih pozicija dama je n!, ali se ogromna većina eliminiše pre nego što se uopšte proveri.
Za n ≤ 11 program radi izuzetno brzo – npr. za n = 8 ispisuje svih 92 rešenja u deliću sekunde.

Moguća poboljšanja

Čuvanje rešenja u vektorima radi kasnije analize (npr. simetrije).
Dodavanje heuristika (npr. „least conflicts“) za veće vrednosti n.
Vizuelizacija na tabli pomoću matrice znakova (‘Q’ i ‘.’).

Poređenje rešenja 1 i 2

Osobina	Rešenje 1	Rešenje 2 (optimizovano)
Provera sukoba	Prolazi kroz sve prethodne redove (O(n) po proveri)	Koristi tri logička niza → O(1) provera
Struktura podataka	Jedan vektor sa pozicijama dama	Jedan niz pozicija + tri pomoćna niza za kolone i dijagonale
Efikasnost	Sporo za veće n (n ≈ 10)	Vrlo brzo i stabilno za n do 11
Implementacija	Kraća i jednostavnija	Detaljnija, ali efikasnija
Pogodnost za veća n	Ograničena	Znanto bolja, može da se širi heuristikama

Zaključak:
Oba pristupa koriste istu ideju rekurzivnog pretraživanja, ali optimizovano rešenje postiže znatno bolju efikasnost zahvaljujući pametnom evidentiranju zauzetih kolona i dijagonala. To ga čini pogodnijim za analizu većih problema i osnovom za naprednije varijante algoritma.

Rešenje 3 — Iterativni pristup pomoću permutacija

U ovom rešenju koristimo iterativni pristup bez rekurzije. Ideja je da svaka permutacija n brojeva 1..n predstavlja raspored dama, pošto u svakoj vrsti i koloni može biti samo jedna dama. Zatim proveravamo da li postoji sukob na dijagonalama. Ako nema, raspored je validan.


#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// Funkcija koja proverava da li se dame napadaju dijagonalno
bool validnaPermutacija(const vector<int>& kolone) {
    int n = kolone.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (abs(kolone[i] - kolone[j]) == abs(i - j))
                return false;
        }
    }
    return true;
}

int main() {
    int n;
    cout << "Unesite broj n (4 <= n <= 11): ";
    cin >> n;

    if (n < 4 || n > 11) {
        cout << "Dozvoljene vrednosti su od 4 do 11." << endl;
        return 1;
    }

    vector<int> kolone(n);
    for (int i = 0; i < n; i++)
        kolone[i] = i + 1;

    do {
        if (validnaPermutacija(kolone)) {
            for (int i = 0; i < n; i++)
                cout << kolone[i] << " ";
            cout << endl;
        }
    } while (next_permutation(kolone.begin(), kolone.end()));

    return 0;
}

Objašnjenje koda

Kreiramo vektor kolone koji sadrži brojeve od 1 do n, gde kolone[i] označava kolonu u kojoj se dama nalazi u i-tom redu.
Funkcija validnaPermutacija proverava da li se bilo koja dva dama napadaju na dijagonalama. Ako je razlika kolona jednaka razlici redova, postoji sukob.
Kroz sve permutacije vektora prolazimo pomoću next_permutation i ispisujemo one koje su validne.
Ovaj pristup je potpuno iterativan i ne koristi rekurziju.

Efikasnost i analiza

Ukupna složenost: O(n! * n²), jer generišemo sve permutacije i proveravamo dijagonale.
Prednost: jednostavno i lako razumljivo; nema rekurzije.
Nedostatak: brzo postaje neizvodljivo za veće n (n ≥ 10). Za n=11 postoji 39.916.800 permutacija.
Moguća poboljšanja:
- Paralelizacija provere permutacija.
- Upotreba bitmask reprezentacije za bržu proveru dijagonala.
- Heuristički pristupi, npr. min-conflicts algoritam.

Rešenje 4 — Heuristički pristup: Min-Conflicts algoritam

U ovom rešenju koristimo heuristički pristup poznat kao min-conflicts algoritam. Ideja je početi sa proizvoljnim rasporedom n dama, a zatim iterativno smanjivati konflikte tako što pomeramo dame u kolone koje izazivaju najmanji broj sukoba.


#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

// Funkcija koja računa broj konflikata za damu u datom redu i koloni
int konflikti(int red, int kolona, const vector<int>& pozicije) {
    int n = pozicije.size();
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i == red) continue;
        if (pozicije[i] == kolona || abs(pozicije[i] - kolona) == abs(i - red))
            cnt++;
    }
    return cnt;
}

int main() {
    srand(time(nullptr));
    int n;
    cout << "Unesite broj n (4 <= n <= 100): ";
    cin >> n;

    if (n < 4) {
        cout << "Nedozvoljena vrednost n." << endl;
        return 1;
    }

    // Nasumičan početni raspored dama (svaka vrsta ima jednu damu u nekoj koloni)
    vector<int> pozicije(n);
    for (int i = 0; i < n; i++)
        pozicije[i] = rand() % n;

    const int MAX_ITER = 10000;
    for (int iter = 0; iter < MAX_ITER; iter++) {
        // Pronađi damu sa konfliktom
        vector<int> konfliktne;
        for (int i = 0; i < n; i++) {
            if (konflikti(i, pozicije[i], pozicije) > 0)
                konfliktne.push_back(i);
        }

        if (konfliktne.empty()) break; // Nema konflikata - rešenje je pronađeno

        int red = konfliktne[rand() % konfliktne.size()];

        // Pomeramo damu u kolonu sa najmanjim konfliktom
        int minKonflikt = n+1;
        vector<int> najboljeKolone;
        for (int k = 0; k < n; k++) {
            int c = konflikti(red, k, pozicije);
            if (c < minKonflikt) {
                minKonflikt = c;
                najboljeKolone = {k};
            } else if (c == minKonflikt) {
                najboljeKolone.push_back(k);
            }
        }

        pozicije[red] = najboljeKolone[rand() % najboljeKolone.size()];
    }

    // Ispis rešenja
    for (int i = 0; i < n; i++)
        cout << pozicije[i]+1 << " ";
    cout << endl;

    return 0;
}

Objašnjenje koda

Početni raspored dama generišemo nasumično, po jedan po vrsti.
Funkcija konflikti računa koliko dama napada datu damu u određenoj koloni.
U svakoj iteraciji biramo damu koja je u konfliktu i pomeramo je u kolonu koja minimalizuje broj sukoba.
Postupak se ponavlja dok ne dobijemo raspored bez konflikata ili dok ne dostignemo maksimalan broj iteracija.

Efikasnost i analiza

Algoritam je vrlo brz i praktičan za veće n (čak n ~ 100 i više).
Vremenska složenost zavisi od broja iteracija i n, ali empirijski radi gotovo uvek u stotinama ili hiljadama koraka.
Prednost: omogućava rešavanje velikih instanci problema n kraljica, što nije izvodljivo rekurzivnim backtracking pristupima za n ≥ 15.
Nedostatak: rezultat je heuristički; može zahtevati restart ako se zaglavi u lokalnom minimumu.
Moguća poboljšanja:
- Višestruki startovi sa različitim nasumičnim početnim stanjima.
- Dodavanje male verovatnoće nasumičnog pomeranja da bi se izbegli lokalni minimumi.
- Bitmask reprezentacija za bržu proveru sukoba.

Rešenje 5 — Bitmask Dynamic Programming (napredno)

Ovo rešenje koristi bitmask dynamic programming za efikasno brojanje svih rešenja problema N kraljica. Ideja je da se svaka kolona i dijagonale predstavljaju kao bitovi, tako da možemo u O(1) proveriti da li je polje slobodno. Ovaj pristup je napredniji, ali značajno ubrzava rešavanje za veće n (n ≤ 16).


#include <iostream>
using namespace std;

int n;
int total = 0;

// Bitmask DP funkcija: vrsta = trenutni red, kol = zauzete kolone,
// diag1 = zauzete glavne dijagonale, diag2 = zauzete sporedne dijagonale
void solve(int vrsta, int colMask, int diag1Mask, int diag2Mask) {
    if (vrsta == n) {
        total++;
        return;
    }

    // Svi slobodni položaji u ovom redu
    int available = ((1 << n) - 1) & ~(colMask | diag1Mask | diag2Mask);
    while (available) {
        int p = available & -available; // uzmi desni najnižiji slobodan bit
        available -= p; // ukloni ga iz dostupnih

        // Rekurzivno postavi damu u sledeći red
        solve(vrsta + 1, colMask | p, (diag1Mask | p) << 1, (diag2Mask | p) >> 1);
    }
}

int main() {
    cin >> n;
    total = 0;
    solve(0, 0, 0, 0);
    cout << total << endl;
    return 0;
}

Objašnjenje koda:

Svaki bit u colMask označava da li je kolona zauzeta.
Glavne i sporedne dijagonale se takođe predstavljaju bitmaskama (diag1Mask i diag2Mask).
available računa sve slobodne kolone u trenutnom redu.
Operator p = available & -available uzima desni najniži slobodan bit.
Rekurzivni poziv ažurira maske za sledeći red koristeći bitshift operacije.
Kada vrsta == n, pronađeno je jedno validno rešenje, pa se total uvećava.

Efikasnost:

Vremenska složenost je O(n!) u praksi, ali bitmasking omogućava izuzetno brzu provera slobodnih polja.
Memorijska složenost je O(1) jer se koristi samo nekoliko celobrojnih varijabli.
Ovo je posebno pogodno kada želimo samo broj rešenja, a ne sve rasporede.

Moguća poboljšanja / napredna optimizacija: Koristiti simetrije table (rotacije i refleksije) da se broj rešenja prepolovi, čime se još više ubrzava izvođenje za n ≥ 12.

Uporedna analiza 5 rešenja — Problem N kraljica

Sledeća tabela i komentari prikazuju različite pristupe rešavanju problema N kraljica, sa fokusom na efikasnost, tip rešenja i kompleksnost.

Rešenje	Pristup	Opis	Vremenska složenost	Memorijska složenost	Napomene / prednosti
1	Klasični backtracking (rekurzivno)	Postavlja dame red po red, proverava da li je trenutna pozicija bezbedna (kolone + dijagonale).	O(n!)	O(n) (za niz pozicija i rekurzivni stack)	Jednostavno i edukativno; brzo za n ≤ 10; prikazuje sva rešenja.
2	Backtracking sa beleženjem zauzetih kolona i dijagonala (bool nizovi)	Optimizacija klasičnog backtrackinga; proverava konflikte u O(1) vremenu koristeći pomoćne nizove.	O(n!) u praksi, ali brže od rešenja 1 zbog brzih provera	O(n + 2n + 2n) ≈ O(n)	Veoma brzo za n ≤ 11; još uvek generiše sva rešenja; jednostavno za implementaciju.
3	Permutacije (generišemo sve permutacije kolona)	Svaka permutacija n kolona predstavlja mogući raspored; proverava dijagonale.	O(n! * n)	O(n)	Jednostavno za implementaciju; dobro za male n; nepotrebno proverava sve permutacije, što nije efikasno za n ≥ 10.
4	Heuristički pristup (npr. min-conflicts)	Koristi lokalnu pretragu i rešava konfliktne pozicije iterativno; može brzo pronaći jedno rešenje.	O(n) do O(n^2) po iteraciji (empirijski)	O(n)	Brzo pronalazi jedno rešenje za veće n; ne garantuje sve rešenja; idealno za praktične slučajeve gde je dovoljno jedno rešenje.
5	Bitmask dynamic programming	Reprezentuje kolone i dijagonale kao bitove; koristi rekurziju sa bitmaskama za brzo brojanje svih rešenja.	O(n!) u praksi, ali veoma brzo zbog bit operacija	O(1)	Efikasno za brojanje rešenja; manje pogodno za generisanje svih konfiguracija; napredno, ali optimalno za n ≤ 16.

Zaključak:

Za edukativne i male dimenzije (n ≤ 10) — rešenja 1, 2 i 3 su dovoljna.
Za praktične potrebe kada je potrebno samo jedno rešenje — heuristički pristupi (rešenje 4) su odlični.
Za brzo brojanje svih rešenja kod većih n (n ≤ 16) — bitmask DP (rešenje 5) je najefikasniji.
Uvek je dobro početi sa jednostavnim backtracking rešenjima kako bi se razumela struktura problema, a potom preći na optimizacije i napredne pristupe.

Prethodno
|< Priprema za drzavno takmičenje i SIO

Problem n kraljica – analiza rešenja

Uputstvo i ideja rešenja

Rešenje u C++ jeziku

Objašnjenje koda

Komentar o efikasnosti i mogućim poboljšanjima

Problem n kraljica – optimizovano rešenje

Uputstvo i ideja rešenja

Rešenje u C++ jeziku

Objašnjenje koda

Analiza i efikasnost

Moguća proširenja

Problem n kraljica – optimizovano rešenje

Uputstvo i ideja rešenja

Rešenje u C++ jeziku

Objašnjenje koda

Analiza i efikasnost

Moguća poboljšanja

Poređenje rešenja 1 i 2

Rešenje 3 — Iterativni pristup pomoću permutacija

Objašnjenje koda

Efikasnost i analiza

Rešenje 4 — Heuristički pristup: Min-Conflicts algoritam

Objašnjenje koda

Efikasnost i analiza

Rešenje 5 — Bitmask Dynamic Programming (napredno)

Uporedna analiza 5 rešenja — Problem N kraljica

Zaključak:

Podešavanja kolačića