Problema opt doamne

Obiectul problemei celor opt dame este de a plasa opt dame dintr-un joc de șah pe o tablă de șah pătrată de 8 × 8 fără ca dame să se poată amenința reciproc, în conformitate cu regulile jocului de șah (culoarea pieselor a fi ignorat). Prin urmare, două doamne nu ar trebui să împartă niciodată același rând, coloană sau diagonală. Această problemă aparține domeniului problemelor matematice și nu celui al compoziției șahului .

Simplă, dar nu trivială, această problemă este adesea folosită ca exemplu pentru a ilustra tehnicile de programare .

Istorie

De ani de zile, mulți matematicieni , inclusiv Gauss , au lucrat la această problemă, care este un caz particular al problemei generalizate a n -dames, pusă în 1850 de Franz Nauck și care este de a plasa n doamne „libere” pe o tablă de șah. n × n cutii. În 1874, S. Gunther a propus o metodă de găsire a soluțiilor folosind determinanți , iar JWL Glaisher a rafinat această abordare.

Această problemă a fost utilizată la începutul anilor 1990 în jocul de pe PC The 7th Guest ( al șaptelea invitat ).

Soluțiile

Problema celor opt dame are 92 de soluții distincte sau doar 12 soluții luând în considerare transformări precum rotații sau reflexii (prin lema lui Burnside ). Rețineți că una dintre soluțiile remarcabile, indiferent de dimensiunea tabloului de șah, este aceea

Fiecare regină are simetria sa într-o coloană alăturată, cu excepția celor 2 care ating axa orizontală de simetrie a tabloului de șah (Soluția unică 5)

Variante

Cu diferite părți

Patruzeci de episcopi , treizeci și doi de călăreți sau șaisprezece regi pot fi aranjați pe o tablă de șah tradițională, fără ca nicio piesă să o amenințeze pe alta. Piesele de șah de zână pot înlocui doamnele.

Cu diferite table de șah

Pólya a studiat problema n- dame pe o tablă de șah toroidală . Au fost utilizate alte suporturi, cum ar fi tablele de șah tridimensionale.

Problema dominatiilor

Problema este de a găsi numărul minim de regine (sau alte piese) necesare pentru a controla toate pătratele unui n × n tablă de șah . De exemplu, pentru o tablă de șah "8 × 8", acest număr valorează cinci.

Problema celor nouă doamne

Încercăm să așezăm nouă regine și un pion pe o tablă de șah clasică, evitând ca reginele să poată fi prinse. Această problemă este generalizată luând în considerare o tablă de șah n × n și r regine ( r > n ) și este necesar să se găsească numărul minim de pioni, astfel încât reginele și pionii să poată fi așezați pe tabla de șah fără ca reginele să nu se amenințeze reciproc .

Pătrate magice

În 1992, Demirörs, Rafraf și Tanik au publicat o metodă de conversie a pătratelor magice în soluții ale problemei n- dame și invers.

Pătrate latine

Probleme de șah

În informatică

Problema celor opt dame este un bun exemplu de problemă simplă, dar nu evidentă. Din acest motiv, este adesea folosit ca implementare a diferitelor tehnici de programare, inclusiv abordări netradiționale de programare, cum ar fi programarea constrângerii , logica de programare sau algoritmii genetici .

Cel mai adesea, este folosit ca exemplu de problemă care poate fi rezolvată cu un algoritm recursiv , exprimând că o soluție a problemei n -dames poate fi obținută, prin inducție , din orice soluție a problemei des ( n -1) ) -dames adăugând o doamnă. Recurența începe cu soluția problemei reginei 0, care se sprijină pe o tablă de șah goală.

Această tehnică este mult mai eficientă decât algoritmul naiv de căutare exhaustivă , care parcurge fiecare dintre cele 64 8 = 2 48 = 281 474 976 710 656 posibile plasări ale celor opt regine, pentru a elimina toate cele pentru care mai multe regine sunt pe același pătrat. (lăsând doar 178.462.987 637.760 aranjamente posibile) sau pentru care doamnele se amenință reciproc. $A _ {{64}} ^ {8} = 64! / 56! =$

