Problema damelor (sau problema reginelor) tratează plasarea a opt regine de șah pe o tablă de șah astfel încât să nu existe două regine care se amenință reciproc. Astfel, se caută o soluție astfel încât nicio pereche de două regine să nu fie pe același rând, pe aceeași coloană, sau pe aceeași diagonală. Problema cu opt regine este doar un caz particular pentru problema generală, care presupune plasarea a n regine pe o tablă de șah n×n în aceleași condiții. Pentru această problemă, există soluții pentru toate numerele naturale n cu excepția lui n=2 și n=3.E. J. Hoffman et al., "Construction for the Solutions of the m Queens Problem".
Istoria a publicat problema celor opt regine în 1848. Franz Nauck a publicat primele soluții în 1850. (1960) "The Eight Queens Problem", in Mathematical Recreations and Essays, Macmillan, New York, pp. 165–171. Nauck a și extins problema la n regine, cu n regine pe o tablă de șah de n × n pătrate.
De atunci, mulți matematicieni, inclusiv Carl Friedrich Gauss, au lucrat atât la problema inițială cu opt regine cât și la varianta generalizată cu n regine. În 1874, S. Gunther a propus o metodă care utilizează determinanții pentru a găsi soluții. a rafinat abordarea lui Gunther.
În 1972, Edsger Dijkstra a folosit această problemă pentru a ilustra puterea a ceea ce el numește programare structurată. El a publicat o descriere foarte detaliată a unui algoritm backtracking de parcurgere în adâncime.2
Construcția soluției Problema poate fi destul de costisitoare computațional, întrucât sunt 4426165368 (adică, 64C8) aranjamente posibile ale celor opt regine pe o tablă 8×8, dar numai 92 de soluții. Se pot utiliza scurtături care reduc cerințele de calcul, sau reguli aproximative, care evită căutarea cu forța brută. De exemplu, aplicând o regulă simplă, care constrânge fiecare regină să stea pe coloana (sau rândul) ei, deși încă se consideră că se folosește forța brută, se poate reduce numărul de posibilități la 16777216 (88) combinații posibile. Generarea de permutări reduce și mai mult posibilitățile la 40320 (adică 8!), care sunt apoi verificate dacă damele nu se atacă pe diagonală.
a publicat un program ce numără soluțiile pentru problema cu n dame cu ajutorul .Martin Richards.
Soluții Problema cu opt regine are 92 de soluții distincte. Daca soluțiile care diferă numai prin operațiunile de simetrie (rotație și reflexie a tablei) sunt considerate a fi una singură, problema are 12 soluții. Acestea sunt numite soluții fundamentale; mai jos sunt prezentate reprezentante ale fiecăreia.
O soluție fundamentală are, de obicei, opt variante (inclusiv forma sa originală) obținute prin rotirea cu 90, 180 sau 270° și apoi reflexia fiecăreia dintre cele patru variante într-o oglindă într-o poziție fixă. Cu toate acestea, dacă o soluție este echivalentă cu propria rotire la 90° (cum se întâmplă cu o soluție cu cinci regine pe o tablă 5×5), ca soluție fundamentală va avea doar două variante (ea însăși și reflexia sa). Dacă o soluție este echivalentă cu propria rotație la 180° (dar nu cu rotația la 90°), va avea patru variante (ea însăși și reflexia sa, rotirea la 90° și reflexia sa). Dacă n > 1, nu este posibil ca o soluție să fie echivalentă cu propria reflexie pentru că aceasta ar impune ca două regine să fie una în fața alteia. Din cele 12 soluții fundamentale la problema cu opt regine pe o tablă 8×8, exact una (soluția 12 de mai jos) este egală cu propria rotație la 180°, și niciuna nu este egală cu rotația la 90°; astfel, numărul de soluții distincte este 11×8 + 1×4 = 92 (unde 8 rezultă din cele patru poziții de rotație la 90° și reflexiile lor, iar 4 rezultă din două poziții de rotație la 180° și reflexiile lor).
Soluția 10 are proprietatea suplimentară că .
Soluțiile explicite Acești algoritmi cu forță brută de numărare a soluțiilor sunt tratabile computațional pentru n = 8, dar ar fi greu de rezolvat pentru probleme de n ≥ 20, ca de 20! = 2.433 × 1018. În cazul în care obiectivul este de a găsi o soluție unică, atunci există soluții explicite pentru orice n ≥ 4, care nu necesită căutare combinatorică.Explicit Solutions to the N-Queens Problem for all N, Bo Bernhardsson (1991), Departamentul de Automatică, Lund Institute of Technology, Suedia. Soluțiile explicite prezintă modele în trepte, ca în următoarele exemple pentru n = 8, 9 și 10:
Exemplele de mai sus pot fi obținute cu ajutorul următoarelor formule. Fie (i, j) pătratul de pe coloana i și linia j a unei table de șah n × n, și k un număr întreg. Dacă n este par și n ≠ 6k + 2, atunci se pun dame în (i, 2i) și (n/2 + i, 2i - 1) pentru i = 1, 2, ..., n / 2. Dacă n este par și n ≠ 6k, atunci se pun dame în (i, 1 + (2i + n/2 - 3 (mod n))) și (n + 1 - i, n - (2i + n/2 - 3 (mod n))) pentru i = 1, 2, ..., n / 2. Dacă n este impar, atunci se folosește unul dintre modelele de mai sus pentru (n − 1) și se adaugă o damă în (n, n). O altă abordare este: Dacă restul de la împărțirea lui N la 6 nu este 2 sau 3, atunci lista este pur și simplu toate numere pare urmate de toate numerele impare mai mici sau egale cu N. Altfel, se scriu liste separate de numere pare și impare (adică 2, 4, 6, 8 — 1, 3, 5, 7). Dacă restul este 2, se schimbă 1 și 3 lista impară și se mută 5 la final (adică 3, 1, 7, 5). Dacă restul este 3, se mută 2 la finalul listei pare și 1,3 la sfârșitul listei impare (adică 4, 6, 8, 2 — 5, 7, 1, 3). Se adaugă lista impară la cea pară și se pun damele pe rândurile date de aceste numere, de la stânga la dreapta (adică a2, b4, c6, d8, e3, f1, g7, h5). Pentru N = 8 aceasta lucru duce la soluția fundamentală 1 de mai sus. Alte câteva exemple. 14 dame (restul 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5. 15 dame (restul 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3. 20 dame (restul 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.
Numărarea soluțiilor Tabelul următor prezintă numărul de soluții pentru plasarea a n regine pe o tablă n × n, atât al celor fundamentale cât și total , pentru n=1-10, 24-27. n:12345678910...24252627fundamentale:1001216124692...toate:10021044092352724... Se observă că problema cu șase dame are mai puține soluții decât cea cu cinci.
În prezent, nu există o formulă cunoscută pentru numărul exact de soluții, și nici măcar pentru un comportament asimptotic. În prezent, cea mai mare tablă ale cărei soluții au fost complet enumerate este 27x27.The Q27 Project Găsirea unei soluții unice pentru o tablă mai mare nu este însă dificilă.
Probleme asociate Dimensiuni mai mari Găsirea unei configurații de regine care nu se atacă reciproc pe o tablă d-dimensională de dimensiune n. În unele dimensiuni superioare se pot pune mai mult de n regine (cel mai mic exemplu este un spațiu de șah tridimensional 3 × 3 × 3 în care se pot pune patru regine), și se știe că, pentru orice k, există dimensiuni mai mari unde nk regine nu sunt suficiente pentru a ataca toate spațiile.J. Barr and S. Rao (2006), The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, vol 61 (4), pp. 133–137. Folosirea altor piese decât dame Pe o tablă 8×8 se pot pune 32 de cai, 14 nebuni, 16 regi sau opt ture, astfel încât două piese să nu se atace reciproc. Reginele au mai fost înlocuite și cu piese de șah neconvenționale. În cazul cailor, o soluție simplă este de a plasa câte un cal pe fiecare pătrat de o anumită culoare, deoarece ei se mișcă numai pe culoarea opusă. Soluția este ușoară și pentru ture și regi. Opt ture pot fi plasate de-a lungul unei diagonale lungi (printre mii de alte soluții), și 16 regi se plasează împărțind tabla în subpătrate 2 pe 2 și punând regi în punctele echivalente de pe fiecare pătrat. Matricea de permutare În matematică, o matrice de permutare poate fi privită din punct de vedere geometric, ca o mulțime de n puncte situate pe pătratele unei table de șah nxn, astfel încât fiecare rând sau coloană conține doar un singur punct. Astfel, o permutare a unei matrice de ordin-n este o soluție pentru problema celor n ture. Table nestandard Pólya a studiat problema celor n regine pe o tablă toroidală („în formă de gogoașă”) și a arătat că nu există o soluție pe o tablă n×n dacă și numai dacă n nu este divizibil cu 2 sau 3.G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, George Pólya: Collected papers Vol. În 2009, Pearson și Pearson au populat algoritmic table tridimensionale (n×n×n) cu n2 dame, și au avansat ipoteza că multiplii acestora pot genera soluții pentru o versiune tetradimensională a problemei. Dominare Se dă o tablă n×n, și se definește numărul de dominare ca fiind numărul minim de dame (sau alte piese) necesare pentru a ataca sau a ocupa toate pătratele. Pentru n=8, numărul de dominare cu dame este 5. Problema celor nouă regine Se pun nouă regine și un pion pe o tablă 8×8 în așa fel încât reginele să nu se atace reciproc. O generalizare a problemei (cu soluția completă încă necunoscută): se dă o tablă de șah n×n și m > n regine; să se găsească numărul minim de pioni, astfel încât m regine și pionii respectivi să poată fi așezate pe tablă în așa fel încât să nu existe două regine care se atacă reciproc. Problema damelor și cailor Să se pună m dame și m cai pe o tablă n×n, astfel încât nicio piesă să nu o atace pe alta. Pătrate magice În 1992, Demirörs, Rafraf, și Tanik au publicat o metodă de conversie a unor pătrate magice în soluții ale problemelor celor n dame, și vice-versa.O. Demirörs, N. Rafraf, and M.M. Tanik. Pătratele latine Într-o matrice n×n, se pune fiecare număr de la 1 la n în n locații din matrice, astfel încât să nu existe două instanțe ale aceleiași cifre pe același rând sau coloană.
Se consideră o matrice cu o coloană primară pentru fiecare din cele n coloane ale tablei, o coloană primară pentru fiecare din cele n linii, și o coloană secundară pentru fiecare din cele 4n − 6 de diagonale triviale de pe tablă. Matricea are n2 rânduri: unul pentru fiecare plasament posibil al unei regine, și fiecare linie are un 1 pe coloanele corespunzătoare pentru fiecare rând, coloană și diagonală și 0 în toate celelalte coloane. Atunci problema celor n regine este echivalentă cu alegerea unei submulțimi de rânduri din această matrice astfel încât fiecare coloană primară să aibă un 1 în exact unul dintre rândurile alese și fiecare coloană secundară are un 1 în cel mult unul din rândurile alese; acesta este un exemplu de problemă generalizată a acoperirii exacte; alt exemplu de astfel de problemă este sudoku.
Exercițiu de proiectare de algoritm Găsirea de soluții pentru problema celor opt regine este un bun exemplu de joc simplu, dar netrivial. Din acest motiv, adesea este folosită ca exemplu de problemă pentru diverse tehnici de programare, inclusiv abordări netradiționale, cum ar fi, sau algoritmii genetici. De cele mai multe ori, este folosit ca un exemplu de problemă care poate fi rezolvată cu un algoritm recursiv, formulând problema celor n regine inductiv în ceea ce privește adăugarea unei singure regine la orice soluție a problemei plasării a n−1 regine pe o tablă n x n. Inducția se limitează cu problema plasării a 0 regine pe o tablă de șah, a cărei soluție este tabla goală.
Această tehnică este mult mai eficientă decât algoritmul naiv al , care consideră toate cele 648 = 248 = 281474976710656 distribuții posibile ale celor opt regine, și apoi le filtrează pentru a elimina toate așezările în care două regine sunt fie pe aceeași pătrat (lăsând doar 64!/56! = 178,462,987,637,760 posibile distribuții) fie pe poziții care se atacă reciproc. Printre altele, acest algoritm foarte prost va produce aceleași rezultate în mod repetat, în toate permutările diferite a opt regine, și va repeta aceleași calcule de mai multe ori pentru submulțime diferită a fiecărei soluții. Un algoritm de forță brută mai bun pune o singură regină pe fiecare rând, apoi face doar 88 = 224 = 16.777.216 așezări.
Se poate însă și mai bine decât așa.