de Sachin Malhotra

Să revenim și să salvăm câteva regine

Sa revenim si sa salvam cateva regine
https://derickbailey.com/wp-content/uploads/2015/01/recursion1.jpg

Acesta este un titlu ciudat, care probabil nu are sens chiar acum. Dar credeți-mă, acesta este un post destul de lung și este foarte distractiv!

Ce este Backtracking-ul?

Backtracking este o tehnică standard de rezolvare a problemelor bazată pe recursivitate.

Un algoritm de backtracking încearcă să construiască o soluție la o problemă de calcul în mod incremental. Ori de câte ori algoritmul trebuie să decidă între mai multe alternative la următoarea componentă a soluției, pur și simplu încearcă recursiv toate opțiunile posibile.

Căutare în adâncime (DFS) folosește conceptul de backtracking chiar la bază. Deci, în DFS, încercăm practic să explorăm recursiv toate căile de la nodul dat până când atingem obiectivul. După ce explorăm o anumită ramură a unui copac din DFS, putem ateriza în două stări posibile.

  • Am găsit starea obiectivului, caz în care pur și simplu ieșim.
  • Or, nu am găsit starea obiectivului și am lovit o fundătură. În acest scenariu, noi revenire la ultimul punct de control și apoi încercăm o ramură diferită.

Pentru introducerea detaliată a algoritmului Depth First Search, treceți prin

Scufundare profundă printr-un grafic: DFS Traversal
În bine sau în rău, există întotdeauna mai multe modalități de a face ceva. Din fericire pentru noi, în lumea software-ului și …medium.com

și pentru o introducere detaliată a backtracking-ului și recursivității în general, consultați următoarele două articole.

Backtracking explicat
Backtracking-ul este unul dintre algoritmii mei preferați datorită simplității și eleganței sale; nu are întotdeauna mare …medium.comCum funcționează recursiunea – explicat cu diagrame și un videoclip
„Pentru a înțelege recursivitatea, trebuie mai întâi să înțelegem recursivitatea.”medium.freecodecamp.org

Acum, că suntem cu toții profesioniști în retragere și recursivitate, să vedem ce legătură au „reginele” cu toate acestea.

Faimoasa problemă N-Queens

Poziționarea reginelor pe o tablă de șah este o problemă clasică în matematică și informatică.

Puzzle-ul reginei (alias puzzle-ul celor opt regine), a fost publicat inițial în 1848. Aceasta implică plasarea a opt regine pe o tablă de șah 8×8, în așa fel încât să nu se poată ataca două regine.

Regina se întâmplă să fie cea mai puternică piesă de pe tablă de șah, în primul rând datorită libertății de mișcare pe care o are.

Regina se poate deplasa în 8 direcții diferite, așa cum este ilustrat în imaginea de mai jos:

1611278530 77 Sa revenim si sa salvam cateva regine
8 direcții pentru mișcarea reginei.

Această libertate de mișcare face ca problema N-Queens să fie extrem de grea.

Mai jos este o scurtă prezentare generală a modului în care progresează restul acestui articol. Vom discuta 4 algoritmi diferiți pentru a rezolva problema:

  • Soluția Brute Force.
  • Soluție bazată pe backtracking.
  • Soluție bazată pe permutații.
  • În cele din urmă, soluția aparent nebună folosind Bit Magic.

Aș recomanda cu tărie să citiți soluțiile în această ordine. Cu toate acestea, nu ezitați să ignorați o soluție dacă sunteți deja familiarizat cu ea.

Întregul cod pentru soluțiile discutate mai jos este disponibil aici.

Soluția Forței Brute

while there is life on earth:    try a possible arrangement of queens.
1611278531 489 Sa revenim si sa salvam cateva regine
https://i.ytimg.com/vi/keCgNXlq3Vo/maxresdefault.jpg

Avem o tablă de șah 8×8, ceea ce înseamnă că avem 64 de locuri diferite pentru a amplasa reginele. Trebuie să calculăm C (64, 8) sau numărul de combinații din 64 de obiecte, luate câte 8 pe rând.

