Ocolind cavaler tablă de șah
Regula originală, oferind un liniar-timp placi de algoritm plinta, Varnsdorf (warnsdorff) a fost propusă în 1983.
Regula 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.
Un alt mod de rezolvare a problemei este, în mod evident, în bustul cu retragere. Următoarea ilustrație este dată să se apropie de 8x8 bord.
Folosind două rânduri dimensionale matrice [64] și col [64] pentru stocarea numerele rândurilor, respectiv, și coloanele care succesiv calul trece bord.
Calul, care se află în poziția (i, j), se pot deplasa de lângă a fi în celule cu coordonate (i-2, j + 1), (i-1, j + 2), (i + 1, j + 2), ( i + 2 j + 1), (i + 2 j-1), (i + 1, j-2), (i-1, j-2), (i-2, j-1). Rețineți că, în cazul în care calul este aproape de marginea de bord, unele mișcări pot provoca mișcarea calului dincolo de faptul că, desigur, inacceptabilă. Opt posibil cal deplasările pot fi prezentate sub forma a două matrice ktmov1 [] și ktmov2 [], așa cum sa demonstrat în următorul fragment de program.
Prin urmare, cal, situat la poziția (i, j) se poate deplasa într-o poziție (i + ktmov [k], j + ktmov2 [k]), unde k - orice valoare în intervalul 0 - 7 ales dintre condițiile că calul trebuie să rămână pe bord. Astfel, programul care implementează mișcarea calului, în conformitate cu condițiile de mai sus vor fi după cum urmează: