Ammendav otsing. Lippude paigutamise ülesanne (8 queens).
Ammendav otsing (variantide läbivaatus)
Teatud ülesannete korral on ainsaks täpseks lahendusmeetodiks "proovimise meetod", s.t. kõigi võimalike lahendusvariantide süstemaatiline läbivaatus (ammendav otsing). Kuna lõplikul n-elemendilisel hulgal on 2^n alamhulka, siis on ammendava otsingu ülesanne üldjuhtumil eksponentsiaalse keerukusega. Konkreetset keerukust saab teatud juhtudel vähendada otsinguruumi ahendamisega.
Kaht liiki ülesanded:
* esimese sobiva lahendi leidmine
* kõigi lahendite leidmine
Variandigeneraator - funktsioon lahendusvariantide süstemaatiliseks genereerimiseks.
Tagasivõtt, backtracking: uue variandi valik antud tasemel, kui kõik alamjuhtumid on ammendatud.
Näide. 8 lippu - kõigi lahendite leidmine.
Paigutada malelauale 8 lippu nii, et ükski neist ei oleks mõne teise lipu tules.
Idee: paigutada lippe järjekorras "vasakult paremale" nii, et n-nda lipu jaoks otsitakse kohta olukorras, kus eelnevad n-1 lippu on nõuetekohaselt paigutatud. Kui sobivat kohta n-ndas veerus ei leidu, siis vähendada n väärtust (backtracking) ning leida järgmine sobiv paigutus "eelmisele" lipule.
Kujutame malelaua seisu ühemõõtmelise massiivina laud, mille iga element kodeerib ühe malelaua veeru järgmiselt:
laud[j]=0 - veerus j ei ole lippu paigutatud
laud[j]=i - veerus j paikneb lipp i-ndas reas (1 <= i <= 8)
Predikaat onTules(n) : kas lipp number n on mõne eelneva lipu tules (samal real või diagonaalil, samas veerus ei saa olla juba seisu kujutusviisi tõttu).