Problema damelor

De la Wikipedia, enciclopedia liberă
abcdefgh
8
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
Singura soluție simetrică la problema celor opt dame (cu excepția rotațiilor și reflexiilor proprii).

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.[1]

Istoria[modificare | modificare sursă]

Compozitorul de șah⁠(d) Max Bezzel⁠(d) a publicat problema celor opt regine în 1848. Franz Nauck a publicat primele soluții în 1850.[2] 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. J. W. L. Glaisher⁠(d) 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[modificare | modificare sursă]

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ă.

Martin Richards⁠(d) a publicat un program ce numără soluțiile pentru problema cu n dame cu ajutorul operațiilor la nivel de bit⁠(d).[3]

Soluții[modificare | modificare sursă]

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ă nu există trei dame coliniare⁠(d).

Soluțiile explicite[modificare | modificare sursă]

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ă.[4] 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.

  1. 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.
  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.
  3. 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:

  1. 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.
  2. Altfel, se scriu liste separate de numere pare și impare (adică 2, 4, 6, 8 — 1, 3, 5, 7).
  3. Dacă restul este 2, se schimbă 1 și 3 lista impară și se mută 5 la final (adică 3, 1, 7, 5).
  4. 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).
  5. 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[modificare | modificare sursă]

Tabelul următor prezintă numărul de soluții pentru plasarea a n regine pe o tablă n × n, atât al celor fundamentale Șirul A002562 la Enciclopedia electronică a șirurilor de numere întregi (OEIS) cât și total Șirul A000170 la Enciclopedia electronică a șirurilor de numere întregi (OEIS), pentru n=1-10, 24-27.

n: 1 2 3 4 5 6 7 8 9 10 ... 24 25 26 27
fundamentale: 1 0 0 1 2 1 6 12 46 92 ... 28.439.272.956.934 2,7598668374343 × 1014 2,7897124665103 × 1015 2,9363791967678 × 1016
toate: 1 0 0 2 10 4 40 92 352 724 ... 2,2751417197374 × 1014 2,2078934358084 × 1015 2,2317699616364 × 1016 2,3490796715412 × 1017

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.[5] Găsirea unei soluții unice pentru o tablă mai mare nu este însă dificilă.

Probleme asociate[modificare | modificare sursă]

  • 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.[6]
  • 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.
Î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.[7] Î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.
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.
Să se pună m dame și m cai pe o tablă n×n, astfel încât nicio piesă să nu o atace pe alta.
Î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.[8]
Î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[modificare | modificare sursă]

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 programarea cu constrângeri⁠(d), programarea logică⁠(d) 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 căutării cu forța brută⁠(d), 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. Un algoritm rezolvă problema a opt ture prin generarea de permutări ale numerelor de la 1 la 8 (care sunt 8! = 40320), și utilizează elementele din fiecare permutare ca indici pentru plasarea unei regine pe fiecare rând. Apoi se resping acele table cu poziții care se atacă pe diagonală. Programul de căutare în adâncime prin backtracking, o ușoară îmbunătățire a metodei cu permutări, construiește un arbore de căutare⁠(d) considerând o linie a tablei la un moment dat, eliminând majoritatea pozițiilor care nu duc la soluții din stadii foarte timpurii în construcția lor. Deoarece respinge atacurile de tip tură și în diagonală chiar și pe configurații incomplete, ea analizează numai 15720 de plasări de regine. O îmbunătățire suplimentară, care examinează doar 5508 de plasamente posibile, este de a combina metoda bazată pe permutare cu metoda tăierii timpurii: permutările sunt generate întâi în adâncime, și spațiul de căutare este tăiat dacă permutarea parțială produce un atac pe diagonală. Programarea pe constrângeri⁠(d) poate fi și ea foarte eficientă la această problemă.

min-conflicte soluție pentru 8 regine

O alternativă la căutarea exhaustivă este un algoritm de „reparare iterativă”, care, de obicei, începe cu toate reginele pe tablă, de exemplu cu o regină pe fiecare coloană.[9] Apoi, el contorizează numărul de conflicte (atacuri), și folosește o euristică pentru a determina modul de a îmbunătăți plasarea reginelor. 'Minim-conflicte⁠(d)' euristică⁠(d) — mutarea piesei cu cel mai mare număr de conflicte pe pătratul de pe aceeași coloană în care numărul de conflicte este minim — este deosebit de eficientă: se găsește o soluție la problema a 1.000.000 de regine în medie în mai puțin de 50 de pași. Aceasta presupune că configurația inițială este „destul de bună” — dacă un milion de regine stau pe același rând, este evident că va fi nevoie de cel puțin 999.999 pași. Un punct de plecare „destul de bun” poate fi găsit, de exemplu, punând fiecare regină pe propriul său rând și coloană, astfel încât să intre în conflict cu cel mai mic număr de regine deja aflate pe tablă.

Spre deosebire de căutarea cu revenire descrisă mai sus, „repararea iterativă” nu garantează o soluție: ca toate procedurile de tip urcarea dealului (de exemplu, greedy) se poate ajunge la blocaj într-un optim local (caz în care algoritmul poate fi reluat cu o altă configurație inițială). Pe de altă parte, se pot rezolva probleme de dimensiuni cu câteva ordine de mărime mai mari decât domeniul de aplicare al căutării în adâncime.

Animația ilustrează abordarea backtracking de rezolvare a problemei. O regină este plasată într-o coloană care se știe că nu va provoca un conflict. Dacă nu se găsește o coloană, programul revine la ultima stare bună și apoi încearcă o altă coloană.

Exemplu de program[modificare | modificare sursă]

Mai jos este redat un program scris în Pascal de Niklaus Wirth în 1976.[10] El găsește o soluție a problemei celor opt regine.

program eightqueen1(output);
 
var i : integer; q : boolean;
    a : array[ 1 .. 8] of boolean;
    b : array[ 2 .. 16] of boolean;
    c : array[ -7 .. 7] of boolean;
    x : array[ 1 .. 8] of integer;
 
procedure try( i : integer; var q : boolean);
    var j : integer;
    begin 
    j := 0;
    repeat 
        j := j + 1; 
        q := false;
        if a[ j] and b[ i + j] and c[ i - j] then
            begin 
            x[ i    ] := j;
            a[ j    ] := false; 
            b[ i + j] := false; 
            c[ i - j] := false;
            if i < 8 then
                begin
                try( i + 1, q);
                if not q then
                    begin 
                    a[ j] := true; 
                    b[ i + j] := true; 
                    c[ i - j] := true;
                    end
                end 
            else 
                q := true
            end
    until q or (j = 8);
    end;
 
begin
for 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
    for i := 1 to 8 do write( x[ i]:4);
writeln
end.

Referințe[modificare | modificare sursă]

  1. ^ E. J. Hoffman et al., "Construction for the Solutions of the m Queens Problem".
  2. ^ W. W. Rouse Ball⁠(d) (1960) "The Eight Queens Problem", in Mathematical Recreations and Essays, Macmillan, New York, pp. 165–171.
  3. ^ Martin Richards.
  4. ^ Explicit Solutions to the N-Queens Problem for all N, Bo Bernhardsson (1991), Departamentul de Automatică, Lund Institute of Technology, Suedia.
  5. ^ The Q27 Project
  6. ^ J. Barr and S. Rao (2006), The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, vol 61 (4), pp. 133–137.
  7. ^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, George Pólya: Collected papers Vol.
  8. ^ O. Demirörs, N. Rafraf, and M.M. Tanik.
  9. ^ A Polynomial Time Algorithm for the N-Queen Problem by Rok Sosic and Jun Gu, 1990.
  10. ^ Wirth, 1976, p. 145

Lectură suplimentară[modificare | modificare sursă]

  • Bell, Jordan; Stevens, Brett (). „A survey of known results and research areas for n-queens”. Discrete Mathematics. 309 (1): 1–31. doi:10.1016/j.disc.2007.12.043.  Mai multe valori specificate pentru |DOI= și |doi= (ajutor)
  • Watkins, John J. (). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6. 
  • O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN: 0-12-200550-3 see pp 72–82 for Dijkstra's solution of the 8 Queens problem.
  • Allison, L.; Yee, C.N.; McGaughey, M. (). „Three Dimensional NxN-Queens Problems”. Department of Computer Science, Monash University, Australia.  Mai multe valori specificate pentru |nume= și |last1= (ajutor); Mai multe valori specificate pentru |first1= și |first= (ajutor)
  • Nudelman, S. (). „The Modular N-Queens Problem in Higher Dimensions”. Discrete Mathematics. 146 (1-3): 159–167. doi:10.1016/0012-365X(94)00161-5.  Mai multe valori specificate pentru |DOI= și |doi= (ajutor)
  • Engelhardt, M. (august 2010). „Der Stammbaum der Lösungen des Damenproblems (in German, means The pedigree chart of solutions to the 8-queens problem”. Spektrum der Wissenschaft: 68–71. 
  • On The Modular N-Queen Problem in Higher Dimensions, Ricardo Gomez, Juan Jose Montellano and Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexico.
  • Wirth, Niklaus (), Algorithms + Data Structures = Programs⁠(d), Prentice-Hall, ISBN 0-13-022418-9  Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)

Legături externe[modificare | modificare sursă]

Adus de la https://ro.wikipedia.org/w/index.php?title=Problema_damelor&oldid=15191684