- Declarația problemei
- algoritmul traversarea
- Un exemplu al programului
- Listing:
Acest puzzle interesant a fost propus matematician Euler. Sarcina la prima vedere, este destul de simplu # 150; ai nevoie de un cavaler de șah, situat pe o celulă arbitrară a tablă de șah, pentru a ocoli toate celelalte celule ale consiliului, a căror dimensiune este, de asemenea, stabilite în mod arbitrar. Cu toate acestea, doar o singură dată poate părea ca o singură celulă.
Calul, după cum știți, merge la L în formă. Ie în două celule în orice direcție (în sus, jos, stânga, dreapta), și o celulă într-o perpendicular. Astfel, un cal, acesta poate fi un maxim de opt linii diferite de celule predeterminate (sau mai puțin în cazul în care calul este situat la marginile plăcii).
Pentru a rezolva această problemă pe un computer, este necesar să se dezvolte regulile, potrivit cărora computerul va alege o mișcare. În principiu, următoarea mișcare poate fi selectat în mod aleatoriu.
Regula originală, oferind un liniar-timp placi de algoritm plinta, Varnsdorf (warnsdorff) a fost propusă în 1983. Am implementat în activitatea lor de curs.
Algoritmul este formulat foarte simplu: următoarea mutare calul pentru a face o celulă în cazul în care există cele mai puține mișcări posibile. În cazul în care același număr de celule muta mai mult, puteți alege orice.
În practică, acest lucru se realizează, de exemplu, după cum urmează. Înainte de fiecare muta rating evaluat cel mai apropiat cal domenii disponibile - domenii în care calul nu a fost încă, și el se poate deplasa într-o tură. câmp Rating-ul este determinat de numărul de câmpuri disponibile de lângă ea. Este mai mic rating, cu atât mai bine este. Apoi a făcut progrese pe teren, cu cel mai mic rating (pe oricare dintre acestea, în cazul în care mai mult de unul), și așa mai departe până când nu există în cazul în care pentru a merge.
Euristici sunt întotdeauna de lucru pe panourile de la 5x5 până la 76x76 celule pentru mari dimensiuni bord cal poate veni la un impas. În plus, în funcție de regula algoritmului nu oferă toate soluțiile posibile (de exemplu, piese de cai), puteți merge împotriva regulilor și a obține încă o sarcină rundă satisfăcătoare.
Există un algoritm liniar pentru placi de orice dimensiune care împarte placa în bucăți mai mici, dar, din cauza abundenței de cazuri speciale, este destul de complicat și nu la fel de interesant ca acest euristică elegant.
Fiecare curs poate fi descrisă ca circulând un număr predeterminat de celule pe orizontală și pe verticală. De exemplu, deplasarea la zero corespunde deplasa în două celule orizontale, și „-1“ celulă verticală (semnul minus indică direcția de deplasare).
Umplerea disponibilitatea unei matrice un pic mai complicat. Fiecare element corespunde unei celule de pe bord, dar aici înregistrăm informații despre cât de multe celule puteți merge pe platoul de filmare. De exemplu, în a1 celula poate semăna cu două celule (c2 și b3). O serie de aceasta înainte de a rezolva problema este următoarea:
Un exemplu al programului
Dialog pentru a crea o tablă de șah cu un cal pe care am ales să dimensiunea câmpului, dimensiunea celulei, poziția, și alți parametri ai calului. Puteți descărca, de asemenea, elementele de imagine ale consiliului fișierelor.
5x5 câmp creat, calul se află în poziția de 2x4. Acum, că domeniul a fost deja creat, puteți rula placa de cal de by-pass algoritm.
Rezultat Algoritmul Traversarea vizibil pe numerele de bord afișate bord comanda traversal cal. Puteți șterge ordinea filelor și executați din nou algoritmul. Puteți merge, de asemenea, cal cu ajutorul săgeților și șoareci.
//// versiunea 8 recomment finală
// trage o imagine de cal în domeniul
g.drawImage (HorseImage, EventBoardHorseMovedelX, EventBoardHorseMovedelY, null);
* Creează o imagine de fundal eșichierului unei matrice densă de celule lumină și întuneric,
* Dacă imaginea nu init. (Null), fondul nu este tras,
* Ordinea de dispunere a celulelor „de cursivă, printr-o“, care este prima celulă în domeniu este determinată de primul parametru.
* WhiteCells @param Imagine de celule luminoase (celule).
* BlackCells @param Image celulă întunecată (celule).
* @param firstCellWhite dacă este adevărat - prima celulă a câmpului de lumină, dacă este fals - întuneric
* @return adevărat - fundal este pictat, fals - fundalul nu este desenată din faptul că nu izobrascheniya de inițializare. sau inițializare. dimensiunea bord.
BoardFonCreate publice boolean (BufferedImage whiteCells, BufferedImage blackCells, firstCellWhite Boolean)
BoardFon = new BufferedImage (BoardSize, BoardSize, BufferedImage.TYPE_INT_RGB);
int Kx = 0 /// coordonatele "desen punct"
boolean firstCell = firstCellWhite; flag /// pentru prima celulă
Grafică Fon = BoardFon.createGraphics (); /// desen
Fon.clearRect (0, 0, BoardFon.getWidth (), BoardFon.getHeight ()); /// cleanse
pentru (int j = 0; j Kx = 0; // o linie nouă pentru (int i = 0; i Alb // în cazul în care o celulă, chiar și prima celulă albă Alb // dacă celula ciudat și prima celulă a negru Fon.drawImage (whiteCells, Kx, Ky, CellsSize, CellsSize, null); Fon.drawImage (blackCells, Kx, Ky, CellsSize, CellsSize, null); Kx = kx + CellsSize; // pass în desenul din dreapta a celulei următoare (celule) /// linia următoare începe cu culoarea opusă a celulei * Flag faptul că placa de tras calul cu mouse-ul * Coordonatele inițiale ale calului pentru a trage, X pe gorizotali (pixeli) * Coordonatele inițiale ale calului pentru a trage, Y verticale (pixeli) * Schimbarea coordonatelor, X pe gorizotali (pixeli) * Schimbare de coordonate Y verticale (pixeli) * Coordonatele mouse-ului făcând clic pe LMB în cal sistem de coordonate (JButton), X pe gorizotali (pixeli) * Mouse-ul coordonatele când se apasă calul LMB într-un sistem de coordonate (JButton), Y verticale (pixeli) * Panou Pereprorisovka (bord) * Poziția inițială atunci când se deplasează săgeata * Inainte de prima parte a „T“ accident vascular cerebral în formă de * Adică, poziția orizontală a celulei (fragmente, celule). * Poziția inițială atunci când se deplasează săgeata * Inainte de prima parte a „T“ accident vascular cerebral în formă de * Adică, Poziția verticală a celulei (fragmente, celule). * Cheie Codul care a fost apăsat în primul rând, „prima mana“ * Componenta decalat față de prima parte a „T“ accident vascular cerebral în formă de * (Lungimea segmentului în celula 1) finală int firstPartG = 2; * Direcția până la prima parte a „T“ accident vascular cerebral în formă de * Pentru a doua parte este perpendicular pe primul ( „L“), * Adevărat - vertical. fals - orizontal. * Cheie Codul care a fost apăsat de două: adică a doua săgeată după prima săgeată * Componenta de compensare în a doua parte a „T“ accident vascular cerebral în formă de * (Lungimea segmentului în celula 1) finală int secondPartG = 1; * Calul este o copie a (aparținând bord) publice clHorse cal = nul; * Clasa de cai moștenită de la JButton pentru plasarea în continuare pe panoul care bord. * Cal Imaginea nu este conținută în clasa, iar clasa este luat de placi, precum și parametrii și funcțiile sunt luate. * (Clasele de cai și masă nu sunt separabile deloc). class clHorse extinde JButton privat statică finală serialVersionUID lung = 1L; * Constructorul implicit inițializează calul this.setBounds (0, 0, CellsSize, CellsSize); /// pune cavaler de pe placa (implicit) this.addKeyListener (nou KeyMoveListener ()); // adauga intrarile de la tastatura ascultător pentru evenimente de cai mouseMoveListener = new MouseMoveListener (); // ascultător pentru evenimente mouse-ul în legătură cu calul * Constructorul inițializează calul cu inscrie pe un stand * Numărul de celule @param PosX orizontal * @param numărul de celule posy pe verticală clHorse (int PosX, int posy) acest lucru (); // apelează constructorul (implicit) calul HorseMove (PosX, Posy); /// cal poartă un anumit loc de pe placa * Celule orizontale Poziție cal: 0,1,2. CellsNumberX-1 * Celulă Poziție verticală cal: 0,1,2. CellsNumberY-1articole similare