C(n,r) = n! / (r!(n−r)!)

Ne deplasăm 4,5 miliarde de combinații diferite de plasare a celor 8 regine pe o tablă de șah 8×8.

Algoritmul forței brute este după cum urmează:

while there are untried configurations{   generate the next configuration   if queens don't attack in this configuration then   {      print this configuration;   }}

Este o mulțime de permutări pentru a căuta un procesor standard. Am putea folosi un fel de soluție multi-procesare (deoarece verificarea unei permutări este independentă de alta).

Dar de ce să facem asta când avem algoritmi mai buni pentru a rezolva această problemă?

Backtracking

Putem face mai bine decât soluția naivă a forței brute pentru această problemă. Luați în considerare următorul pseudocod pentru soluția bazată pe backtracking:

1) Start in the leftmost column2) If all queens are placed    increment the number of solutions counter and return3) Try all rows in the current column. Do following for every tried row.    a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
    b) If placing queen in [row, column] leads to a solution then   increment the number of solutions counter and return
    c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows.
4) If all rows have been tried and nothing worked, return, to trigger backtracking.

Pseudocodul arată destul de simplu și puteți verifica codul bazat pe python pentru acest lucru aici. Nu voi furniza aici descrierea algoritmului de backtracking.

Aș vrea totuși discuta un optimizare pentru a reduce complexitatea timpului verificării dacă putem plasa o regină într-o celulă de pe tablă.

O parte importantă a algoritmului este aceea în care trebuie să verificăm dacă o regină poate fi plasată într-o celulă [i, j]. Acest pas durează mult. Să ne uităm la o modalitate cu forță brută de a face acest lucru și apoi la o versiune optimizată.

Aceasta are o timp complexitate din O (N), și acest lucru va fi apelat de mai multe ori pentru fiecare celulă de pe tablă.

Cu toate acestea, putem folosi câteva structuri de date suplimentare pentru a accelera verificarea validității plasării unei regine pe o celulă [i, j]. Acest lucru va reduce complexitatea O(1) – cu alte cuvinte, timp constant. Aceasta este o reducere imensă !.

Punctele cheie din această bucată de cod sunt următoarele:

  • Toate elementele dintr-o anumită diagonală (de la stânga sus la dreapta jos) au aceeași valoare pentru row — column .
  • Toate elementele dintr-o anumită anti-diagonală (de la dreapta sus la stânga jos) au aceeași valoare pentru row + column .

Această optimizare scade isSafe complexitate la O(1). Hurra?

Acum că am terminat cu algoritmii de bază pentru N-Queens. Să trecem la unele mai complicate, care rulează mult mai repede decât cele descrise mai sus.

Permutații și N-Regine

Ideea din spatele acestui algoritm este destul de simplă. Luați în considerare următoarele fapte despre plasarea fiecărei regine:

  • Nu putem așeza decât o singură regină la rând.
  • Același lucru se poate spune pentru fiecare coloană.
  • Aceasta înseamnă că toate soluțiile de succes vor fi doar permutări ale indexurilor coloanei.
  • Fiecare rând succesiv are o poziție mai puțină candidată pentru ca regina să fie plasată.

Mergând după această logică, spațiul problematic se reduce la doar 8! = 40.320.

Acest lucru oferă mult mai puține opțiuni pentru a încerca și a găsi soluțiile pentru problema noastră.

Să ne uităm la pseudo-cod pentru această abordare:

* Start with an initial permutation of the queens lined up along one of the diagonals. 
* To position a queen on row j    * If j has reached N, you have a valid solution. Process it as               valid.    * Loop on k from j to N       * Swap board[j] and board[k].        * Check if a queen can be placed on (row, board[row])           * If yes, then place a queen and recurse for row j+1       * Undo placing a queen on (row, board[row])   * Undo the swaps done.   

Pentru o mai mare claritate, să ne uităm și la cod:

Notă: board[i] stochează numărul coloanei unde a fost plasată o regină în rând i. Prin urmare, valoarea celulei este dată de (i, board[i]).

Această optimizare accelerează foarte mult calculul, datorită spațiului de bord foarte redus de luat în considerare în timpul plasării reginelor.

Accelerarea devine mai proeminentă pe măsură ce creștem dimensiunea plăcii și, prin urmare, numărul de regine care urmează să fie plasate.

De asemenea, verificarea validității pentru o anumită celulă devine mai simplă, deoarece acum trebuie să verificăm doar diagonalele și anti-diagonalele.

Să vedem niște Bit Magic!

Această soluție specială a problemei este ceva care era practic grec pentru mine prima dată când am trecut-o.

Este de înțeles totuși, pentru că hei, este pic magie!

Dar, din fericire, am găsit acest lucru uimitor postare pe blog explicând întregul algoritm linie cu linie. Codul este în JavaScript. Voi descrie același lucru în afară de codul din python. Citește orice post ți se potrivește 🙂

Cea mai bună modalitate de a explica acest algoritm este prin introducerea codului mai întâi?

1611278531 520 Sa revenim si sa salvam cateva regine
http://mymemes.biz/wp-content/uploads/2017/10/meme-magic-59df0f3650800.jpg

Algoritmul funcționează folosind aceeași idee de bază despre care am discutat înainte. Trebuie doar să verificăm trei lucruri înainte de a plasa o regină pe un anumit pătrat:

  1. Coloana pătratului nu are alte regine pe ea
  2. Diagonala stângă a pătratului nu are alte regine pe ea
  3. Diagonala dreaptă a pătratului nu are alte regine pe ea

Codul ar putea arăta ca o cutie neagră care pare să funcționeze. Așa m-am simțit prima dată când am citit această bucată de cod nebun de rapidă.

Să încercăm să o descompunem rând cu rând.

Linia 1

Veți observa că funcția acceptă 4 parametri:

  1. coloană
  2. left_diagonal
  3. dreapta_diagonală
  4. regine_plasate

queens_placed se explică de la sine. Trebuie să urmărim câte regine am plasat până acum pentru ca recursiunea să se termine la un moment dat.

Cele trei variabile column, left_diagonal și right_diagonal sunt practic numere întregi, dar sunt tratate ca o secvență de biți în scopul acestui algoritm. Aceste variabile ne ajută să determinăm pozițiile deschise pe rândul curent pentru a fi plasată o regină.

Să ne uităm la imaginea de mai jos:

  • ld = left_diagonal
  • cols = coloană
  • rd = dreapta_diagonală
Sa revenim si sa salvam cateva regine
http://gregtrowbridge.com/a-bitwise-solution-to-the-n-queens-problem-in-javascript/

Ignorați poss variabilă deocamdată. Vom ajunge la el mai târziu.

Liniile # 2–6

Aceste linii de cod se ocupă pur și simplu de baza pentru recursivitate. Când am plasat N regine de pe placa noastră N by N, incrementăm numărul contorului de soluții și imprimăm soluția dacă semnalizatorul corespunzător a fost setat în timpul rulării (consultați întregul cod pentru acest semnal).

Linia # 8

Aceasta găsește valid_spots rămânând pe rândul curent. Acesta este practic poss variabilă descrisă în imaginea de mai sus.

valid_spots = self.all_ones & ~(column | left_diagonal | right_diagonal)

De exemplu, să spunem că după un număr de iterații avem:

left_diagonal = 00011000column = 11001001 right_diagonal = 00011100

Codul (column | left_diagonal | right_diagonal) face doar o operație „SAU” și se termină cu secvența de biți 11011101.

Apoi, adăugând ~ în fața acelei expresii determină „flip” secvența de biți rezultată (deci toate zero-urile devin unii și invers) și valid_spots ar fi setat la 00100010.

Deci, pentru rândul curent, numărul coloanei 0,1,3,4,5 și 7 nu sunt disponibile. Putem plasa o regină doar pe coloana numărul 2 și 6. Acestea sunt singurele două locuri pe care le vom încerca.

Linia # 10

current_spot = -valid_spots & valid_spots

