Termeni și condiții
Pe forum este interzis:
Violatorii regulilor vor fi pedepsiți sever de către moderatori sau administratorul forumului și li se va refuza complet accesul la forum.
Utilizând acest forum puteți:
În acest articol, hai să vorbim despre un puzzle logic cunoscut numit "opt regine". Esența problemei constă în faptul că trebuie să fie capabil de a plasa pe tabla de șah (8 × 8) opt regine, astfel încât acestea nu sunt sub reciproc lupta (amintiți-vă că Regina (Regina) are un atacant și în diagonală). Voi spune că există mai multe variante ale aranjamentului, dar nu este întotdeauna ușor să le găsiți manual, este deosebit de dificil să puneți ultima regină. Una dintre variantele reglajelor reginei este prezentată în figura 1 de mai jos.
Pentru a rezolva problema celor opt regine, vom scrie un program în limbajul de programare C ++, care va aranja reginele. Vă sugerez să urmați această tactică:
1. Tabla de șah trebuie prezentată sub forma unei matrice bidimensionale, de dimensiune 8x8.
2. Pentru fiecare celulă din matrice, specificați un număr care va indica cât de mult din respectiva celulă regina poate bate alte celule. Vezi Figura 2
După cum puteți vedea, dacă plasați regina în poziția x = 2, y = 1, atunci sub bătălie vor fi 23 de celule. O astfel de procedură va trebui făcută pentru fiecare celulă de tablă de șah (matrice bidimensională). Ca rezultat, obținem următoarea imagine, prezentată mai jos în Figura 3
3. Odată ce prioritățile sunt stabilite, selectați celula cu prioritatea minimă (cea cu care mai puțin de alte bate bord de celule) și a pus pe ea regina. Cred că este de înțeles aici. deoarece dacă ai pus regine pe acele celule cu care să bată mai multe alte celule, înainte de plasarea opt regine nu ajungem. Continuăm să justificăm. dacă există mai multe celule cu o prioritate minimă (și chiar la începutul aranjamentului va fi așa), atunci vom alege aleatoriu corespunzător. Cum este logic să organizăm? Pentru a face acest lucru, trebuie să găsim mai întâi prioritatea minimă (de exemplu, 21 - că este cel mai mic din prima iterație - a se vedea figura 3), apoi conta numărul cu prioritate a celulelor (în acest caz, cu 21 dintre aceste aceleași celule este deja 28), denumit în continuare generează un număr aleator în intervalul de la 1 la numărul de celule identice (din 28) și, din care rezultă din numărul generație, a pus regina la locația dorită. Cușca, unde am pus regina, va fi cumva marcată, de exemplu, atribuirea i o valoare de 100. Puteți lua absolut orice valoare, cu excepția faptului că este selectată, astfel încât nu este definită ca fiind minim în prioritate.
4. După setarea reginei, trebuie să scoateți celulele bătut de ele, marcându-le cu un număr. Să presupunem că marchez aceste celule pentru comoditate cu numărul 99.
O mică explicație. În cazul în care algoritmul de bază de aranjament de regine va lucra și vom rămâne pe placa (matrice bidimensională, care emulează o tablă de șah) o celulă cu numerele 100 (aceasta regina) și 99 - celule învinețită, obținem rezultatul pe ecran cu condiția ca, dacă ne întâlnim numărul 100 - care trage regina (sau consola - fulgul de zăpadă, gratar, etc), în caz contrar face doar celula martor (sau consola pentru claritate, aveți posibilitatea să le marcați cu o cratimă, puncte, etc).
5. Din nou, totul se repetă de la punctul 2 la 4, până când aranjăm toate reginele, care ar trebui să fie opt. Există un alt punct: la prima încercare, chiar folosind așa-numita abordare "inteligentă" pentru implementarea sarcinii, algoritmul de mai sus nu poate plasa toate cele opt regine. Dar există o cale de ieșire din această situație. După plasare, vom verifica: sa dovedit că a pus toate reginele. Dacă nu, repetați din nou acordul.
În următoarea figură a patra, activez algoritmul de mai sus pentru claritate. Se pot produce diferite variante de aranjamente, dar pentru acest lucru trebuie să reporniți pagina web ( „Refresh“ în browser-ul sau F5-ul), iar apoi rezultatul se va schimba. Din păcate, încă nu cunosc tehnologia web-Ajax, așa că pentru a obține o nouă imagine, trebuie să reîncărcați pagina.
Iată tipul de program (pentru moment, citez doar partea principală - funcția principal ()) care implementează algoritmul
După cum puteți vedea, ea implementează ceea ce am spus mai sus
1) Declasați o placă de tablouri bidimensională. dimensiunea celulelor de 8 x 8 - aceasta va fi tabla noastră de șah. De asemenea, vom avea nevoie de variabile pentru a stoca coordonatele punctelor (x și y) și indicii către ei (ptrX și ptrY). Pentru a inițializa matricea cu zerouri, vom folosi funcția resetBoard ().
2) Matricea este declarată, inițializată. Acum ne uităm în buclă. care va fi pentru noi să realizăm aranjamentul a opt regine. Așa cum am spus în paragraful 2 de mai sus, trebuie să ne stabilim prioritatea pentru fiecare celulă din matrice. Acest lucru se va face prin funcția updateBoard ().
4) După ce am pus-o pe regină, vom marca celulele ucise de el. Aceasta se face prin funcția deleteCell ().
Acest proces se repetă exact de opt ori, așa cum se specifică în condițiile pentru bucla pentru. Dacă, așa cum am scris mai sus, nu va lucra cu prima încercare de a plasa opt regine, procesul de plasare este eliminat prin utilizarea resetBoard () și plasarea ciclului începe din nou. Pentru a ne informa dacă toate cele opt regine sunt plasate sau nu, se utilizează funcția checkQueens (). care întoarce o minciună. dacă nu a ieșit, și adevărul. dacă aranjamentul a reușit.
Aici, în principiu, și tot ce vroiam să spun despre acest algoritm. Implementarea completă a programului este prezentată mai jos.
Rezultatul programului
P.S. De asemenea, pe site găsiți o altă implementare a algoritmului "Opt Queens", implementat de programatorul Alexei și prezentat pe forum. pentru care vă mulțumește foarte mult.
Articole similare
Trimiteți-le prietenilor: