Rekursija, backtrackingas. Pascal

Reikia parašyti programą - Šachmatų lentoje 8x8 išdėlioti 12 žirgų taip, kad jų kertami langeliai dengtų visą lentą.

Reikėtų pagalbos galvojant algoritmą. Užduotį reikia padaryti su rekursija ir backtrackingu(grįžimais). Esu sugalvojęs, kad reikėtų imti langelį, tada tikrinti, koks žirgas tą langelį galėtų kirsti ir statyti žirgą. Imti sekantį langelį ir kartoti veiksmą, jei nėra kur statyti grįžti atgal ir imti sekantį. Bet kaip tai programiškai padaryt, sunku sumąstyt.. :/

Dabartinis programos variantas - http://pastebin.com/PS6pLrRK bet čia daryta kitaip negu minėjau, čia pirma dedu žirga, tada sužymiu ką dengia ir t.t. Bet atsakymo ieško apie 5 min ...

Dabartinis programos variantas - http://pastebin.com/PS6pLrRK bet čia daryta kitaip negu minėjau, čia pirma dedu žirga, tada sužymiu ką dengia ir t.t. Bet atsakymo ieško apie 5 min ...

Tai klausimas... ?

Kaip optimalizuot algoritmą?

*Galbūt for ciklus galima kažkaip optimaliau užrašyt, pvz patikrinimo procedūroje?

*Pastoviai kviečiu nunulinima ir patikrinima, čia spėju didžiausias stabdis. Reikėtų dirbt su objektu (Lentos) kopijomis daug greičiau veiktų bei nereiktų švaistyti laiko nereikalingiems call'ams, bet kaip dirbti su tomis kopijomis? :)

Kaip optimalizuot algoritmą?

*Galbūt for ciklus galima kažkaip optimaliau užrašyt, pvz patikrinimo procedūroje?

*Pastoviai kviečiu nunulinima ir patikrinima, čia spėju didžiausias stabdis. Reikėtų dirbt su objektu (Lentos) kopijomis daug greičiau veiktų bei nereiktų švaistyti laiko nereikalingiems call'ams, bet kaip dirbti su tomis kopijomis? :)

Na labai jau cia sudetingai ir letai veikiantis algoritmas. Visu pirma tai tikrinimas turi vykti tik sudejus visus 12 zirgu. Nesinagrinejau per daug sito uzdavinio.. manyciau turetu buti kazkas gudresnio nei perrinkimas, bet jei jau eiti bruteforco budu, tai siulau naudoti vienmati masyva [1..64], atitinkamai "ejimu" indeksus N ir M, bei atskira masyva [1..12] zirgu pozicijai. Ir tiesiog perrinkti visas pozicijas visiems 12 zirgu tol, kol ju issidestymas uzpildys visa lenta. Ir toks perrinkimas tikrai uztrunka.

Beje, kai taip intensyviai sukami ciklai, stenkis skaiciuot kiek imanoma maziau, t.y. tokius kaip i+N[o] pradzioj dek i atskira kintamaji ir naudok ji, o ne skaiciuok visur kur reikia.

Taigi, turiu gerų žinių :D Pagaliau sumasčiau, sutvarkiau ir optimizavau savo algoritmą ir visą programą. Dabar programa atsakymą parodo per maždaug 5 sekundes :) Tai pavyko padaryti pasitelkus labai paprastą papildomą apribojimą žirgų dėliojimui :)

Function isItWorth(r:rec):boolean;
Begin
if ((tK-r.knights)*9) >= ((N*N)-r.spots)
       then isItWorth := true
       else isItWorth := false;
End;

Kur tK=12, r.knights=tuo momentu padėtų žirgų skaičius, N=8, o r.spots=uždengti lentos langeliai :)

Tai tiek, ačiū už patarimą, kurio dėja nepanaudojau :)