Această linie găsește primul bit non zero și îl stochează în current_spot. Deci, practic, găsim primul loc gol unde ne putem așeza regina (din coloana din dreapta).

Chiar aici este ceea ce face algoritmul atât de rapid. Am folosit operatorii de biți pentru a ne spune direct pozițiile goale care sunt complet sigure pentru noi să ne plasăm reginele. Prin urmare, acest lucru duce la accelerarea majoră, așa cum veți vedea mai târziu.

Linia # 11 și 12

Linia # 11 adaugă pur și simplu regina fiind plasată la current_spot la setul nostru de soluții, astfel încât să îl putem tipări ulterior.

Linia # 12 marchează current_spot ca indisponibil. Tine minte, XORing aceiași biți duc la 0.

Linia # 13

Aceasta este probabil cea mai importantă linie de cod pentru acest algoritm (și cea mai confuză, de asemenea). Aici doar propagăm efectele pe care le-am introdus, mai jos la rândul următor.

Am plasat o regină la current_spot iar acum vrem să ne actualizăm variabilele column, left_diagonal și right_diagonal pentru a conține aceste modificări pe măsură ce trecem la rândul următor.

self.solve((column | current_spot), (left_diagonal | current_spot)>> 1,(right_diagonal | current_spot) << 1, queens_placed + 1)

NOTĂ: a | b înseamnă SAU în biți pentru variabile a și b. De asemenea, a <<1 este un operator de stânga. Similarly, a >> 1 este operatorul de schimbare dreapta.

Așa că sună (right_diagonal | current_spot) <<1 spune pur și simplu: combine right_diagonal and current_spot cu o operație SAU, apoi mutați totul în rezultat la stânga cu unul.

De exemplu – să spunem right_diagonal a avut valoare 00011100. Și spunem că am făcut-o pe regină să ocupe ultimul slot, cum ar fi ultimul 1 din valid_spots întreg 00100010.

Apoi current_spot ar deveni 000000010 și OR-ing cu right_diagonal ne-ar da 00011110. Am schimbat-o la stânga pentru a obține 00111100 și acesta este exact efectul pe care îl dorim pentru diagonala dreaptă.

Diagonala dreaptă se deplasează de la dreapta sus în jos stânga. Deplasarea la stânga pe biți produce acel efect.

Pentru o mai mare claritate, încercați să efectuați această operație pe o hârtie:

Sa revenim si sa salvam cateva regine
Doar pentru a nu fi nevoie să urcați articolul?

Începem cu 0 pentru toate cele trei variabile, ceea ce înseamnă că toate pozițiile sunt disponibile în primul rând pentru plasarea reginelor.

Acum vine partea distractivă (bine, ceva care să te uimească?), Speed ​​Comparisons.

Statistici

Să analizăm statisticile pentru un instrument creat de Google pentru rezolvarea N-Queens.

1611278532 110 Sa revenim si sa salvam cateva regine
https://developers.google.com/optimization/cp/queens

Următoarele sunt statisticile pentru cele 4 abordări diferite pe care le-am discutat pentru
N-Regine:

1611278533 630 Sa revenim si sa salvam cateva regine
Toate orele sunt în ms.
1611278533 268 Sa revenim si sa salvam cateva regine
Toate orele sunt în ms.

Ultima soluție care implică operatori bit-bit are o performanță mai bună decât rezultatele raportate de Google N-Queens solver. ?

De asemenea, un lucru interesant de remarcat aici este efectul pe care o ușoară optimizare l-a avut asupra rezultatelor. Reamintim optimizarea în care am convertit is_cell_safeverifica de la un O(N) soluție la un O(1) Verifica. Acest lucru ne arată clar cum astfel de mici modificări pot produce impacturi uriașe asupra performanței.

Dacă ați citit până la capăt, sunt sigur că curiozitatea dvs. algoritmică a fost acum satisfăcută! Dar hei, acesta este doar vârful aisbergului.

Am în curând un alt post în care vom aborda o problemă similară cu N-Queens, dar cu o ușoară întorsătură.

Mulțumiri lui Rahul Gupta pentru contribuțiile sale valoroase în cod și articol.