Tai gana sudėtingas galvosūkis. Atsitiktinis nuotraukų dėliojimas užimtų labai daug laiko, nes reikėtų patikrinti daugybę kombinacijų, kurių dauguma būtų neteisingos. Jei į 6 nuotraukų galvosūkį įtraukiama dar viena nuotrauka, gaunama šešis kartus daugiau galimybių padėti 7-ąją nuotrauką į tuščią vietą.

Jei turime n nuotraukų, išeina (n-1)! = 1 * 2 * 3 * … * (n-2) * (n-1) skirtingų sprendinių. Taigi šiuo atveju yra 720 skirtingų sprendinių (tačiau beveik visi iš jų neteisingi).

Logiškai mąstydami galime paiešką labai susiaurinti. Atkreipkime dėmesį, kad visi bebrai, kurių kardai nukreipti žemyn, turi būti rikiuojami viršutinėje eilėje ir tėra tik vieno bebro nuotrauka, kurią galima padėti virš Broniaus nuotraukos.

Išsamioji paieška atliekama taikant grįžties algoritmą. Tačiau tada reikia labai daug atminties, todėl būtina sumažinti ieškomų atvejų skaičių atmetant logiškai netinkamus.

http://www.inf-schule.de/grenzen/komplexitaet/affenpuzzle/einstieg_affenpuzzle

https://it.wikipedia.org/wiki/Backtracking

Raktiniai žodžiai: loginis mąstymas, dedukcija, grįžties algoritmas.

Teisingas atsakymas