Problema celor opt regine

Problema celor opt regine este o problemă combinatorie  binecunoscută pentru aranjarea pieselor pe o tablă de șah . Formularea inițială: „Aranjați 8 dame pe o tablă de șah standard cu 64 de celule, astfel încât niciuna dintre ele să nu fie atacată de altă parte . ” Se înțelege că regina bate toate celulele situate de-a lungul verticalelor, orizontalelor și ambelor diagonale.

O generalizare a problemei este de a plasa matcile în același mod pe un câmp dreptunghiular arbitrar, în special unul pătrat cu latura .

Formulare

Strict matematic, problema poate fi formulată în mai multe moduri, de exemplu, după cum urmează: „Umpleți matricea cu zerouri și unu în așa fel încât suma tuturor elementelor matricei să fie egală cu 8, în timp ce suma dintre elementele din orice coloană, rând sau rând diagonal al matricei nu depășesc unu.”

Scopul final stabilit pentru rezolvarea problemei poate fi formulat în mai multe moduri:

• Construiți orice soluție la problemă.
• Demonstrați analitic că există o soluție .
• Determinați numărul de soluții.
• Construiți toate soluțiile posibile.
• Scrieți un program de calculator care găsește toate soluțiile posibile la o problemă. Una dintre sarcinile tipice pentru programarea algoritmilor de enumerare .

Uneori, formularea problemei necesită găsirea unor modalități de aranjare a matcilor pe tabla de celule (rețineți că pentru problema nu are soluție).

Caracteristicile soluției

Numărul total de aranjamente posibile de 8 matci pe o tablă de 64 de celule este ( formula combinație ). Numărul total de aranjamente posibile care satisfac condițiile problemei este de 92. Setul acestor 92 de aranjamente este împărțit în 12 subseturi (11 subseturi a câte 8 aranjamente fiecare și unul dintre cele patru rămase), în fiecare dintre care toate aranjamentele sunt obținute unul de celălalt prin transformări de simetrie: reflexii din axele verticale și orizontale, reflexii din diagonalele plăcii și rotații cu 90, 180 și 270 de grade.

Calculatoarele moderne permit deja rezolvarea problemei (găsirea oricăreia sau a tuturor soluțiilor) prin enumerarea exhaustivă a tuturor opțiunilor de aranjare posibile, dar o astfel de soluție este de obicei considerată incorectă: soluționătorul problemei trebuie să găsească un algoritm care ar reduce semnificativ cantitatea de enumerare. . De exemplu, este evident că nu poate exista mai mult de o matcă pe o tablă orizontală sau verticală, deci algoritmul de soluție nu ar trebui să includă inițial în căutare pozițiile în care două matci sunt pe aceeași orizontală sau verticală. Chiar și o regulă atât de simplă poate reduce semnificativ numărul de locații posibile: în loc de 4 426 165 368 . Prin generarea de permutări care sunt soluții la problema celor opt turnuri și apoi verificând atacurile de-a lungul diagonalelor, putem reduce numărul de aranjamente posibile la doar . Dacă, la generarea pozițiilor, se ia în considerare și condiția de atac în diagonală, atunci viteza de numărare crește cu un ordin de mărime și numărul de cicluri pentru rezolvarea problemei va fi 4022.

Unul dintre algoritmii tipici pentru rezolvarea problemei este folosirea backtracking -ului : prima matca este asezata pe prima orizontala, apoi fiecare urmatoare este asezata pe urmatoarea astfel incat sa nu fie batuta de matcile stabilite anterior. Dacă în următoarea etapă de setare nu există câmpuri libere, are loc un pas înapoi - dama stabilită anterior este rearanjată.

Note

Link -uri

• Rezolvarea fractală a problemei pentru plăci dacă N=(a1)•(a2)•…•(an), unde a1 ≥ 4 și a2,…,an > 4 (A. Ermakov, 2011)
• Metoda generică n queens cu implementare java