b"\n_START_ARTICLE_\nProblema damelor\n_START_SECTION_\nIstoria\n_START_PARAGRAPH_\nCompozitorul de \xc8\x99ah\xc2\xa0Max Bezzel a publicat problema celor opt regine \xc3\xaen 1848. Franz Nauck a publicat primele solu\xc8\x9bii \xc3\xaen 1850. Nauck a \xc8\x99i extins problema la\xc2\xa0n regine, cu n regine pe o tabl\xc4\x83 de \xc8\x99ah de n \xc3\x97 n p\xc4\x83trate._NEWLINE_De atunci, mul\xc8\x9bi matematicieni, inclusiv Carl Friedrich Gauss, au lucrat at\xc3\xa2t la problema ini\xc8\x9bial\xc4\x83 cu opt regine c\xc3\xa2t \xc8\x99i la varianta generalizat\xc4\x83 cu\xc2\xa0n\xc2\xa0regine. \xc3\x8en 1874, S. Gunther\xc2\xa0a\xc2\xa0propus o metod\xc4\x83 care utilizeaz\xc4\x83 determinan\xc8\x9bii pentru a g\xc4\x83si solu\xc8\x9bii. J. W. L. Glaisher\xc2\xa0a rafinat abordarea lui Gunther._NEWLINE_\xc3\x8en 1972, Edsger Dijkstra\xc2\xa0a folosit aceast\xc4\x83 problem\xc4\x83 pentru a ilustra puterea a ceea ce el nume\xc8\x99te programare structurat\xc4\x83. El a publicat o descriere foarte detaliat\xc4\x83 a unui algoritm backtracking\xc2\xa0de parcurgere \xc3\xaen ad\xc3\xa2ncime.\n_START_SECTION_\nConstruc\xc8\x9bia solu\xc8\x9biei\n_START_PARAGRAPH_\nProblema poate fi destul de costisitoare computa\xc8\x9bional, \xc3\xaentruc\xc3\xa2t sunt 4426165368 (adic\xc4\x83, \xe2\x82\x86\xe2\x82\x84C\xe2\x82\x88) aranjamente posibile ale celor opt regine pe o tabl\xc4\x83 8\xc3\x978, dar numai 92 de solu\xc8\x9bii. Se pot utiliza scurt\xc4\x83turi care reduc cerin\xc8\x9bele de calcul, sau reguli aproximative, care evit\xc4\x83 c\xc4\x83utarea cu for\xc8\x9ba brut\xc4\x83. De exemplu, aplic\xc3\xa2nd o regul\xc4\x83 simpl\xc4\x83, care constr\xc3\xa2nge fiecare regin\xc4\x83 s\xc4\x83 stea pe coloana (sau r\xc3\xa2ndul) ei, de\xc8\x99i \xc3\xaenc\xc4\x83 se consider\xc4\x83 c\xc4\x83 se folose\xc8\x99te for\xc8\x9ba brut\xc4\x83, se poate reduce num\xc4\x83rul de posibilit\xc4\x83\xc8\x9bi la 16777216 (8\xe2\x81\xb8) combina\xc8\x9bii posibile. Generarea de\xc2\xa0permut\xc4\x83ri reduce \xc8\x99i mai mult posibilit\xc4\x83\xc8\x9bile la 40320 (adic\xc4\x83\xc2\xa08!), care sunt apoi verificate dac\xc4\x83 damele nu se atac\xc4\x83 pe diagonal\xc4\x83._NEWLINE_Martin Richards a publicat un program ce num\xc4\x83r\xc4\x83 solu\xc8\x9biile pentru problema cu n dame cu ajutorul opera\xc8\x9biilor la nivel de bit.\n_START_SECTION_\nExerci\xc8\x9biu de proiectare de algoritm\n_START_PARAGRAPH_\nG\xc4\x83sirea de solu\xc8\x9bii pentru problema celor opt regine este un bun exemplu de joc simplu, dar netrivial. Din acest motiv, adesea este folosit\xc4\x83 ca exemplu de problem\xc4\x83 pentru diverse tehnici de programare, inclusiv abord\xc4\x83ri netradi\xc8\x9bionale, cum ar fi\xc2\xa0programarea cu constr\xc3\xa2ngeri, programarea logic\xc4\x83 sau algoritmii genetici. De cele mai multe ori, este folosit ca un exemplu de problem\xc4\x83 care poate fi rezolvat\xc4\x83 cu un\xc2\xa0algoritm\xc2\xa0recursiv, formul\xc3\xa2nd problema celor\xc2\xa0n regine inductiv \xc3\xaen ceea ce prive\xc8\x99te ad\xc4\x83ugarea unei singure regine la orice solu\xc8\x9bie a problemei plas\xc4\x83rii a\xc2\xa0n\xe2\x88\x921 regine pe o tabl\xc4\x83 n x n. Induc\xc8\x9bia\xc2\xa0se limiteaz\xc4\x83 cu problema plas\xc4\x83rii a 0 regine pe o tabl\xc4\x83 de \xc8\x99ah, a c\xc4\x83rei solu\xc8\x9bie este tabla goal\xc4\x83._NEWLINE_Aceast\xc4\x83 tehnic\xc4\x83 este mult mai eficient\xc4\x83 dec\xc3\xa2t algoritmul naiv al c\xc4\x83ut\xc4\x83rii cu for\xc8\x9ba brut\xc4\x83, care consider\xc4\x83 toate cele 64\xe2\x81\xb8 = 2\xe2\x81\xb4\xe2\x81\xb8 = 281474976710656 distribu\xc8\x9bii posibile ale celor opt regine, \xc8\x99i apoi le filtreaz\xc4\x83 pentru a elimina toate a\xc8\x99ez\xc4\x83rile \xc3\xaen care dou\xc4\x83 regine sunt fie pe aceea\xc8\x99i p\xc4\x83trat (l\xc4\x83s\xc3\xa2nd doar 64!/56! = 178,462,987,637,760 posibile distribu\xc8\x9bii) fie pe pozi\xc8\x9bii care se atac\xc4\x83 reciproc. Printre altele, acest algoritm foarte prost va produce acelea\xc8\x99i rezultate \xc3\xaen mod repetat, \xc3\xaen toate\xc2\xa0permut\xc4\x83rile\xc2\xa0diferite a opt regine, \xc8\x99i va repeta acelea\xc8\x99i calcule de mai multe ori pentru submul\xc8\x9bime diferit\xc4\x83 a fiec\xc4\x83rei solu\xc8\x9bii. Un algoritm de for\xc8\x9b\xc4\x83 brut\xc4\x83 mai bun pune o singur\xc4\x83 regin\xc4\x83 pe fiecare r\xc3\xa2nd, apoi face doar 8\xe2\x81\xb8 = 2\xc2\xb2\xe2\x81\xb4 = 16.777.216 a\xc8\x99ez\xc4\x83ri._NEWLINE_Se poate \xc3\xaens\xc4\x83 \xc8\x99i mai bine dec\xc3\xa2t a\xc8\x99a._NEWLINE_Un algoritm rezolv\xc4\x83 problema a opt ture\xc2\xa0prin generarea de permut\xc4\x83ri ale numerelor de la 1 la 8 (care sunt 8! = 40320), \xc8\x99i utilizeaz\xc4\x83 elementele din fiecare permutare ca indici pentru plasarea unei regine pe fiecare r\xc3\xa2nd._NEWLINE_Apoi se resping acele table cu pozi\xc8\x9bii care se atac\xc4\x83 pe diagonal\xc4\x83._NEWLINE_Programul de\xc2\xa0c\xc4\x83utare \xc3\xaen ad\xc3\xa2ncime\xc2\xa0prin\xc2\xa0backtracking, o u\xc8\x99oar\xc4\x83 \xc3\xaembun\xc4\x83t\xc4\x83\xc8\x9bire a metodei cu permut\xc4\x83ri, construie\xc8\x99te un\xc2\xa0arbore de c\xc4\x83utare consider\xc3\xa2nd o linie a tablei la un moment dat, elimin\xc3\xa2nd majoritatea pozi\xc8\x9biilor care nu duc la solu\xc8\x9bii din stadii foarte timpurii \xc3\xaen construc\xc8\x9bia lor._NEWLINE_Deoarece respinge atacurile de tip tur\xc4\x83 \xc8\x99i \xc3\xaen diagonal\xc4\x83 chiar \xc8\x99i pe configura\xc8\x9bii incomplete, ea analizeaz\xc4\x83 numai 15720 de plas\xc4\x83ri de regine._NEWLINE_O \xc3\xaembun\xc4\x83t\xc4\x83\xc8\x9bire suplimentar\xc4\x83, care examineaz\xc4\x83 doar 5508 de plasamente posibile, este de a combina metoda bazat\xc4\x83 pe permutare cu metoda t\xc4\x83ierii timpurii: permut\xc4\x83rile sunt generate \xc3\xaent\xc3\xa2i \xc3\xaen ad\xc3\xa2ncime, \xc8\x99i_NEWLINE_spa\xc8\x9biul de c\xc4\x83utare este t\xc4\x83iat dac\xc4\x83 permutarea par\xc8\x9bial\xc4\x83 produce un atac pe diagonal\xc4\x83._NEWLINE_Programarea pe constr\xc3\xa2ngeri\xc2\xa0poate fi \xc8\x99i ea foarte eficient\xc4\x83 la aceast\xc4\x83 problem\xc4\x83._NEWLINE_O alternativ\xc4\x83 la c\xc4\x83utarea exhaustiv\xc4\x83 este un algoritm de \xe2\x80\x9ereparare iterativ\xc4\x83\xe2\x80\x9d, care, de obicei, \xc3\xaencepe cu toate reginele pe tabl\xc4\x83, de exemplu cu o regin\xc4\x83 pe fiecare coloan\xc4\x83. Apoi, el contorizeaz\xc4\x83 num\xc4\x83rul de conflicte (atacuri), \xc8\x99i folose\xc8\x99te o euristic\xc4\x83 pentru a determina modul de a \xc3\xaembun\xc4\x83t\xc4\x83\xc8\x9bi plasarea reginelor.  'Minim-conflicte' euristic\xc4\x83 \xe2\x80\x94 mutarea piesei cu cel mai mare num\xc4\x83r de conflicte pe p\xc4\x83tratul de pe aceea\xc8\x99i coloan\xc4\x83 \xc3\xaen care num\xc4\x83rul de conflicte este minim\xc2\xa0\xe2\x80\x94 este deosebit de eficient\xc4\x83: se g\xc4\x83se\xc8\x99te o solu\xc8\x9bie la problema a 1.000.000 de regine \xc3\xaen medie \xc3\xaen mai pu\xc8\x9bin de 50 de pa\xc8\x99i. Aceasta presupune c\xc4\x83 configura\xc8\x9bia ini\xc8\x9bial\xc4\x83 este \xe2\x80\x9edestul de bun\xc4\x83\xe2\x80\x9d\xc2\xa0\xe2\x80\x94 dac\xc4\x83 un milion de regine stau pe acela\xc8\x99i r\xc3\xa2nd, este evident c\xc4\x83 va fi nevoie de cel pu\xc8\x9bin 999.999 pa\xc8\x99i. Un punct de plecare\xc2\xa0\xe2\x80\x9edestul de bun\xe2\x80\x9d poate fi g\xc4\x83sit, de exemplu, pun\xc3\xa2nd fiecare regin\xc4\x83 pe propriul s\xc4\x83u r\xc3\xa2nd \xc8\x99i coloan\xc4\x83, astfel \xc3\xaenc\xc3\xa2t s\xc4\x83 intre \xc3\xaen conflict cu cel mai mic num\xc4\x83r de regine deja aflate pe tabl\xc4\x83._NEWLINE_Spre deosebire de c\xc4\x83utarea cu revenire descris\xc4\x83 mai sus, \xe2\x80\x9erepararea iterativ\xc4\x83\xe2\x80\x9d nu garanteaz\xc4\x83 o solu\xc8\x9bie: ca toate procedurile de tip urcarea dealului (de exemplu, greedy) se poate ajunge la blocaj \xc3\xaentr-un optim local (caz \xc3\xaen care algoritmul poate fi reluat cu o alt\xc4\x83 configura\xc8\x9bie ini\xc8\x9bial\xc4\x83). Pe de alt\xc4\x83 parte, se pot rezolva probleme de dimensiuni cu c\xc3\xa2teva ordine de m\xc4\x83rime mai mari dec\xc3\xa2t domeniul de aplicare al c\xc4\x83ut\xc4\x83rii \xc3\xaen ad\xc3\xa2ncime._NEWLINE_Anima\xc8\x9bia ilustreaz\xc4\x83 abordarea backtracking de rezolvare a problemei. O regin\xc4\x83 este plasat\xc4\x83 \xc3\xaentr-o coloan\xc4\x83 care se \xc8\x99tie c\xc4\x83 nu va provoca un conflict. Dac\xc4\x83 nu se g\xc4\x83se\xc8\x99te o coloan\xc4\x83, programul revine la ultima stare bun\xc4\x83 \xc8\x99i apoi \xc3\xaencearc\xc4\x83 o alt\xc4\x83 coloan\xc4\x83.\n_START_SECTION_\nExemplu de program\n_START_PARAGRAPH_\nMai jos este redat un program scris \xc3\xaen\xc2\xa0Pascal\xc2\xa0de Niklaus Wirth \xc3\xaen 1976. El g\xc4\x83se\xc8\x99te o solu\xc8\x9bie a problemei celor opt regine._NEWLINE_program eightqueen1(output);_NEWLINE_ _NEWLINE_var i : integer; q : boolean;_NEWLINE_    a : array[ 1 .. 8] of boolean;_NEWLINE_    b : array[ 2 .. 16] of boolean;_NEWLINE_    c : array[ -7 .. 7] of boolean;_NEWLINE_    x : array[ 1 .. 8] of integer;_NEWLINE_ _NEWLINE_procedure try( i : integer; var q : boolean);_NEWLINE_    var j : integer;_NEWLINE_    begin _NEWLINE_    j := 0;_NEWLINE_    repeat _NEWLINE_        j := j + 1; _NEWLINE_        q := false;_NEWLINE_        if a[ j] and b[ i + j] and c[ i - j] then_NEWLINE_            begin _NEWLINE_            x[ i    ] := j;_NEWLINE_            a[ j    ] := false; _NEWLINE_            b[ i + j] := false; _NEWLINE_            c[ i - j] := false;_NEWLINE_            if i < 8 then_NEWLINE_                begin_NEWLINE_                try( i + 1, q);_NEWLINE_                if not q then_NEWLINE_                    begin _NEWLINE_                    a[ j] := true; _NEWLINE_                    b[ i + j] := true; _NEWLINE_                    c[ i - j] := true;_NEWLINE_                    end_NEWLINE_                end _NEWLINE_            else _NEWLINE_                q := true_NEWLINE_            end_NEWLINE_    until q or (j = 8);_NEWLINE_    end;_NEWLINE_ _NEWLINE_beginfor i :=  1 to  8 do a[ i] := true;for i :=  2 to 16 do b[ i] := true;for i := -7 to  7 do c[ i] := true;try( 1, q);if q then_NEWLINE_    for i := 1 to 8 do write( x[ i]:4);writelnend."