În ceea ce privește complexitatea algoritmică , acest algoritm foarte „rău” va produce aceleași rezultate de mai multe ori prin atribuirea de locuri diferite celor opt doamne și va repeta aceleași calcule de mai multe ori pentru diferite părți ale fiecărei soluții. Un algoritm de căutare exhaustiv ușor mai bun plasează o singură regină pe rând, reducând la doar 8 8 = 2 24 = 16 777 216 destinații de plasare posibile.

Este posibil să te descurci mult mai bine. De exemplu, un program de cercetare aprofundat ar analiza doar 15.720 posibile plasări de dame, construind un arbore de cercetare și parcurgând rândurile tabloului de șah unul câte unul, eliminând majoritatea pozițiilor posibile într-un stadiu foarte primitiv al construcției lor. .

Programare constrângere este mult mai eficientă pentru această problemă. Un algoritm de „reparații iterative” pornește de obicei de la plasarea tuturor reginelor pe tablă de șah, de exemplu, cu o singură regină pe coloană. Apoi numără numărul conflictelor dintre dame și folosește o metodă euristică pentru a determina cum să îmbunătățească plasarea damei. Metoda euristică a celui mai mic conflict, care constă în mutarea părții cu cel mai mare număr de conflicte, în aceeași coloană într-un loc în care numărul conflictelor este cel mai mic, este deosebit de eficientă. Rezolvă problema a milioane de dame (pe o tablă de șah de 1.000.000 × 1.000.000 de pătrate) în mai puțin de 50 de pași în medie .

Obținerea acestei medii în 50 de pași presupune că configurarea inițială este rezonabilă. Dacă la început un milion de dame sunt plasate în același rând, algoritmul va face evident mai mult de 50 de pași pentru a rezolva problema. Un punct de plecare „rezonabil de bun” este plasarea fiecărei regine într-o coloană astfel încât să intre în conflict cu cele mai puține regine care se află deja pe tablă.

Metoda de reparație iterativă, spre deosebire de cercetările aprofundate descrise mai sus, nu garantează o soluție. La fel ca toate metodele de coborâre mai profundă, se poate bloca pe un extremum local (în acest caz algoritmul poate fi repornit cu o configurație inițială diferită.) Pe de altă parte, poate rezolva probleme mari. -cercetări adânci.

Note și referințe

Note

Uneori denumită problema celor opt regine prin traducere din engleză, deși numele acestei piese este Dame în franceză.
Termenul problemă este pus aici între ghilimele, deoarece este într-adevăr o problemă în sensul general al termenului, dar nu o problemă de șah în sensul compoziției șahului . Într-adevăr, această problemă nu a fost compusă și nu are autor. Mai mult, el nu are o singură soluție, dar în acest ultim punct, ar fi suficient să-și schimbe afirmația cerând să găsească numărul de soluții și ar putea fi apoi plasat în categoria problemelor de șah matematic.

Referințe

Jean-Paul Delahaye , „ Logică și calcul: principiul sertarelor ”, Pour la science , n o 433,ianuarie 2018, p. 78.
(în) The 9 Queens Problem pe chessvariants.org
(în) O. Demirörs N. Rafraf, domnul Tanik , „ Obținerea de soluții n regine din pătrate magice și Construirea pătratelor magice din soluții n-regine ” , Journal of Recreational Mathematics , Vol. 24,1992, p. 272-280

Anexe

Bibliografie

Édouard Lucas , Recreații matematice , vol. 1, Gauthier Villars,1882, "Recreere nr. 4: Problema celor opt regine din jocul de șah"
Watkins, John J. (2004). De ansamblu: Matematica problemelor de șah . Princeton: Princeton University Press. ( ISBN 0-691-11503-6 ) .

Articole similare

Link extern

(ro) Problema N-Queens în Codul Rosetta